负权边与 Bellman–Ford（进阶）
复习
- Dijkstra 算法：每次确定距离最小的节点
- 图：带权图
- 松弛操作：用新信息更新距离
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 负权边会让 Dijkstra 的贪心判断失效
- Bellman–Ford 反复对所有边做松弛
- 最多做 V-1 轮就能得到最短距离
- 它还能顺便检测出负权环
正文
Dijkstra 很快，却怕负权边。可有些场景里，边权真的会是负的——比如“收益”“补贴”，走一条边反而让总代价减少。这时就要请出 Bellman–Ford 算法。
不再贪心，改成反复松弛
Bellman–Ford 放弃“确定”的思路，改用一种更朴素的策略：反复地对所有边做松弛。
松弛这个动作我们见过：如果“经过某条边”能让目标节点的距离变短，就更新它。Bellman–Ford 就是一轮一轮地把图上所有边都过一遍，让距离信息不断向远处传播、修正。
为什么做 V-1 轮就够
一张有 V 个节点的图，一条最短路径最多经过 V-1 条边（再多就会出现重复节点，也就是绕圈，而绕圈通常不会更短）。
每做完一轮对所有边的松弛，就相当于让“最短路径最多包含 k 条边”的信息传播出去。所以做完 V-1 轮，“最多 V-1 条边”的所有情况都考虑到了，最短距离也就确定了。
多出来的第 V 轮
既然 V-1 轮就够，那再做一轮会发生什么？
如果第 V 轮里还有节点的距离能被更新，那就说明：存在一条“经过 V 条边还能更短”的路径，也就是绕一圈回来反而更便宜。这只有在存在负权环时才可能——沿着这个环可以无限绕下去，距离无限变小，最短路径根本不存在。
所以，第 V 轮的用途，是检测负权环。发现它，就意味着“最短路”这个问题本身无解，需要特别处理。
代价换来了什么
Bellman–Ford 的代价是更慢：它要跑 V-1 轮，每轮扫所有边，复杂度 O(V·E)，比 Dijkstra 慢不少。
但换来的是能处理负权边，以及能检测负权环这两项能力。用更多时间，换更广的适用范围——又是一次同样的取舍。
思考题 1
为什么负权边会让 Dijkstra 出错，却难不倒 Bellman–Ford？
思考题 2
Bellman–Ford 为什么最多做 V-1 轮？多出来的第 V 轮有什么用？
小结
知识点
- 负权边使 Dijkstra 的贪心失效
- Bellman–Ford 反复对所有边做松弛
- V-1 轮即可确定最短距离
- 第 V 轮可检测负权环
参考资料
- Wikipedia(zh)：贝尔曼-福特算法：可处理负权边的单源最短路算法
- Wikipedia(zh)：最短路径问题：各类最短路算法概览
思考题答案（仅供参考）
思考题 1
Dijkstra 依赖“当前最小节点已确定”，而负权边会让绕远路反而更省，破坏这个前提。Bellman–Ford 不依赖这种贪心，而是反复松弛所有边，让信息一轮轮传播修正，因此能正确处理负权边。
思考题 2
因为任一最短路径最多含 V-1 条边，V-1 轮已覆盖所有情况。若第 V 轮仍有节点能被松弛，说明存在“绕一圈反而更短”的情况，即负权环，最短路不存在。所以第 V 轮用于检测负权环。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