最短路径
01 / 共享的机制
从源点出发,到所有节点的最短距离。机制按边能携带什么分叉 —— 等权坍缩成 BFS,非负权要优先队列(Dijkstra),允许负权要做多轮松弛(Bellman-Ford), 全源距离则落到 Floyd-Warshall。
01 / 一句话本质
当边权非负时,未访问节点中当前距离最小的那个不可能再被其他未访问节点松弛得更短 —— 所以用一个最小优先队列,每轮取出最近的节点并松弛它的出边,一次扫描就能得到最短距离。
题目非负权图上,从源点到所有节点的最短路径图网格源点A
图有 6 个节点。把所有距离初始化为 ∞,把源点放入优先队列。
步
0 / 47
优先队列
—
已确定
0 / 6
0 / 47
02 / 模式骨架
# 从源点出发的 Dijkstra —— 边权非负dist[v] ← ∞ for all vdist[s] ← 0pq ← 最小堆 (0, s)while pq 非空:(d, u) ← pq.pop_min() # 取出最小if d > dist[u]: continuefor (v, w) in neighbors(u): # 松弛if dist[u] + w < dist[v]:dist[v] ← dist[u] + wpq.push((dist[v], v)) # decrease-key 或直接重复入堆
03 / 什么时候用这个模式
"非负权"
边带正数(或零)代价 —— 距离、时间、金钱、延迟。只要可能出现负权,Dijkstra 就会悄无声息地给出错答案,改用 Bellman-Ford。
"最小代价 / 最短距离"
目标是累加边权,而不是数跳数。「最便宜」「总时间最少」「最省力路径」 —— 凡是沿路径累加一个非负代价的题都属于这一类。
"单源到多个目标"
一个源点,到所有其他节点的距离 —— 或者到某个特定目的地。 一次 Dijkstra 同时给出两种答案;若只关心单个目的地,可以在它出队时提前结束。
"优先队列 / 最小堆"
数据结构就是算法本身。每次永远取出当前距离最小的节点 —— 普通队列或栈在这里行不通,因为权值不一致时,第一次到达节点的路径并不一定是最短的。
04 / 常见坑
i.
在含负权的图上跑 Dijkstra。
节点一旦出队就被定型,Dijkstra 不会再重新检查 —— 但之后某条负权边仍然可能把它的距离改得更短。 算法不会报错,只是默默给出错误答案。只要可能有负权,改用 Bellman-Ford。
ii.
忘了过期项的检查。
大多数实现是松弛时直接把新的
(dist, v) 推进堆,而不做真正的 decrease-key, 所以堆里会堆积大量过期项。出队时必须判断 d > dist[u] 就跳过; 否则节点会被重复处理,时间复杂度被放大。iii.
在带「最多 K 次中转」之类约束的题上直接用 Dijkstra。
Dijkstra 只优化累计代价。一旦加上跳数或中转上限(LC 787), 最短路可能需要更多的中转才能满足约束,「取当前最小」的贪心前提就不成立了。 这时要改用带状态的 BFS、跑 K 轮的 Bellman-Ford, 或者以
(cost, stops) 为键的改造版 Dijkstra。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
无权 BFS
当每条边的代价相同时使用 —— 一步 = 一条边。
网格 · 迷宫 · O(V + E)
Dijkstra
当边权非负时使用。
优先队列 · O((V + E) log V)
Bellman-Ford
当允许负权,或需要检测负环时使用。
V−1 轮松弛 · O(V · E)
Floyd-Warshall
当需要全源距离、而不仅是单源时使用。
经中转点 DP · O(V³)