---

1514. 概率最大的路径

• 标签：图、数组、最短路、堆（优先队列）
• 难度：中等

题目链接

• 1514. 概率最大的路径 - 力扣

题目大意

描述：给定一个 $n$ 个节点的无向图，边集 $edges$ 和概率 $succProb$。$succProb[i]$ 表示从 $edges[i][0]$ 到 $edges[i][1]$ 的成功概率。

要求：返回从 $start$ 到 $end$ 的最大成功概率。如果不可达，返回 $0$。

说明：

• $2 \le n \le 10^4$。
• $0 \le start, end < n$。
• $0 \le succProb[i] \le 1$。

示例：

• 示例 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

解题思路

思路 1：Dijkstra 变体（最大乘积路径）

1. 核心思想

路径概率 = 各边概率的乘积。要最大化从起点到终点的概率乘积。

这是最长路径问题的变体，但由于概率 $\le 1$，取对数后转化为最短路。不过更直接的方法是使用 Dijkstra 的变体：用最大堆替换最小堆，每次取概率最大的路径扩展。

由于概率在 $[0, 1]$ 之间，乘积不会越乘越大，因此可以用贪心（Dijkstra 的贪心性质依然成立：当前概率最大的路径一定是该节点的最优路径）。

2. 具体步骤

第 1 步：建无向图，邻接表存 $(neighbor, prob)$。

第 2 步：初始化 $dist[start] = 1.0$，其他为 $0$。最大堆 $(prob, node)$。

第 3 步：当堆非空：

• 弹出 $(prob, u)$。
• 如果 $prob < dist[u]$，跳过。
• 如果 $u == end$，直接返回 $prob$（贪心保证第一次弹出终点时就是最大概率）。
• 遍历邻居 $(v, p)$：
  • 如果 $dist[u] \times p > dist[v]$：更新 $dist[v]$，入堆。

第 4 步：返回 $0$。

3. 举例说明

以 $n=3, edges=[[0,1],[1,2],[0,2]], succProb=[0.5,0.5,0.2], start=0, end=2$ 为例：

0 --0.5-- 1
|        /
0.2   0.5
|    /
|  /
2

• $dist[0]=1.0$，堆：$(1.0, 0)$。
• 弹出 $(1.0, 0)$：邻居 $1(p=0.5)$，$dist[1]=0.5$；邻居 $2(p=0.2)$，$dist[2]=0.2$。
• 弹出 $(0.5, 1)$：邻居 $2(p=0.5)$，$dist[1]*0.5=0.25 > 0.2$，$dist[2]=0.25$。
• 如果先弹出 $(0.25, 2)$：不是终点时继续。

最大概率路径：$0 \to 1 \to 2$，概率 $0.5 \times 0.5 = 0.25$。

思路 1：代码

import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = [[] for _ in range(n)]
        for (u, v), p in zip(edges, succProb):
            graph[u].append((v, p))
            graph[v].append((u, p))

        dist = [0.0] * n
        dist[start] = 1.0
        pq = [(-1.0, start)]  # 最大堆，取负数

        while pq:
            prob, u = heapq.heappop(pq)
            prob = -prob
            if u == end:
                return prob
            if prob < dist[u]:
                continue
            for v, p in graph[u]:
                new_prob = prob * p
                if new_prob > dist[v]:
                    dist[v] = new_prob
                    heapq.heappush(pq, (-new_prob, v))

        return 0.0

思路 1：复杂度分析

• 时间复杂度：$O((n + m) \log n)$。
• 空间复杂度：$O(n + m)$。