贝尔曼-福特算法

Richard Bellman（动态规划的奠基人）在 1958 年的论文《On a Routing Problem》中、Lester Ford Jr.（最大流-最小割定理的共同提出者，他与 Fulkerson 的最大流论文发表于 1956 年）在更早的 RAND 报告中，分别给出了处理含负权边图的最短路径算法。Alfonso Shimbel 在 1955 年也独立发现了相似方法。

Dijkstra 算法无法处理负权边——这不是实现的缺陷，而是贪心策略在负权下理论上就会失败。Bellman-Ford 通过动态规划，绕过了这一限制。更重要的是，它能检测负权环（Negative Weight Cycle）——一个路径绕一圈就能让总代价无限减少的环，使"最短路径"变得无意义。

Dijkstra 为何无法处理负权边#

Dijkstra 的核心假设：一旦某节点的最短距离被确定（取出优先队列），就永远不需要更新。这依赖于"非负边权保证：从已确定节点出发的路径，距离只会增大"。若存在负权边，已"确定"的节点可能通过后续的负权边获得更短路径，导致 Dijkstra 给出错误答案。

例：S → A (权重5)，S → B (权重2)，B → A (权重-4)
实际 S → A 最短路：S→B→A = 2 + (-4) = -2
Dijkstra 先确定 B(2)，再确定 A(5)，错误！（A 的真实最短距离是 -2）
```

Bellman-Ford 核心思想#

关键观察：若图有 $V$ 个节点，不含负权环，则最短路径上最多经过 $V-1$ 条边（路径不重复访问节点，否则去掉环更短）。

动态规划状态：$d_k(v)$ = 从源点 $s$ 出发，经过最多 $k$ 条边到达 $v$ 的最短距离。

递推：

$$d_k(v) = \min\left(d_{k-1}(v),\ \min_{(u,v) \in E}\left(d_{k-1}(u) + w(u, v)\right)\right)$$

初始：$d_0(s) = 0$，$d_0(v) = \infty$（$v \neq s$）。迭代 $V-1$ 次即可得到所有最短路径。

等价算法描述（更常用的实现）：

def bellman_ford(graph, source, V, E):
    dist = {v: float('inf') for v in graph.nodes}
    dist[source] = 0

for _ in range(V - 1): for (u, v, w) in E: # 松弛每条边 if dist[u] + w < dist[v]: dist[v] = dist[u] + w

检测负权环 for (u, v, w) in E: if dist[u] + w < dist[v]: return "存在负权环"#

return dist ```

时间复杂度：$O(VE)$（$V-1$ 轮，每轮松弛所有 $E$ 条边）。比 Dijkstra 的 $O((V+E) \log V)$ 慢，但能处理负权边，且检测负权环。

手算一遍：5 节点带负权图的逐轮松弛#

下面这张图有 5 个节点、10 条边，其中两条是负权。源点是 $s$。

先手工找出答案，再让算法去撞它。$s$ 到各点的真正最短路：

• $y$：只有 $s \to y = 7$ 一条（另一条 $s\to t\to y$ 要 $6+8=14$）。7
• $x$：$s \to y \to x = 7 - 3 = 4$。4
• $t$：$s \to y \to x \to t = 7 - 3 - 2 = 2$，比直连的 6 更短。2
• $z$：$s \to y \to x \to t \to z = 2 - 4 = -2$。−2

注意 $t$ 的最短路要走 3 条边，$z$ 的要走 4 条边——这就是为什么单轮松弛不够。

约定边的松弛顺序为上表的字典序：$s\!\to\!t$、$s\!\to\!y$、$t\!\to\!x$、$t\!\to\!y$、$t\!\to\!z$、$x\!\to\!t$、$y\!\to\!x$、$y\!\to\!z$、$z\!\to\!s$、$z\!\to\!x$。逐轮结果：

这张表最该注意的是第 1 轮那一行的括号：$x$ 先被松弛到 11，同一轮里又被 $y\!\to\!x$ 压到 4。同一轮内后面的边能立刻用上前面刚更新的值——这是教科书递推式 $d_k$ 与实际代码的一个重要差别。递推式里 $d_k$ 只读 $d_{k-1}$，代码里 dist 是原地更新的，所以第 $k$ 轮结束时 $dist[v]$ 往往比 $d_k(v)$ 更小。这不影响正确性（$dist[v]$ 永远是某条真实路径的长度，只会更好），却让"需要几轮"变成一个依赖顺序的问题——下一节就是这件事。

第 2、3 轮各只成功松弛一条边：信息像水一样一格一格往下渗，$t$ 变小之后 $z$ 才能变小。第 4 轮一无所获，此时其实已经可以提前退出（early termination），这是实现里最值得加的一行判断。

