Bellman-Ford 与路由协议：负环、SPFA 与距离向量收敛

Bellman-Ford 最容易被误读成“比 Dijkstra 慢、但能处理负边”的教材算法。这个说法漏掉了两个工程上更重要的点：第一，反复松弛给了它一个明确的失败信号——从源点可达的负权环；第二，同一个递推式可以在没有全局拓扑的网络里分布式运行，于是距离向量路由会继承它的收敛优点，也会暴露 count-to-infinity 这样的坏消息传播问题。

本文先讲集中式 Bellman-Ford 的不变式、提前停止和负环提取；再把松弛式改写成距离向量路由，逐条对照 RIP、Babel、EIGRP、BGP 与 OSPF 的规范；最后给出两个复现程序：bellman_ford_check.c 对拍 Floyd-Warshall，dv_sim.py 模拟 count-to-infinity 并重画本文的两张图。

一、问题、谱系与不变式

设有向图 \(G=(V,E)\)，\(n=|V|\)，\(m=|E|\)，边权 \(w:E\to\mathbb{R}\)，源点为 \(s\)。单源最短路要计算每个顶点 \(v\) 的

\[ \delta(s,v)=\min_{p:s\leadsto v}\sum_{e\in p}w(e), \]

前提是不存在从 \(s\) 可达且还能影响 \(v\) 的负权环；否则最短距离可以沿环无限下降，不是一个有限数。

Bellman-Ford 的历史比常见命名更分叉：Ford 的 RAND Paper P-923《Network Flow Theory》（1956）已经给出网络流和最短路背景下的松弛方法；Bellman 在 Quarterly of Applied Mathematics 16:87-90 的《On a routing problem》（1958）用动态规划方程表述路由问题；Moore 的《The shortest path through a maze》（1959）给出相近的逐层/队列式视角。因此文献中也常见 Bellman-Ford-Moore 的叫法。

核心操作只有一条边的松弛：

\[ \text{if } d[v] > d[u] + w(u,v),\quad d[v]\leftarrow d[u]+w(u,v),\quad \pi[v]\leftarrow u. \]

第 \(k\) 轮扫描完所有边后，标准不变式要写成两层：若从 \(s\) 到 \(v\) 存在一条至多 \(k\) 条边的路径，\(d[v]\) 不大于这些路径长度的最小值；同时，任何有限的 \(d[v]\) 始终等于某条从 \(s\) 到 \(v\) 的真实路径长度，因此它是最短距离的上界。不能说第 \(k\) 轮后“正好等于至多 \(k\) 边路径最小值”，因为同一轮内后面的边可以继续使用前面刚更新的距离。没有负权环时，一条简单最短路最多有 \(n-1\) 条边，所以 \(n-1\) 轮后收敛。若第 \(n\) 轮仍能松弛某条边，那么某条可达路径在超过 \(n-1\) 条边后还变短，路径中必含负权环。

提前停止只改变实际轮数，不改变最坏复杂度。某一轮没有任何松弛时，下一轮也不会再有松弛，可以立即返回；但有输入会让每轮只推进一小步，最坏仍是 \(O(nm)\) 次边检查。

二、负权环不仅要检测，还要提取

负权环的工程含义取决于模型：差分约束里代表不等式矛盾，外汇图里代表忽略手续费和滑点后的套利机会，最短路服务里代表请求本身无定义。只返回一个布尔值通常不够，至少要能拿到一条环作为诊断证据。

提取方法是 Bellman-Ford 的一个小技巧。第 \(n\) 轮记录最后被更新的顶点 \(x\)，沿前驱指针走 \(n\) 步，必然进入某个负权环；再从这个点沿前驱走到重复即可得到环。本文的 C 程序在例图上输出 2->3->1->2，对应权重 \(-1-1-1=-3\)。

需要注意两个边界：

• 只检测从源点可达的负权环。不可达分量里的负环不会影响从 \(s\) 出发的最短路。
• 若要标记所有距离无下界的顶点，应先找出第 \(n\) 轮能被松弛的顶点集合，再沿原图正向搜索；这些点以及它们可达的点都没有有限最短距离。

下面是可运行实现里的核心片段（完整代码见 reproduce/bellman_ford_check.c）：

for (int r = 1; r <= n - 1; r++) {
    int changed = 0;
    for (int i = 0; i < m; i++) {
        if (dist[e[i].u] != INF && dist[e[i].u] + e[i].w < dist[e[i].v]) {
            dist[e[i].v] = dist[e[i].u] + e[i].w;
            pred[e[i].v] = e[i].u;
            changed = 1;
        }
    }
    if (!changed) break;
}

