1.题目

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25

示例 2：

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000

示例 3：

输入：n = 3, edges = 0,1, succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径

提示：
2 <= n <= 104
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每两个节点之间最多有一条边

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-maximum-probability

2.思路

（1）dijkstra算法
思路参考我写了一个模板，把 DIJKSTRA 算法变成了默写题。

3.代码实现（Java）

//思路1————dijkstra算法
class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //使用邻接表来存储图
        List<double[]>[] graph = new LinkedList[n];
        //创建 n 个节点
        for (int i = 0; i < n; i++) {
            graph[i] = new LinkedList<>();
        }
        //根据 edges 和 succProb 来创建节点之间的边
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            double weight = succProb[i];
            // a -> b   b -> a
            graph[a].add(new double[]{(double)b, weight});
            graph[b].add(new double[]{(double)a, weight});
        }
        return dijkstra(start, end, graph);
    }

    public double dijkstra(int start, int end, List<double[]>[] graph) {
        //dist[i]: 起点 start 到节点 i 的最短路径长度(即本题中的概率)
        double[] dist = new double[graph.length];
        //初始化 dist，dist[i] = -1 表明起点 start 到节点 i 之间不可达
        Arrays.fill(dist, -1);
        dist[start] = 1;
        //定义优先级队列，distFromStart值较小的元素排在队首
        Queue<State> queue = new PriorityQueue<>((a, b) -> {
            return Double.compare(b.distFromStart, a.distFromStart);
        });
        //从起点 start 开始进行 BFS
        queue.offer(new State(start, 1));
        while (!queue.isEmpty()) {
            //取出队首元素
            State curState = queue.poll();
            int curNodeID = curState.id;
            double curDistFromStart = curState.distFromStart;
            //如果找到终点 end，则直接返回 curDistFromStart 即可
            if (curNodeID == end) {
                return curDistFromStart;
            }
            //需要注意的是本题要找出从起点到终点成功概率最大的路径，并返回其成功概率
            if (curDistFromStart < dist[curNodeID]) {
                continue;
            }
            //将与当前节点相邻的所有节点存入队列
            for (double[] neighbor : graph[curNodeID]) {
                int nextNodeID = (int)neighbor[0];
                double distToNextNode = dist[curNodeID] * neighbor[1];
                //更新 dist
                if (dist[nextNodeID] < distToNextNode) {
                    dist[nextNodeID] = distToNextNode;
                    queue.offer(new State(nextNodeID, distToNextNode));
                }
            }
        }
        return 0.0;
    }

    class State {
        // 图节点的 id
        int id;
        // 从 start 节点到当前节点的距离(在本题中指从 start 节点到当前节点遍历成功的概率)
        double distFromStart;

        public State(int id, double distFromStart) {
            this.id = id;
            this.distFromStart = distFromStart;
        }
    }
}