Bellman-Ford 算法
Bellman-Ford 求加权有向图的单源最短距离，允许负边。算法反复扫描全部边，最多进行 V−1 轮松弛，再检查一轮：若仍能改进，就存在源点可达的负环，环上及环下游的顶点没有有限最短距离。
每轮至少保证把路径信息多传播一条边；边顺序合适时，一轮可以传播更多。若本轮后面的边降低了某个顶点距离，而该顶点的出边已经扫描过，下轮就要修正依赖旧值的结果。观察这种修正，比只记住“重复 V−1 次”更有用。
Dijkstra 通过确定最小距离来节省搜索，负边会破坏这个承诺。Bellman-Ford 在运行中不锁定任何距离，迟来的便宜路线仍可更新。Dijkstra 陷阱预设使用同一张会让 Dijkstra 出错的图，这里能得到正确结果。代价是最坏 O(V·E) 时间；非负边通常选 Dijkstra，需要负边支持或负环检测时再用本算法。
Bellman-Ford 如何工作
状态只有 dist 和 prev：前者记录目前最小成本，源点为 0，其余为 ∞；后者记录当前最优路径的前驱。没有优先队列，也没有已确定集合，边按声明顺序放在列表中。
一轮按顺序检查全部边。对 u → v、权重 w，若 u 不可达就跳过；否则比较 dist[u] + w < dist[v]，成立则更新距离和 prev[v] = u。多数检查可能不改变值。
没有可达负环时，最短路线可取简单路径，最多 V−1 条边。第 k 轮后，最多 k 条边的最短路线已得到正确传播，因此 V−1 轮足够。若整轮没有任何更新，后续检查的输入也不会改变，可以提前结束。
最后再扫一轮检测。简单路径的信息已传播完，若边仍可降低距离，就说明有可达负环。绕它一圈会减小成本，重复绕行使成本无下界。本实现返回 None 拒绝给出一组有限最短距离。源点不可达区域的负环检测不到，也不影响从该源点出发的答案；可达负环影响环上和下游顶点，不代表图中每个顶点都受影响。
Bellman-Ford 逐步演示
默认传播预设从 A 出发，有 A–E 五个顶点，每轮按此顺序检查六条边：A→B (4)、A→C (3)、B→D (3)、B→E (2)、C→B (−2)、D→E (2)。B 的出边排在改善 B 的边之前。
第 1 轮：
A→B：0+4=4 < ∞，B 为 4。A→C：0+3=3 < ∞，C 为 3。B→D：4+3=7 < ∞，D 为 7，依赖此时 B 的 4。B→E：4+2=6 < ∞，E 为 6，同样依赖旧 B。C→B：3+(−2)=1 < 4，B 降为 1。负边只是一次普通更新，但 D、E 已经用过旧值。D→E：7+2=9 ≥ 6，不变。本轮共更新五次。
第 2 轮：
A→B的 4 不小于 1，A→C的 3 等于 3，都不更新。B→D：1+3=4 < 7，D 降为 4。上一轮 B 的出边已经扫过，所以这次才修正。B→E：1+2=3 < 6，E 降为 3。C→B和D→E不更新。本轮共更新两次。
第 3 轮： 六条边都不更新，证明距离已稳定，跳过第 4 轮。
检测轮： 再查六条边，无改进，说明没有源点可达的负环。最终为 A=0, B=1, C=3, D=4, E=3。
画布运行中所有节点保持暂定的琥珀色，结束时五个节点一起变为确定状态。底部边列表固定，游标逐轮扫过，不按距离选择边。
负环预设中，B→C→D→B 的总权重为 −1，dist[B] 每轮下降一，各轮结束时依次为 0、−1、−2（第一轮先经 A→B 设为 1，同一轮内 D→B 又降到 0）。检测轮仍能改进，环变红，运行以无有限答案结束。红环沿算法的 prev 指针提取，不是手工标注。
时间与空间复杂度
| 情况 | 松弛扫描时间 | 辅助空间 |
|---|---|---|
| 最坏，完整 V−1 轮及检测 | O(V·E) | O(V) |
| 一轮传播后稳定并提前退出 | O(E) | O(V) |
每轮检查 E 条边，每次 O(1)。最好情况包含一轮有效传播、无更新确认轮和检测轮，仍为 O(E) 扫描；若计入全部顶点的初始化与输出，还应加 O(V)。dist、prev 占 O(V)，不需要队列。非负图中 Dijkstra 的 O((V+E) log V) 通常提供更好的最坏上界，但不能据此断言每个输入上的实际操作数都更少。
边界情况
- 负边正常参与松弛，前提是起点距离有限；不可达起点的边不能传播。
- 可达负环会使环上及下游距离无下界，需要检测并报告。
- 不可达顶点保持 ∞，从它出发的边一直跳过。
- 边顺序影响收敛轮数，不影响无可达负环时的最终距离。好顺序可能一轮传播完，差顺序可能需要 V−1 轮。
- 单节点无边：无需松弛，检测也为空，源点距离为 0。
常见错误
- 省略不可达检查。 浮点 ∞ 可能掩盖错误，整数哨兵
INT_MAX + w可能溢出。展示代码中的u in dist检查保证只延伸已有路径。 - 一轮后就确定距离。 默认 D 第一轮为 7，正确值是 4。全轮无更新才能证明已稳定。
- 过早判断负环。 V−1 轮之前的改进可能只是正常传播，不能由此推断负环。
- 轮数差一。 少于 V−1 轮可能漏掉最长简单路径的最后一跳；额外检测轮要与普通松弛轮区分。
- 非负图无需求也使用 Bellman-Ford。 它适合负边、负环检测，以及分布式路由等依靠反复松弛传播信息的场景。