Bellman-Ford 与路由协议：负环、SPFA 与距离向量收敛
内容提要
Bellman-Ford 算法不仅比 Dijkstra 慢，还能通过松弛操作检测可达负权环并提取环，其递推式可分布式化为距离向量路由。RIP 使用水平分割、毒性逆转和度量值 16 防止环路，但三角环路仍会导致计数到无穷。Babel、EIGRP、BGP、OSPF 分别采用可行性条件、扩散计算、AS_PATH 和链路状态机制防环。文章还提供了 C 语言对拍与同步模拟复现。
延伸解读
负环检测的工程意义
负权环不仅是理论概念，在差分约束中代表不等式矛盾，在外汇图中代表套利机会，在最短路服务中代表请求无定义。文章强调检测到负环后还需提取环作为诊断证据，并注意只检测从源点可达的负环，不可达分量中的负环不影响结果。
SPFA 的适用边界
SPFA 通过队列优化减少无效扫描，在稀疏随机图上表现良好，但最坏复杂度仍为 O(nm)，可被对抗构造退化。文章指出它适合作为工程启发式，但不应替代最坏界清晰的 Bellman-Ford，尤其在输入可能被恶意构造的场景。
距离向量协议的防环策略对比
RIP 使用水平分割、毒性逆转和度量值 16 防环，但三角环路仍会导致计数到无穷。Babel 引入可行性条件和序列号，EIGRP 使用扩散计算，BGP 依赖 AS_PATH，OSPF 则采用链路状态机制。不同协议在环路控制与收敛速度上各有取舍。
复现实验的设计思路
文章通过 C 程序对拍 Floyd-Warshall 验证 Bellman-Ford 正确性，并用 Python 模拟距离向量收敛过程，关注轮数、松弛次数和消息数等与机器无关的指标。这种复现方式避免了墙钟基准的噪声，更贴合算法教学与协议行为分析。
Q&A
Bellman-Ford 算法如何检测并提取负权环？
在完成 n-1 轮松弛后，再进行第 n 轮松弛。如果仍存在边可以被松弛，则说明存在从源点可达的负权环。记录第 n 轮最后被更新的顶点 x，然后沿着前驱指针回溯 n 步，此时 x 必然位于某个负权环上；再从 x 出发沿前驱指针走直到遇到重复顶点，即可得到环。
SPFA 算法的最坏时间复杂度是多少？为什么它不能替代 Bellman-Ford？
SPFA 的最坏时间复杂度仍是 O(nm)。虽然它在许多稀疏、随机或实际变化不大的图上能减少无效扫描，但存在对抗性输入会使其退化，例如让顶点先以较差标签出队并扫描大量出边，再被更靠前的顶点改小标签、重新入队，如此重复 Θ(n) 层。因此 SPFA 适合作为工程启发式，但不能作为“平均很快所以总安全”的接口承诺，若输入可被对抗构造，应使用最坏界清晰的 Bellman-Ford。
RIP 协议如何防止路由环路？为什么三角环路仍会导致计数到无穷？
RIP 使用水平分割（split horizon）、毒性逆转（poisoned reverse）、触发更新和度量值 16 来防止环路。水平分割不把从某接口学来的路由原样从该接口发回；毒性逆转则把反向路由以 metric 16 发回。但 simple split horizon 只省略反向条目，两点回声要靠 timeout 失效；poisoned reverse 只保证两路由器环路立即破掉。对于三角环路，split horizon 只禁止把路由发回给自己的下一跳，但 A 仍能从 B 收到坏消息，B 仍能从 C 收到坏消息，C 仍能从 A 收到坏消息，因此坏消息会绕另一条边回来，导致计数到无穷，需要靠触发更新、超时和有限无穷收敛。
BGP、Babel、EIGRP 和 OSPF 分别采用什么机制防止路由环路？
BGP 是路径向量协议，通过 AS_PATH 属性防止 AS 级环路，路由器会检查 AS_PATH 中是否出现本地 AS 号，若出现则排除该路由。Babel 是改造过的距离向量协议，使用可行性条件（feasibility condition）和序列号来限制环路持续时间。EIGRP 基于距离向量技术，使用 DUAL 算法，通过可行后继（feasible successor）和扩散计算（Query/Reply）保证无环。OSPF 是链路状态协议，通过泛洪 LSA 同步链路状态数据库，然后本地运行 Dijkstra 计算最短路径树，坏消息不必逐跳猜测。
在工程中如何选择最短路径算法？有哪些常见坑？
非负权单源最短路首选 Dijkstra；有负边但无负环的单源最短路用 Bellman-Ford，小图可尝试 SPFA；有负边且全源稀疏图用 Johnson 算法（一次 BF 重赋权，再多次 Dijkstra）；差分约束可满足性加虚拟源点跑 BF 找负环。常见坑包括：把“有负边”误写成“有负环”；负环提取时未先回溯 n 步导致起点不在环内；用 SPFA 时只统计入队次数却忽略从源点不可达的负环；把 split horizon 当成完整防环方案，实际上三角环路仍会出问题。
Bellman-Ford 算法在距离向量路由中是如何体现的？
距离向量路由将 Bellman-Ford 的松弛式分布式化：每台路由器只知道邻居、链路代价和邻居发来的距离向量，通过 D_x(d) = min_{y∈N(x)} {c(x,y) + D_y(d)} 迭代更新到目的地的距离。好消息（更短路径出现）传播很快，沿路径逐跳降低距离即可；坏消息（路径失效）传播慢，旧信息可能绕一圈回到故障点，形成临时环，导致 count-to-infinity 问题。
负权环在实际应用中有哪些含义？
负权环的工程含义取决于模型：在差分约束中代表不等式矛盾；在外汇图中代表忽略手续费和滑点后的套利机会；在最短路服务中代表请求本身无定义。因此，仅返回布尔值通常不够，至少需要提取一条环作为诊断证据。
