LeetCode-概率最大的路径-题解（Dijkstra）

输入：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 之间不存在路径
复制代码

解题思路

该题目乍看之下好像挺复杂的（实际上我也被唬到了），之前类似的题目都是求最短/长路径之类的，但是现在突然跑出来了一个求概率的题目。但是认真想一想的话，这个其实和求路径长度没什么区别，求路径长度是把各个节点间的路径叠加，而本题只不过是把叠加改成了叠乘了而已。因此，我们可以使用万能的Dijkstra算法来进行求解，把加法改成乘法，把小于改成大于就ok了。

有些同学可能会有疑惑，Dijkstra算法不是是贪心的，不能用来求最长路径，要不然会产生环吗？确实如此，但是本题要求的并不是最长路径，而是最大概率。对于最长路径来说，由于路径是越走越长的，如果使用Dijkstra算法会让算法无限走下去，但是如果是最大概率的话，由于概率只会越乘越小，因此不会产生环，故可以使用Dijkstra算法。

代码

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<vector<pair<double, int>>> graph(n);
        for (int i = 0; i < edges.size(); i++) {
            auto& e = edges[i];
            graph[e[0]].emplace_back(succProb[i], e[1]);
            graph[e[1]].emplace_back(succProb[i], e[0]);
        }

        priority_queue<pair<double, int>> que;
        vector<double> prob(n, 0);

        que.emplace(1, start);
        prob[start] = 1;
        while (!que.empty()) {
            auto [pr, node] = que.top();
            que.pop();
            if (pr < prob[node]) {
                continue;
            }
            for (auto& [prNext, nodeNext] : graph[node]) {
                if (prob[nodeNext] < prob[node] * prNext) {
                    prob[nodeNext] = prob[node] * prNext;
                    que.emplace(prob[nodeNext], nodeNext);
                }
            }
        }
        return prob[end];
    }
};
复制代码