LeetCode_dijkstra算法_中等_1514. 概率最大的路径

末蓝、 2023-10-06 22:37 7阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

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

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

**示例 1：**  
![在这里插入图片描述][d3ad425b039548a19455a73347695bdc.png]  
输入：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：**  
![在这里插入图片描述][3d6eaff85ef74f749d457021841ad437.png]  
输入：n = 3, edges = \[\[0,1\],\[1,2\],\[0,2\]\], succProb = \[0.5,0.5,0.3\], start = 0, end = 2  
输出：0.30000

**示例 3：**  
![在这里插入图片描述][54d3fe4c106c4dd1a7d46aa79e9bac60.png]  
输入：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 算法变成了默写题][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;
            }
        }
    }

[d3ad425b039548a19455a73347695bdc.png]: https://img-blog.csdnimg.cn/d3ad425b039548a19455a73347695bdc.png
[3d6eaff85ef74f749d457021841ad437.png]: https://img-blog.csdnimg.cn/3d6eaff85ef74f749d457021841ad437.png
[54d3fe4c106c4dd1a7d46aa79e9bac60.png]: https://img-blog.csdnimg.cn/54d3fe4c106c4dd1a7d46aa79e9bac60.png
[DIJKSTRA]: https://labuladong.github.io/algo/2/20/55/