形式陈述

Bellman–Ford 初始化 $d[s]=0$、其余为 $+\mathrm{\infty }$，重复 $|V|-1$ 轮扫描所有边并松弛。归纳不变量是第 $i$ 轮后，$d[v]$ 不超过所有至多含 $i$ 条边的 $s⇝v$ 路径权重；若不存在可达负环，最短简单路径至多含 $|V|-1$ 条边，故最终正确。再扫描一轮若仍可改进，则存在从 $s$ 可达的负权环。邻接表实现时间 $O(|V||E|)$、空间 $O(|V|)$。

直觉

每一整轮允许最短路径信息再向前传播一条边。有限顶点图中的简单最短路边数有上限，额外改进只能来自可反复利用的负环。

例子与边界

边 $s\to a$ 权 2、$a\to b$ 权 -5 可在两轮内把 $b$ 更新为 -3。负环若从源不可达，不会影响源最短路，也不应由标准检测报告为相关负环，因为其端点距离仍为无穷。异步原地松弛可能一轮传播多条边，只会更快，不破坏上界；但提前停止需在整轮无更新时进行。算法检测的是可达负环，不直接恢复环，恢复需沿前驱回退。

推论与应用

Bellman–Ford 用于含负代价网络、距离向量路由和差分约束可行性，并作为最短路与负环判定的基本算法。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。