What is the approach for solving the Path with Maximum Probability problem?

You should use a priority queue (max-heap) and a modified Dijkstra's algorithm to maximize the probability of traversing edges from start to end.

How does GhostInterview assist in solving Path with Maximum Probability?

It provides feedback on applying graph algorithms, ensuring correct handling of probabilities and edge cases, and optimizing your solution.

What is the time complexity of the Path with Maximum Probability solution?

The time complexity is O((n + m) * log n), where n is the number of nodes and m is the number of edges in the graph.

Can this problem be solved without a priority queue?

A priority queue is the most efficient approach, but it can be solved with other algorithms like DFS with manual probability tracking, though less efficiently.

What happens if the probabilities multiply to zero?

If the product of probabilities for a path equals zero, it indicates that path is impossible, and the algorithm should return zero for such cases.

#1514

Medium

auto_awesome堆

LeetCode 题解工作台

概率最大的路径

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成…

数组图堆（优先队列）最短路径

题目描述

给你一个由 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 <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每两个节点之间最多有一条边

lightbulb

解题思路

方法一：堆优化 Dijkstra 算法

我们可以使用 Dijkstra 算法求解最短路径，这里我们稍微修改一下，求解最大概率路径。

我们可以使用一个优先队列（大根堆） $\textit{pq}$ 来存储从起点到各个节点的概率以及节点编号。初始时我们将起点的概率设为 $1$ ，其余节点的概率设为 $0$ ，然后将起点加入到 $\textit{pq}$ 中。

在每一次的迭代中，我们取出 $\textit{pq}$ 中概率最大的节点 $a$ ，以及 $a$ 的概率 $w$ 。如果节点 $a$ 的概率已经大于 $w$ ，那么我们就可以跳过这个节点。否则我们遍历 $a$ 的所有邻接边 $(a, b)$ 。如果 $b$ 的概率小于 $a$ 的概率乘以 $(a, b)$ 的概率，那么我们就可以更新 $b$ 的概率，并将 $b$ 加入到 $\textit{pq}$ 中。

最终，我们可以得到从起点到终点的最大概率。

时间复杂度 $O(m \times \log m)$ ，空间复杂度 $O(m)$ 。其中 $m$ 为边的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def maxProbability(
        self,
        n: int,
        edges: List[List[int]],
        succProb: List[float],
        start_node: int,
        end_node: int,
    ) -> float:
        g: List[List[Tuple[int, float]]] = [[] for _ in range(n)]
        for (a, b), p in zip(edges, succProb):
            g[a].append((b, p))
            g[b].append((a, p))
        pq = [(-1, start_node)]
        dist = [0] * n
        dist[start_node] = 1
        while pq:
            w, a = heappop(pq)
            w = -w
            if dist[a] > w:
                continue
            for b, p in g[a]:
                if (t := w * p) > dist[b]:
                    dist[b] = t
                    heappush(pq, (-t, b))
        return dist[end_node]

speed

复杂度分析

指标	值
时间	O((n + m) \cdot \log n)
空间	O(n + m)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate uses a priority queue to manage traversal based on probability.
question_mark
Ensure the candidate accounts for edge case scenarios, such as disconnected nodes or no valid path.
question_mark
Assess the candidate's understanding of probability and its potential impact on the accuracy of the solution, especially with floating-point operations.

warning

常见陷阱

外企场景

error
Forgetting to handle cases where no path exists between the start and end nodes, leading to incorrect results.
error
Not accounting for the precision errors when multiplying small probabilities, which can affect the final output.
error
Misapplying standard shortest-path algorithms without considering the unique nature of the problem, such as maximizing probabilities instead of minimizing distances.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the graph is directed? How would the solution change?
arrow_right_alt
How would the solution scale for graphs with hundreds of thousands of nodes and edges?
arrow_right_alt
What if the edge weights were not probabilities but costs? Would this become a traditional shortest-path problem?

help

常见问题

外企场景

继续练习

#1368 使网格图至少有一条有效路径的最小代价 #2290 到达角落需要移除障碍物的最小数目 #2577 在网格图中访问一个格子的最少时间