题目描述
思路解析动画文字版
记住「dist 记最大概率、优先队列取概率最大的、沿边乘 p 松弛」,下面逐帧套它。
初始化:起点 0 的概率记为 1(它自己一定「到得了自己」),其余节点先记 0(还没找到路)。把 (节点 0,概率 1) 放进优先队列。终点是节点 4。
从队列取出当前概率最大的节点 0(概率 1)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
0-1 这条边(概率 0.5):到 1 的新概率 = 1 × 0.5 = 0.5,比原来的 0 大,更新 dist[1] = 0.5 并入队。
0-2 这条边(概率 0.6):到 2 的新概率 = 1 × 0.6 = 0.6,比原来的 0 大,更新 dist[2] = 0.6 并入队。
从队列取出当前概率最大的节点 2(概率 0.6)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
2-0 这条边(概率 0.6):到 0 的新概率 = 0.6 × 0.6 = 0.36,没有原来的 1 大,不更新。
2-1 这条边(概率 0.5):到 1 的新概率 = 0.6 × 0.5 = 0.3,没有原来的 0.5 大,不更新。
2-3 这条边(概率 0.5):到 3 的新概率 = 0.6 × 0.5 = 0.3,比原来的 0 大,更新 dist[3] = 0.3 并入队。
2-4 这条边(概率 0.2):到 4 的新概率 = 0.6 × 0.2 = 0.12,比原来的 0 大,更新 dist[4] = 0.12 并入队。
从队列取出当前概率最大的节点 1(概率 0.5)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
1-0 这条边(概率 0.5):到 0 的新概率 = 0.5 × 0.5 = 0.25,没有原来的 1 大,不更新。
1-2 这条边(概率 0.5):到 2 的新概率 = 0.5 × 0.5 = 0.25,没有原来的 0.6 大,不更新。
1-3 这条边(概率 0.9):到 3 的新概率 = 0.5 × 0.9 = 0.45,比原来的 0.3 大,更新 dist[3] = 0.45 并入队。
从队列取出当前概率最大的节点 3(概率 0.45)并定下来。看它的每条边,尝试把邻居的概率「乘上去」刷新得更大。
3-1 这条边(概率 0.9):到 1 的新概率 = 0.45 × 0.9 = 0.405,没有原来的 0.5 大,不更新。
3-2 这条边(概率 0.5):到 2 的新概率 = 0.45 × 0.5 = 0.225,没有原来的 0.6 大,不更新。
3-4 这条边(概率 0.7):到 4 的新概率 = 0.45 × 0.7 = 0.315,比原来的 0.12 大,更新 dist[4] = 0.315 并入队。
从队列取出概率最大的是节点 4(概率 0.315),它正是终点!Dijkstra 第一次定下终点就是最优,直接返回最大概率 0.315。
点亮最优路径的一段:0-1(概率 0.5)。累乘到这里概率 = 0.5。
点亮最优路径的一段:1-3(概率 0.9)。累乘到这里概率 = 0.45。
点亮最优路径的一段:3-4(概率 0.7)。累乘到这里概率 = 0.315。
最优路径 0→1→3→4 全部点亮,概率 0.5 × 0.9 × 0.7 = 0.315。它不是边数最少的:边数更少的 0→2→4 只有 0.6 × 0.2 = 0.12,远不如它。要的是乘积最大的那条。这正是 Dijkstra 把「取最小相加」换成「取最大相乘」后求到的解。
边界:不连通返回 0;概率 0 的边等于断开。
两个延伸:可取对数转加法最短路;Bellman-Ford 可行但更慢。
参考代码
from typing import Listimport heapqclass 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复杂度
- 时间：O((n+e)·log n)，e 条边,每条最多触发一次入堆,堆操作 O(log n);整体近似 O((n+e)log n)
- 空间：O(n+e)，邻接表 O(n+e),dist 数组 O(n),堆最坏 O(e)(不删过期记录),合计 O(n+e)
易错点
面试追问把动画讲成自己的话
追问能不能取对数把乘法变加法,再跑标准最短路?
追问为什么这里不能用 Bellman-Ford 直接乘?会有问题吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
可以到达所有点的最少点数目
LeetCode 1557 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题