Bellman–Ford 算法 | Codeboy's Blog

形式陈述

在最短路问题的有限有向实权模型 $D=(V,A)$ 中，Bellman–Ford 给定源点 $s$ ，初始化 $d[s]=0$ 、其余 $d[v]=+\infty$ ，然后进行 $|V|-1$ 轮；每轮按固定但任意的次序对所有弧执行原地松弛

d[v]\leftarrow\min\bigl(d[v],\ d[u]+w(u,v)\bigr),

并在严格改进时记录前驱 $\pi[v]=u$ 。实现必须跳过 $d[u]=+\infty$ 的弧，否则用有限机器哨兵表示无穷时可能发生溢出或伪造可达性。

轮次证明先采用双数组同步版本：第 $i$ 轮只读 $d_{i-1}$ 并写入

d_i(v)=\min\!\left\{d_{i-1}(v), \min_{(u,v)\in A}\bigl(d_{i-1}(u)+w(u,v)\bigr)\right\}.

归纳可得： $d_i(v)$ 恰好是所有至多含 $i$ 条弧的 $s\leadsto v$ 游走的最小权重。最优游走要么已经使用至多 $i-1$ 条弧，要么最后一条是某个 $(u,v)$ ，两项正好对应递推的两个分支。这是按允许弧数分层的动态规划。

标准单数组实现会立即使用本轮刚得到的改进，可能顺着扫描次序一次传播多条弧。令其第 $i$ 轮结束值为 $\widetilde d_i$ ，只能保证 $\widetilde d_i(v)\le d_i(v)$ ；另一方面，每个有限估计仍由某条真实游走见证，所以在最短距离有限时有 $\widetilde d_i(v)\ge\delta(s,v)$ 。同步不变量不能原样声称为单数组版本的等式，但它仍给出单数组算法的收敛上界。

若从 $s$ 可达的区域没有负权有向圈，每个有限最短距离都由至多 $|V|-1$ 条弧的简单路达到。因此同步版本在 $|V|-1$ 轮得到 $\delta$ ，单数组版本夹在 $\delta$ 与同步值之间，也得到同一答案。随后再完整扫描一轮：若存在可松弛弧，则有一条从 $s$ 可达的负圈；若没有，所有可达顶点的有限距离均已稳定。检测不到与 $s$ 不连通的负圈，这是单源问题的预期语义。

设 $n=|V|$ 、 $m=|A|$ 。输入以边列表或邻接表支持一轮 $\Theta(m)$ 顺序扫描，并假设精确加法、比较为单位成本时，确定性最坏时间为 $\Theta(nm)$ ，距离、前驱与两份同步数组至多占 $O(n)$ 辅助空间；原地版只需一份距离数组。某轮完全无更新即可提前停止，但最坏界不变。若权重是任意精度整数或有理数，还应把算术位复杂度计入，不能只数松弛次数。

直觉

同步版本第 $i$ 轮回答“最多走 $i$ 条弧能有多便宜”。原地扫描保留这条进度保证，却可能沿当前边序一次跨过多步；所以轮号是最坏进度下界，不再精确等于已传播的路径长度。只要一条最短路还没有完整传播，每一整轮至少会把正确前缀向前推进一条弧。

与Dijkstra 算法不同，Bellman–Ford 从不永久结算某个顶点。负边可能让后来到达的长前缀反而更便宜，反复扫描正是允许这种信息回传的机制。经过足够多轮仍能下降时，简单路的 $n-1$ 条弧上限已耗尽，额外改进只能借助重复顶点；其中必有负权圈。

Bellman–Ford 的第 k 轮松弛与额外轮负环证据 — Bellman–Ford 松弛与负环检测

例子与边界

设边 $s\to a$ 权 $2$ 、 $a\to b$ 权 $-5$ 、 $s\to b$ 权 $4$ 。若一轮按 $s\to a,a\to b,s\to b$ 扫描，第一轮就得到 $(d[a],d[b])=(2,-3)$ ；若先扫 $a\to b$ ，第一轮结束为 $(2,4)$ ，第二轮才把 $b$ 降到 $-3$ 。边序影响到达稳定值的轮数，不影响 $n-1$ 轮后的答案，因此“整轮无更新即提前停止”是安全的。

负边与负圈承担不同语义：前者只要求标签允许回改，后者让一部分距离根本没有有限最小值。想恢复负圈，可在第 $n$ 轮记录任一被松弛顶点 $x$ ，沿前驱回退 $n$ 次以进入前驱圈，再走到顶点重复为止。若要标记所有距离为 $-\infty$ 的顶点，应收集第 $n$ 轮仍可改进的顶点，并从它们沿出弧做可达性搜索；只把圈上顶点标负无穷会漏掉圈的后继。

负环检测可以用一个完整的小图看清。设有边

s\to a:0, \qquad a\to b:1, \qquad b\to a:-3, \qquad b\to c:2.

环 $a\to b\to a$ 的总权为 $-2$ ，且从 $s$ 可达；每绕一圈， $a,b$ 的估计再降 $2$ 。顶点 $c$ 不在圈上，却可由圈到达，所以 $\delta(s,c)=-\infty$ 。另一个与 $s$ 不连通的负圈端点始终为 $+\infty$ ，不会触发本次单源检测。平行弧只需逐条松弛；自环若权为负，会在可达时立即成为负圈证书。

推论与应用

Bellman–Ford 还能判断差分约束可行性：不等式 $x_v-x_u\le c$ 对应弧 $u\to v$ 、权 $c$ ，负圈恰是矛盾证书。距离向量路由把松弛分散到相邻路由器，但异步消息、失效传播与 count-to-infinity 需要额外协议分析，不能直接沿用集中式 $\Theta(nm)$ 界。

Johnson 全源最短路用 Bellman–Ford 生成可行势并检测全图负圈，再在非负重赋权图上逐源运行 Dijkstra。Floyd–Warshall则按允许的中间顶点做稠密矩阵动态规划；二者的输入表示和复杂度优势区间不同。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§22.1, Bellman–Ford and negative-weight cycles。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§6.8, shortest paths with negative edge costs。
Richard Bellman, “On a Routing Problem,” Quarterly of Applied Mathematics 16(1), 1958, pp. 87–90。

形式陈述 ​

反向链接

形式陈述