边的顺序决定收敛快慢#

$V-1$ 轮是上界，不是必然。把上面的图换成最简单的一条链就能看清两个极端。

节点 $1 \to 2 \to 3 \to 4 \to 5$，每条边权重 1，源点是 1。真实答案：$0,1,2,3,4$。

顺序 A：$(1{,}2), (2{,}3), (3{,}4), (4{,}5)$

一轮搞定。因为每条边被松弛时，它的起点刚好在同一轮里已经拿到了最终值。

顺序 B：$(4{,}5), (3{,}4), (2{,}3), (1{,}2)$（完全倒过来）

整整 4 轮，也就是 $V-1$ 轮，一轮都省不掉。每轮只有最后被扫到的那条边能生效，前面三条边的起点还是 ∞。

同一张图、同一个算法，只是边表的排列不同，工作量差了 4 倍。这同时也证明了 $V-1$ 这个界是紧的：存在输入使它必须跑满。把链拉长到 $V$ 个节点，倒序边表就需要 $V-1$ 轮。

该记住的判断：Bellman-Ford 的实际开销由"信息沿最长最短路传播需要几轮"决定，而这取决于边表顺序与最短路径树的形状是否对齐。下一节的 SPFA 正是试图自动对齐它——它把"该松弛哪条边"交给队列，而不是交给静态的边表顺序。

负权环检测#

第 $V$ 轮（额外再做一次）松弛：若仍有边能被松弛，说明从源点可达某负权环。在 $V-1$ 条边已能覆盖所有最短路的情况下，第 $V$ 次仍能松弛，意味着路径还在"缩短"，必然有负权环。

在上面那张 5 节点图上造一个环。只改一个数：把 $t \to y$ 的权重从 8 降到 1。现在 $t \to y \to x \to t = 1 + (-3) + (-2) = -4 < 0$，一个三节点负权环出现了。同样的边序，逐轮结果变成：

每绕环一圈，环上三个点的距离就各降 4，永无止境。第 $V$ 轮抓到的就是这种"停不下来"。

一个容易踩的实现陷阱：这个检测只发现"从源点可达的"负权环。图里另有一个与 $s$ 不连通的负权环，上述代码一无所知。想找出全图所有负权环，标准做法是加一个虚拟源点，向每个节点连一条权重 0 的边，再跑一次。

现场：套利检测里的负权环#

负权环最广为人知的落地是货币套利。把乘法变成加法这一步是整个转换的关键：汇率沿路径是相乘的，而最短路算法只会相加，所以取对数——

$$w(i \to j) = -\ln(\text{汇率}_{i \to j})$$

于是一条环路上权重之和为负，等价于汇率之积大于 1，也就是"绕一圈回来钱变多了"：

$$\sum -\ln r_k < 0 \iff \prod r_k > 1$$

拟一组汇率算一遍（下面的数字是为了演算而设，不是真实报价）：

权重和 $0.1054 - 5.1059 + 4.9908 = -0.0097 < 0$，Bellman-Ford 的第 $V$ 轮会抓到它。回推收益：$e^{0.0097} = 1.0098$——1 美元绕一圈变成 1.0098 美元，0.98% 的无风险收益。

但这里有一层教科书通常不讲的现实：0.98% 在真实市场上大概率不是套利机会，而是没算交易成本。每一次兑换都有买卖价差（bid-ask spread）和手续费，正确的建模应把它们并入边权：

$$w(i \to j) = -\ln\!\big(r_{i\to j} \cdot (1 - \text{fee})\big)$$

三次兑换、每次 0.4% 的成本，就吃掉 $-3\ln(0.996) \approx 0.0120$ 的权重——比上面那 $0.0097$ 还多，环立刻变成正的。所以真实的套利检测里，"环是负的"只是必要条件；能不能落袋，取决于负得比成本更深，以及负权环消失之前你能不能把三笔交易全部成交。这也是为什么这类系统的瓶颈从来不是 Bellman-Ford，而是延迟。

同一套建模换个场景就是另一类问题：程序分析里的循环依赖、结算网络里的债务闭环、任务调度里的约束不可满足，都是同一个"负权环"在不同领域的名字。

优化：SPFA（Shortest Path Faster Algorithm）#

Bellman-Ford 每轮对所有边松弛，但很多边可能没有"激活"（其起点距离未更新），做无用功。

SPFA：用队列维护"距离刚被更新的节点"，只有这些节点的出边才需要松弛。该算法本质上由 Edward F. Moore 于 1959 年首先发表；1994 年，中国研究者段凡丁在《西南交通大学学报》重新发现并推广了此方法，"SPFA"之名由此在中文算法竞赛社区流行：

queue = [source]
in_queue = {source: True}