int x = -1;
for (int i = 0; i < m; i++) {
    if (dist[e[i].u] != INF && dist[e[i].u] + e[i].w < dist[e[i].v]) {
        pred[e[i].v] = e[i].u;
        x = e[i].v;
    }
}
if (x >= 0) {
    for (int i = 0; i < n; i++) x = pred[x];
    /* x is now on a reachable negative cycle. */
}

整数实现要防溢出：INF 不能取 LLONG_MAX 后直接参与加法；本文程序用 long long 和足够小的哨兵，并在 dist[u] != INF 后才加边权。

三、SPFA、Yen 改进与负权最短路前沿

SPFA（Shortest Path Faster Algorithm）把“每轮扫所有边”换成“只处理距离刚变小的顶点的出边”：顶点 \(u\) 的距离被改小后入队，出队时松弛所有出边。段凡丁 1994 年发表于《西南交通大学学报》的《关于最短路径的 SPFA 快速算法》使这个名字在中文语境里流行；队列式松弛思想本身可追溯到 Moore 等更早工作。

SPFA 的优点是能在许多稀疏、随机、实际变化不大的图上少做大量无效扫描；缺点是最坏复杂度仍为 \(O(nm)\)。这个界不是只来自“大 O 保守估计”：Ahuja、Magnanti、Orlin 的《Network Flows》（1993）按 label-correcting 框架给出 \(O(nm)\) 界；Cherkassky、Goldberg、Radzik（Mathematical Programming, 1996）专门比较各种队列规则，并把 FIFO 队列放在会退化的 label-correcting 家族里。直观的对抗思路是让顶点先以较差标签出队并扫描大量出边，再被更靠前的顶点改小标签、重新入队，如此重复 \(\Theta(n)\) 层。它适合作为工程启发式，不适合作为“平均很快所以总安全”的接口承诺。SLF（Small Label First）和 LLL（Large Label Last）等队列策略能改善一些输入上的常数，不改变最坏界。

Yen 在 1970 年给出 Bellman-Ford 的扫描顺序改进：先给顶点一个线性序，把边分为正向边和反向边；每轮按正序松弛正向边、按逆序松弛反向边。这个非自适应版本把保证轮数从 \(n-1\) 降到 \(\lceil n/2\rceil\)，但每轮仍接触所有边，渐进复杂度仍是 \(O(nm)\)。

负权单源最短路长期被 Bellman-Ford 的 \(O(nm)\) 界统治，但不是没有后续进展：

这张表不是选型建议。生产代码里，若权重非负，Dijkstra 仍是首选；若只有少量负边且要求全源最短路，Johnson 重赋权把一次 Bellman-Ford 和多次 Dijkstra 组合起来更常见；若输入可被对抗构造，SPFA 不能替代最坏界清晰的 Bellman-Ford。

四、从松弛式到距离向量路由

集中式 Bellman-Ford 的松弛式是

\[ d[v] = \min_{(u,v)\in E}\{d[u] + w(u,v)\}. \]

距离向量路由把方向换成“我到目的地 \(d\) 的距离由邻居通告决定”：

\[ D_x(d)=\min_{y\in N(x)}\{c(x,y)+D_y(d)\}. \]

每台路由器只知道邻居、链路代价和邻居发来的距离向量，不需要全局拓扑，也没有 OSPF 那样的统一链路状态数据库。好消息传播很快：某条更短路径出现时，沿路径逐跳降低距离即可。坏消息传播慢：某条路径失效后，旧信息可能绕一圈又回到故障点，形成临时环。

RIP v2（RFC 2453）是经典距离向量协议，关键参数都能在规范里找到：

“RIP 的无穷是 16”不是随手取的小常数，而是用有限上界换收敛保证：当错误距离一路增加到 16，路由就被认定不可达。代价也很明显，RIP 不适合直径超过 15 跳的网络。

五、count-to-infinity：两点能修，三角仍会坏

最小例子是 A–B–C，目的地为 A。A-B 断开后，B 先把到 A 的距离设为 16；但 C 还保留“经 B 到 A，距离 2”的旧消息。若 B 采信 C，就得到距离 3；下一轮 C 又采信 B，变成 4；如此直到 16。这不是负权环，而是分布式系统中旧状态绕路返回。

reproduce/dv_sim.py 用同步轮次模拟这个过程，metric 上限固定为 RIP 的 16。下图的纵轴是系统中最大的通告 metric：

复现结果如下：

