概率最大的路径 图解题解

这道题到底在问什么

输入

n=3, edges=[[0,1],[1,2],[0,2]], prob=[0.5,0.5,0.2], start=0, end=2

输出

0.25(走 0→1→2:0.5×0.5,比直达 0→2 的 0.2 大)

最优解：一步一步想明白

1. 3记住「dist 记最大概率、优先队列取概率最大的、沿边乘 p 松弛」,下面逐帧套它。
2. 4初始化:起点 0 的概率记为 1(它自己一定「到得了自己」),其余节点先记 0(还没找到路)。把 (节点 0,概率 1) 放进优先队列。终点是节点 4。
3. 5从队列取出当前概率最大的节点 0(概率 1)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
4. 60-1 这条边(概率 0.5):到 1 的新概率 = 1 × 0.5 = 0.5,比原来的 0 大,更新 dist[1] = 0.5 并入队。
5. 70-2 这条边(概率 0.6):到 2 的新概率 = 1 × 0.6 = 0.6,比原来的 0 大,更新 dist[2] = 0.6 并入队。
6. 8从队列取出当前概率最大的节点 2(概率 0.6)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
7. 92-0 这条边(概率 0.6):到 0 的新概率 = 0.6 × 0.6 = 0.36,没有原来的 1 大,不更新。
8. 102-1 这条边(概率 0.5):到 1 的新概率 = 0.6 × 0.5 = 0.3,没有原来的 0.5 大,不更新。
9. 112-3 这条边(概率 0.5):到 3 的新概率 = 0.6 × 0.5 = 0.3,比原来的 0 大,更新 dist[3] = 0.3 并入队。
10. 122-4 这条边(概率 0.2):到 4 的新概率 = 0.6 × 0.2 = 0.12,比原来的 0 大,更新 dist[4] = 0.12 并入队。
11. 13从队列取出当前概率最大的节点 1(概率 0.5)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
12. 141-0 这条边(概率 0.5):到 0 的新概率 = 0.5 × 0.5 = 0.25,没有原来的 1 大,不更新。
13. 151-2 这条边(概率 0.5):到 2 的新概率 = 0.5 × 0.5 = 0.25,没有原来的 0.6 大,不更新。
14. 161-3 这条边(概率 0.9):到 3 的新概率 = 0.5 × 0.9 = 0.45,比原来的 0.3 大,更新 dist[3] = 0.45 并入队。
15. 17从队列取出当前概率最大的节点 3(概率 0.45)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
16. 183-1 这条边(概率 0.9):到 1 的新概率 = 0.45 × 0.9 = 0.405,没有原来的 0.5 大,不更新。
17. 193-2 这条边(概率 0.5):到 2 的新概率 = 0.45 × 0.5 = 0.225,没有原来的 0.6 大,不更新。
18. 203-4 这条边(概率 0.7):到 4 的新概率 = 0.45 × 0.7 = 0.315,比原来的 0.12 大,更新 dist[4] = 0.315 并入队。
19. 21从队列取出概率最大的是节点 4(概率 0.315),它正是终点!Dijkstra 第一次定下终点就是最优,直接返回最大概率 0.315。
20. 22点亮最优路径的一段:0-1(概率 0.5)。累乘到这里概率 = 0.5。
21. 23点亮最优路径的一段:1-3(概率 0.9)。累乘到这里概率 = 0.45。
22. 24点亮最优路径的一段:3-4(概率 0.7)。累乘到这里概率 = 0.315。
23. 25最优路径 0→1→3→4 全部点亮,概率 0.5 × 0.9 × 0.7 = 0.315。它不是边数最少的:边数更少的 0→2→4 只有 0.6 × 0.2 = 0.12,远不如它。要的是乘积最大的那条。这正是 Dijkstra 把「取最小相加」换成「取最大相乘」后求到的解。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
import heapq
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        g = [[] for _ in range(n)]
        for (a, b), p in zip(edges, succProb):
            g[a].append((b, p)); g[b].append((a, p))
        dist = [0.0] * n
        dist[start_node] = 1.0
        heap = [(-1.0, start_node)]
        while heap:
            prob, u = heapq.heappop(heap)
            prob = -prob
            if u == end_node:
                return prob
            if prob < dist[u]:
                continue
            for v, p in g[u]:
                np = prob * p
                if np > dist[v]:
                    dist[v] = np
                    heapq.heappush(heap, (-np, v))
        return 0.0

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        vector<vector<pair<int,double>>> g(n);
        for (int i = 0; i < (int)edges.size(); ++i) {
            g[edges[i][0]].push_back({edges[i][1], succProb[i]});
            g[edges[i][1]].push_back({edges[i][0], succProb[i]});
        }
        vector<double> dist(n);
        priority_queue<pair<double,int>> pq;
        dist[start_node] = 1.0; pq.push({1.0, start_node});
        while (!pq.empty()) {
            auto [prob, u] = pq.top(); pq.pop();
            if (u == end_node) return prob;
            if (prob < dist[u]) continue;
            for (auto [v, p] : g[u]) if (prob * p > dist[v]) {
                dist[v] = prob * p;
                pq.push({dist[v], v});
            }
        }
        return 0.0;
    }
};

import java.util.*;
class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        List<double[]>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < edges.length; i++) {
            g[edges[i][0]].add(new double[]{edges[i][1], succProb[i]});
            g[edges[i][1]].add(new double[]{edges[i][0], succProb[i]});
        }
        double[] dist = new double[n];
        PriorityQueue<double[]> pq = new PriorityQueue<>((a,b) -> Double.compare(b[0], a[0]));
        dist[start_node] = 1.0; pq.offer(new double[]{1.0, start_node});
        while (!pq.isEmpty()) {
            double[] cur = pq.poll();
            double prob = cur[0]; int u = (int) cur[1];
            if (u == end_node) return prob;
            if (prob < dist[u]) continue;
            for (double[] e : g[u]) {
                int v = (int) e[0];
                double np = prob * e[1];
                if (np > dist[v]) { dist[v] = np; pq.offer(new double[]{np, v}); }
            }
        }
        return 0.0;
    }
}

复杂度

面试官可能追问