while queue: u = queue.pop(0) in_queue[u] = False for (u, v, w) in edges_from[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w if not in_queue[v]: queue.append(v) in_queue[v] = True ```

它为什么能被卡掉#

SPFA 的开销可以精确写成：每次出队都要扫一遍该点的出边，所以总工作量 = \sum_v (\text{v$ 的出队次数}) \times \deg^+(v)$。

而一个节点每被压小一次距离，就要重新入队一次。如果攻击者能让每个点的距离被压小 $\Theta(V)$ 次，总量就回到 $O(VE)$——和朴素 Bellman-Ford 一样，还多背了队列的常数。

关键在于级联：$v$ 的距离每变小一次，$v$ 的所有后继都要重算，后继的后继也要重算。中文竞赛社区常用两类构造来触发这种级联：

• 网格图：把节点排成 $k \times k$ 网格，只保留向右和向下的边，权重安排成"跳数少的路反而更长"。BFS 式的队列会先送来跳数少的坏消息，之后一轮轮被更长但更优的路径推翻，每个格点被反复压小，改进沿网格向右下持续扩散。
• 菊花图：一个中心点连出大量叶子，再把若干这样的团串起来。中心点每被压小一次，就要把改进推给全部叶子，出边多带来的代价被出队次数乘上一遍。

两种常见改良——SLF（Small Label First，队首优先放距离小的）与 LLL（Large Label Last，把大于平均值的节点丢回队尾）——都只是抬高了构造门槛，没有改变最坏复杂度，也都有对应的针对性数据。

所以"SPFA 已死（SPFA is Dead）"这句在中国算法竞赛圈流传的话，说的是一件很具体的事：出题人只要放一张网格图，SPFA 就退化成带常数惩罚的 Bellman-Ford。现在的建议很干脆——无负权边就用 Dijkstra + 堆（有确定的 $O((V+E)\log V)$ 保证），有负权边就用带提前退出的标准 Bellman-Ford（有确定的 $O(VE)$ 上界）。SPFA 的价值是"平均情况很快"，而竞赛与生产环境要的都是"最坏情况可控"。

实际应用：RIP 网络路由协议#

Bellman-Ford 的分布式版本是互联网早期路由信息协议（RIP，Routing Information Protocol）的核心算法。每个路由器只知道邻居报来的距离，通过与邻居交换距离向量（Distance Vector）逐步收敛——本质上就是把"松弛"这个操作分散到各台机器上异步执行。

分布式带来一个集中式版本没有的病症。收敛问题——"计数到无穷（Count to Infinity）"：链路断开时，节点会相互"误导"，让距离信息一格一格地往上爬。

拿一条三跳的链看清楚：网络 net1 直连在 R1 上，R2 从 R1 学到 net1，R3 从 R2 学到。RIP 里直连网络的度量值是 1。

这张表最该注意的是第 4 行那个 4：R2 采纳的不是错误信息，R3 报的"3"在故障前完全正确——R3 只是不知道它那条路径正好穿过 R2 自己。距离向量协议的根本缺陷不是消息会丢，而是消息里不带路径，收方无法判断这条路是否绕回了自己。

这就解释了协议里那个看起来很随意的数字。RIP 把 16 定义为无穷、可用跳数上限 15（RFC 2453），理由在 RFC 1058 里说得很明确：无穷必须大到没有真实路由能达到，但不能比必要的更大——因为它同时是"计数到无穷"要爬多少级的上限。度量从 4 爬到 16 需要 12 次通告，而 RIP 的默认更新周期是 30 秒（超时 180 秒、垃圾回收 120 秒），也就是分钟量级的收敛时间。把无穷设成 256，网络能大一些，但一次链路故障可以让路由表烂上一小时。15 跳这个上限不是能力不足，是一个刻意的成本折中。

RIP 的缓解手段也都是在打这个补丁：水平分割（split horizon）不把路由通告回学到它的那个接口，毒性逆转（poison reverse）索性把度量 16 通告回去，触发更新（triggered update）不等 30 秒立刻发坏消息。前两者能杀死两节点之间的环，但对三个及以上路由器构成的环无效——上面那张表就是一个三节点的例子。

现代网络因此转向 OSPF（Open Shortest Path First）这类链路状态协议：每台路由器拿到全网拓扑，各自在本地跑 Dijkstra。代价是每台机器都要存全图、洪泛拓扑变更；换来的是没有 count-to-infinity——因为信息里带着完整的图，而不只是一个数字。

Bellman-Ford 与动态规划#

Bellman-Ford 是动态规划的典型应用：

• 子问题：$d_k(v)$ = "最多 $k$ 步到 $v$ 的最短路"
• 最优子结构：若 $P$ 是最短路，$P$ 的任何子路也是对应节点间的最短路
• 无后效性：$d_k$ 只依赖 $d_{k-1}$（单向依赖，无环）
• 表格遍历：从 $k=0$ 到 $k=V-1$ 填表

Richard Bellman 在 1958 年的论文标题就是"On a Routing Problem"，用动态规划的语言表述，体现了他在创立动态规划理论时对这类问题的深度思考。

值得留意的是，"最多 $k$ 条边"这个维度在标准实现里被省掉了——代码只留一个 dist 数组，原地覆盖。这个省法在求最短路时无害（如前所述只会更好），但在一类问题上必须还原：如果题目问的是"恰好用 $k$ 条边的最短路"，或者要限制经过的边数（例如航线中转次数上限），就必须老老实实开两层数组、严格只读上一层。这是 Bellman-Ford 家族里最常见的一处误用。

与 Floyd-Warshall 的关系#

Bellman-Ford 解决单源最短路径（从一个固定源到所有节点）。若需要所有节点对间的最短路径，运行 $V$ 次 Bellman-Ford 需要 $O(V^2 E)$。

Floyd-Warshall 算法用一个三重循环直接求所有节点对最短路，时间 $O(V^3)$——在稠密图（$E = O(V^2)$）上，$O(V^3)$ 与 $V$ 次 Bellman-Ford 的 $O(V^4)$ 相比快得多。

在稀疏图上还有第三条路：Johnson 算法先用一次 Bellman-Ford 求出一组势函数、把所有边权改造成非负，再跑 $V$ 次 Dijkstra，总时间 $O(V^2\log V + VE)$。三者的分工可以这样记——Bellman-Ford 的真正职责不是"慢一点的最短路"，而是"唯一能消化负权的那道预处理"，Johnson 算法用它开路，然后把重活交给 Dijkstra。

跨域连接#

• 外汇：取对数把汇率相乘变成权重相加，环上权重和为负就等价于绕一圈钱变多。但负环只是必要条件：每次兑换的买卖价差与手续费必须并入边权，三次兑换各扣千分之四，就足以把一个千分之十的负环变回正环。真正的瓶颈因此不是检测算法，而是从发现到成交的延迟——环消失得比算得快。
• 最优化：一组形如 $x_j - x_i \le w$ 的差分约束是否可行，等价于对应图上有没有负环，而距离数组本身就是一组可行解。这把最短路变成了通用的可行性判定工具：任务调度的时序约束、时钟偏移的界、程序里的循环依赖都能写成这种形式；无解时算法还能指出是哪一圈约束互相矛盾。
• 热力学定律：能量是状态函数，沿任何闭合回路的净变化必须为零。"存在使总量单调下降的闭环"在物理上就是第一类永动机，被守恒律直接禁止。所以负环检测在物理建模里是一种自洽性检查：若从实验数据反推出的势能面上出现负环，说明测量或模型有内在矛盾，而不是找到了免费能量。
• 强化学习：值迭代的每一步就是对 Bellman 方程做松弛，与这里的边松弛是同一个操作。折扣因子小于一的作用正是防止负环式的发散——它让 Bellman 算子成为压缩映射，保证唯一不动点。无折扣且存在正收益环时值函数发散到无穷，与最短路在负环下失去意义完全对应。
• 路由与交换：把松弛分散到各台路由器上异步执行，就是距离向量协议。它的根本缺陷不是丢包，而是消息只带数字不带路径，收方无法判断这条路是否绕回了自己，于是出现互相抬价的计数到无穷。链路状态协议的解法是让每台机器拿到全图各自算一遍——用存储与洪泛换掉这个结构性缺陷。

参考文献#

• Bellman, R. "On a Routing Problem." Quarterly of Applied Mathematics 16(1), 1958.
• Ford, L.R. "Network Flow Theory." RAND Report P-923, 1956.
• Moore, E.F. "The Shortest Path Through a Maze." Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 1959.
• Hedrick, C. Routing Information Protocol. IETF RFC 1058, 1988.（无穷取 16 的理由）
• Malkin, G. RIP Version 2. IETF RFC 2453, 1998.（跳数上限 15、30/180/120 秒定时器、水平分割与毒性逆转）
• Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022.（第 22 章 Single-Source Shortest Paths）

延伸阅读#

• Tanenbaum, A.S. & Wetherall, D. Computer Networks. 5th ed. Prentice Hall, 2010.（第 5 章网络层，距离向量与链路状态的对照）
• Ahuja, R.K., Magnanti, T.L. & Orlin, J.B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.（第 5 章标号修正法与 Bellman-Ford 的各种变体）
• Kurose, J.F. & Ross, K.W. Computer Networking: A Top-Down Approach. 8th ed. Pearson, 2020.（count-to-infinity 与水平分割的教学推演）