simple split horizon 不是主动毒化：它只是省略从某邻居学来的反向路由。两节点例子里，B 和 C 都收不到对方关于该目的地的条目，错误路由要等 6 个 30 秒周期、也就是 RFC 2453 Section 3.8 的 180 秒 timeout 后才失效；poisoned reverse 才会把反向路由以 metric 16 发回去，一轮打断两路由器环。三角例子是：A、B、C 形成环，故障后暂态 next-hop 为 \(A\to B\)、\(B\to C\)、\(C\to A\)。split horizon 只禁止“把路由发回给自己的下一跳”，但 A 仍能从 B 收到坏消息，B 仍能从 C 收到坏消息，C 仍能从 A 收到坏消息；poisoned reverse 也只保证两路由器环路立即破掉。RFC 2453 Section 3.4.3 明确说 poisoned reverse 会防止只涉及两个网关的环路，三节点及以上环路仍需要靠触发更新、超时和有限无穷收敛。

六、BGP、Babel、EIGRP 与 OSPF：四种防环路线

距离向量不是所有路由协议的共同祖先。几个常见协议对“没有全局视图时如何防环”给了不同答案。

BGP 是路径向量，不是 Bellman-Ford。 RFC 4271 摘要和 Section 1 说明，BGP 交换的是网络可达信息以及这条信息穿过的 AS 列表；Section 5.1.2 定义 AS_PATH，Section 9.1.2 要求 AS loop 检测扫描完整 AS path，若其中出现本地 AS 号，该路由应从 Phase 2 决策中排除。它仍会选择路径、执行策略和聚合，但不要把 BGP 简化成“跑 Bellman-Ford 的互联网版”。

Babel 是改造过的距离向量。 RFC 8966 Section 2.2 直接把 Babel 的概念算法写成 Bellman-Ford；Section 2.3 展示临时环和 count-to-infinity；Section 2.5 解释用序列号解决 starvation；Section 3.5.1 在路由维护规则中细化可行性条件（feasibility condition）和序关系，决定哪些通告可被接受。Babel 的目标不是永远选择瞬时最短路，而是在移动和无线网络里限制环路持续时间，再慢慢收敛到最优。

EIGRP/DUAL 用扩散计算保证无环。 RFC 7868 说明 EIGRP 基于距离向量技术，具体算法是 DUAL；Section 3.3 写 feasibility condition，Section 3.4 写 Update、Query、Reply 等消息。Garcia-Luna-Aceves 的 IEEE/ACM Transactions on Networking 1993 论文《Loop-Free Routing Using Diffusing Computations》给出这类算法的理论基础：当本地没有可行后继（feasible successor）时，路由器发起扩散查询，等依赖范围内的回复回来再切换，避免瞬时环。

OSPF 是链路状态。 RFC 2328 摘要说每台 OSPF 路由器维护描述 AS 拓扑的链路状态数据库，并从该数据库计算最短路径树；Section 2.2 与 Section 16.1 描述 shortest-path tree 计算。它的典型实现使用 Dijkstra，而不是分布式 Bellman-Ford。链路状态的代价是泛洪 LSAs、维护一致数据库和处理区域；收益是坏消息不必逐跳猜测，拓扑变化后可以重新计算全局最短路径树。

七、复现实验：C 对拍与同步距离向量模拟

本文不写墙钟 benchmark，因为这篇的关键不是“谁快几毫秒”，而是轮数、松弛次数、消息数这类与机器负载无关的指标。复现环境如下：

• OS：Linux 6.6.87.2-microsoft-standard-WSL2。
• CPU：Intel Core i9-12900K；复跑命令使用 taskset -c 10。
• 编译器：GCC 16.1.1，参数 -O2 -Wall -Wextra；另用 -fsanitize=address,undefined 跑一遍。
• Python：python3，验证环境版本 3.14.5；dv_sim.py 只用标准库生成 SVG。

运行命令：

cd post/algorithms/44-bellman-ford-routing/reproduce
gcc -O2 -Wall -Wextra -o bellman_ford_check bellman_ford_check.c
taskset -c 10 ./bellman_ford_check > bf-results.txt
gcc -O1 -g -fsanitize=address,undefined -Wall -Wextra -o bellman_ford_check_asan bellman_ford_check.c
taskset -c 10 ./bellman_ford_check_asan > bf-asan-results.txt
rm -f bellman_ford_check bellman_ford_check_asan
taskset -c 10 python3 dv_sim.py > dv-run.txt

bf-results.txt 的输出：

clrs_sample rounds=4 attempts=40 relaxes=7 neg=0 dist= 0 2 4 7 -2
negative_cycle rounds=4 attempts=20 relaxes=17 neg=1 cycle=2->3->1->2
fuzz_ok cases=2000 max_n=8 oracle=floyd_warshall

第一行是 CLRS 常用的 5 点 10 边样例，4 轮、40 次边检查、7 次成功松弛后提前停止，距离为 \(0,2,4,7,-2\)。第二行是本文负环图，提取到 2->3->1->2。第三行用固定随机种子生成 2000 个 \(n\le 8\) 的小图；若 Floyd-Warshall 判断源点可达负环，Bellman-Ford 必须也报告负环；否则每个顶点距离必须逐项相等。

