最短路径
01 / 共享的机制
从源点出发,到所有节点的最短距离。机制按边能携带什么分叉 —— 等权坍缩成 BFS,非负权要优先队列(Dijkstra),允许负权要做多轮松弛(Bellman-Ford), 全源距离则落到 Floyd-Warshall。
01 / 一句话本质
反复松弛每一条边:做完 V−1 轮, 所有最短路径(边数最多 V−1)都已经被发现 —— 即使部分边权为负。
题目单源最短路径,允许负权图含负权源点A
图有 5 个节点 —— 共做 4 轮松弛。把所有距离初始化为 ∞。
步
0 / 66
轮
0 / 4
最近松弛
无变化
负环
—
0 / 66
02 / 模式骨架
# 从源点出发的 Bellman-Ford —— 允许负权dist[v] ← ∞ for all vdist[s] ← 0# V−1 轮 —— 最短路径最多使用 V−1 条边for round in 1 .. V−1:for (u, v, w) in edges:# 松弛if dist[u] + w < dist[v]:dist[v] ← dist[u] + w# 负环检测 —— 再多做一轮for (u, v, w) in edges:if dist[u] + w < dist[v]: return "存在负环"
03 / 什么时候用这个模式
"负权边"
最关键的信号。代价可以为负 —— 退款、收益、货币套利。这种情形下 Dijkstra 不再安全,Bellman-Ford 才是标准工具。
"检测负环"
跑完 V−1 轮后,再多做一轮。如果还有边能松弛,说明从源点可达的位置存在负环。
"最多 K 条边 / K 次中转"
把松弛轮数截断为 K,而不是 V−1。做完 K 轮后,
dist[v] 就是「最多用 K 条边」的最短路 —— 这是 Bellman-Ford 的经典用法。"汇率套利 / 货币兑换"
把
−log(rate) 作为边权,负环就对应一个套利环路 —— Bellman-Ford 能直接找到它。04 / 常见坑
i.
在含负权边的图上跑 Dijkstra。
Dijkstra 一旦把某个节点定型,后续的负权边就无法再修正它的距离 —— 会悄无声息地给出错误答案。只要边权可能为负,就必须用 Bellman-Ford (或者 SPFA / Johnson 算法)。
ii.
跑完 V−1 轮就停止,不做负环检测。
只有在不存在从源点可达的负环时,V−1 轮之后的距离才会稳定下来。 一定要再做一轮:如果还有边能松弛,答案不是某个数,而是「存在负环」。
iii.
当
dist[u] = ∞ 时,dist[u] + w 溢出。如果
dist[u] 还是无穷大,就要跳过这次松弛 —— 否则 ∞ + (−w) 可能回绕成一个有限值,悄悄污染距离数组。务必加上判断。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
无权 BFS
当每条边的代价相同时使用 —— 一步 = 一条边。
网格 · 迷宫 · O(V + E)
Dijkstra
当边权非负时使用。
优先队列 · O((V + E) log V)
Bellman-Ford
当允许负权,或需要检测负环时使用。
V−1 轮松弛 · O(V · E)
Floyd-Warshall
当需要全源距离、而不仅是单源时使用。
经中转点 DP · O(V³)