dv-results.csv 的输出与第五节表格一致：

case,policy,rounds_to_inf,messages
chain_none,none,14,28
chain_split,split,6,12
chain_poison,poison,1,2
triangle_split,split,14,84
triangle_poison,poison,14,84

这两个程序分别覆盖本文两类结论：集中式算法的正确性由小图 oracle 对拍；距离向量的收敛轮数由明确状态机模拟。图 negative-cycle.svg 与 count-to-infinity.svg 都由 dv_sim.py 生成，避免手画数值与正文不一致。

八、工程选型与常见坑

常见实现错误有四类。

第一，把“有负边”误写成“有负环”。负边本身不破坏最短路定义，负环才会让距离无下界。

第二，负环提取只从第 \(n\) 轮的更新点直接打印前驱链。若不先回溯 \(n\) 步，起点可能在通往环的尾巴上，不在环内。

第三，用 SPFA 时只统计入队次数，却忘了“从源点不可达的负环不该被报告”。入队计数法只对从源点传播到的顶点有效；全图负环检测需要加虚拟源点或逐分量处理。

第四，把 split horizon 当成完整防环方案。simple split horizon 只省略反向条目，两点回声要靠 timeout 失效；poisoned reverse 才会主动发 metric 16 打断两点环。三角环路仍会让坏消息绕另一条边回来，RIP 的 metric 16 是最后保险，不是优化。

九、参考资料

规范与文档

• G. Malkin, RFC 2453, RIP Version 2, 1998：Section 3.1、3.2、3.4.3、3.4.4、3.8、3.10.1、3.10.2。
• Y. Rekhter, T. Li, S. Hares, RFC 4271, A Border Gateway Protocol 4 (BGP-4), 2006：摘要、Section 1、5.1.2、9.1.2。
• J. Chroboczek, D. Schinazi, RFC 8966, The Babel Routing Protocol, 2021：Section 1.1、2.2、2.3、2.5、3.5.1。
• D. Savage et al., RFC 7868, Cisco’s Enhanced Interior Gateway Routing Protocol (EIGRP), 2016：Section 3.1、3.3、3.4。
• J. Moy, RFC 2328, OSPF Version 2, 1998：摘要、Section 2.2、16.1。

核心论文

• Lester R. Ford Jr., Network Flow Theory, RAND Corporation Paper P-923, 1956。
• Richard Bellman, “On a routing problem,” Quarterly of Applied Mathematics, 16:87-90, 1958。
• Edward F. Moore, “The shortest path through a maze,” Proceedings of the International Symposium on the Theory of Switching, Part II, Harvard University Press, 1959, pp. 285-292。
• 段凡丁，《关于最短路径的SPFA快速算法》，《西南交通大学学报》，1994 年第 2 期，207-212 页。
• Jin Y. Yen, “An algorithm for finding shortest routes from all source nodes to a given destination in general networks,” Quarterly of Applied Mathematics, 27(4), 1970。
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993。
• Boris V. Cherkassky, Andrew V. Goldberg, Tomasz Radzik, “Shortest paths algorithms: Theory and experimental evaluation,” Mathematical Programming, 73, 1996。
• Andrew V. Goldberg, “Scaling algorithms for the shortest paths problem,” SIAM Journal on Computing, 24(3), 1995。
• Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen, “Negative-Weight Single-Source Shortest Paths in Near-linear Time,” FOCS 2022；FOCS 2022 best paper。
• Jeremy T. Fineman, “Single-Source Shortest Paths with Negative Real Weights in \(\tilde O(mn^{8/9})\) Time,” STOC 2024。
• J. J. Garcia-Luna-Aceves, “Loop-Free Routing Using Diffusing Computations,” IEEE/ACM Transactions on Networking, 1(1):130-141, 1993。

实验

• reproduce/bellman_ford_check.c：Bellman-Ford、提前停止、负环提取、Floyd-Warshall 对拍。
• reproduce/dv_sim.py：count-to-infinity 同步轮次模拟，生成 count-to-infinity.svg 与 negative-cycle.svg。
• reproduce/bf-results.txt、reproduce/bf-asan-results.txt、reproduce/dv-results.csv：本文引用的复现输出。

上一篇：Dijkstra 与 A*：非负权、启发式与工程优先队列 下一篇：最小生成树：割性质、Kruskal/Prim/Borůvka 与线性时间开放问题

相关阅读：

• 路由算法：距离向量 vs 链路状态 vs 路径向量
• Dijkstra 与 A*：非负权、启发式与工程优先队列