2.2 Bellman-Ford与SPFA：处理负权边

2.2 Bellman-Ford 与 SPFA：处理负权边

本节摘要：Bellman-Ford 算法通过"对所有边重复松弛、共点数减一轮"的暴力迭代求解带负权边的单源最短路径，时间复杂度为点数乘以边数；额外再做一轮全量松弛即可检测负权环。SPFA 在其基础上引入队列，只松弛"距离刚被更新的点"的出边，平均复杂度大幅下降但最坏仍与 Bellman-Ford 持平。当你的图里可能出现负权（折扣、收益、惩罚反转），这一节就是标准答案。

核心问题

阅读完本节，你应当能够：

1. 写出 Bellman-Ford 的核心循环，并解释"点数减一轮"的由来；
2. 用第 n 轮松弛是否仍有更新来检测负权环；
3. 说明 SPFA 的队列机制、平均与最坏复杂度；
4. 判断一个具体场景该用 Dijkstra、Bellman-Ford 还是 SPFA。

一、问题与直觉：负权从哪来

先看负权边在现实里的样子。货币兑换里"手续费为负的通道"（套利路径）、物流里"顺路带货反而赚钱"的补贴段、推荐系统里把"用户厌恶"编码为负相似度——这些都是天然的负边。一旦存在，Dijkstra 的"定型不反悔"承诺就失效了：一个当前看起来很远的点，可能通过一条负边被远处的点反过来"打折"。

Bellman-Ford 的态度朴实得多：不挑顺序，全部松弛，多来几轮。既然任何一条最短路径至多包含点数减一条边（简单路径不绕重复点），那么把所有边成批松弛点数减一次后，任何合理的更新都必然已经发生。这个论证同时给了算法正确性和轮数上限——原始文集称之为"容错的旅行者"：走得慢，但什么坑都能过。

二、Bellman-Ford：迭代松弛与负环检测

算法骨架：

def bellman_ford(edges, n, start):
    # edges 为边集数组 每项为 u v w
    dist = [float('inf')] * n
    dist[start] = 0
    for _ in range(n - 1):            # 点数减一轮
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:               # 提前收敛 常见的大加速
            break
    # 负环检测 第n轮
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None               # 存在从源点可达的负权环
    return dist
​

为什么是点数减一轮：归纳可证，第 k 轮结束后，所有"边数不超过 k 的最短路径"的距离都已正确。最短路径本身是简单路径，至多含点数减一条边，所以点数减一轮封顶。负环检测的原理同一句话：如果点数减一轮之后还能松弛，说明存在越走越短的环——从源点可达的负环意味着"最短路"这个概念本身崩塌（绕环无限次距离趋于负无穷）。

提前终止是个重要的工程优化：多数真实图根本用不满点数减一轮，某一轮没有发生任何更新就可以立刻收工。

复杂度：点数乘以边数，空间只要一个距离数组和边集。对比 Dijkstra 堆优化的"边数乘 log 点数"，它明显更慢——这是为"容忍负权 + 检测负环"付的保险费。

三、SPFA：给 Bellman-Ford 装上队列

Bellman-Ford 慢在哪？每轮把所有边无差别扫一遍，可其中绝大多数边根本不可能引发更新——它们的起点距离本轮并没有变。SPFA（Shortest Path Faster Algorithm）的观察是：只有"距离刚被更新的点"才可能带来新的松弛机会。于是用一个队列装这些点，出队一个点、只松弛它的出边，被更新的邻居若不在队中则入队，直到队列空。

from collections import deque

def spfa(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    in_queue = {node: False for node in graph}
    queue = deque([start])
    in_queue[start] = True
    while queue:
        u = queue.popleft()
        in_queue[u] = False
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
    return dist
​

原始文集给出的复杂度刻画很清醒：SPFA 平均是"一个较小常数乘以边数"，实测通常明显快于 Bellman-Ford；但最坏情况仍是点数乘以边数——而且"容易被特殊构造的数据卡掉"。这个警告来自算法竞赛的多年血泪：出题人专门设计网格图、嵌套结构，让 SPFA 反复把同一批点推进队列，性能雪崩。判断负环同样可以借助 SPFA：记录每个点入队次数，超过点数即有负环（比 Bellman-Ford 的事后检测更早发现）。

三算法选型对比

我的选型建议压缩成两句话：能确认非负权，永远用 Dijkstra；必须处理负权，小规模或要求可预期性能用 Bellman-Ford（配合提前终止），规模大且数据"自然"再考虑 SPFA——对外提供的线上服务慎用 SPFA，因为输入分布不受你控制。

⚠️ 常见坑：把"最坏情况"当成耳旁风。SPFA 在论文里的平均表现和在生产环境里的表现可以差几个数量级，攻击性输入并不罕见。另一个坑是负环检测只对"源点可达的负环"生效——不可达的负环不影响任何答案，也检测不出来。

💡 关键直觉：Bellman-Ford 像"全员大扫除"，SPFA 像"哪里脏了扫哪里"。队列机制的本质是把松弛的传播范围限制在"变化的波及区域"，这与 BFS 的涟漪扩散异曲同工——只是这里的"涟漪"由距离更新触发，而不是由首次访问触发。

四、深入一层：负环的世界到底长什么样

负环 detection 的输出经常被误读，值得把语义说透。算法报告"存在负环"时，严格的含义是"存在从源点可达的负环"。此时"最短距离"这个量对可达负环上的点（及其下游）没有定义——绕环 k 圈能把距离压到任意低，infimum 是负无穷，不存在最小值。业务上要分三类处理：套利检测里，负环本身就是答案（找到了无风险套利路径）；路径规划里，负环通常意味着数据错误（边权录入错误），应告警人工介入；若负环不可达源点，它不影响任何答案，检测不出来也不需要检测。

另一个深度话题是松弛的"传播半径"。Bellman-Ford 的第 k 轮，本质是把"距离更新的影响"向前传播 k 步——这与 BFS 的层序传播同构，只是 BFS 传播"可达性"、这里传播"更优性"。SPFA 把这个观察推向极致：只有发生更新的点才值得传播。理解了这一层，你会发现第 2 章的所有算法共享同一个骨架——信息在图上的受控扩散，不同的只是"信息"（可达、更短、更便宜）与"扩散顺序"（层序、贪心序、拓扑序、队列序）。

常见疑问解答

提前终止会不会漏掉负环检测？

不会。负环检测用的是"点数减一轮结束后再做一轮"这个独立步骤，与主循环是否提前收敛无关。主循环提前停下只说明"距离已稳定"，随后的检测轮该做照做——如果稳定后还能松弛，那就是负环的铁证。

SPFA 判负环的"入队次数超点数"为什么对？

一个点若被松弛成功 n 次（入队 n 次），意味着从源点到它的路径已经使用了至少 n 条边——n 个顶点的简单路径至多 n 减 1 条边，多出来的边只能来自重复经过的顶点，即环；而距离在环上还能持续下降，环必为负。实践中为了更早发现，也常用"最短路边数计数"或"记录路径上的环"等变体，原理相同。

队列换成栈会怎样？

就变成另一个算法（接近 SPFA 的栈式变体），正确性仍由"松弛收敛"保证，但性能特征变化明显——栈式在负环场景下反而能更快地"钻进"环里，因此有些负环检测实现故意用栈。这再次说明：框架（迭代松弛）与调度（找边的顺序）是解耦的，调度只影响速度与检测时机。

有没有"又快又稳"的负权方案？

工程上常见两条路：一是检查负权边的语义能否消除（比如把"收益"改成"成本上限减收益"做重赋权，类似 Johnson 的思路）；二是图规模可控时直接 Bellman-Ford 加提前终止，把不确定性锁在最坏复杂度之内。把 SPFA 的"平均很快"当作依赖，才是真正的风险。

动手实验：构造一个让 SPFA 落泪的图

竞赛圈流传着一类"卡 SPFA"的构造，原理是让队列反复吞吐同一批顶点。一个简化版：把若干个"菱形"（源到 a、源到 b、a 到 c、b 到 c，其中一条边带负权）串联，负权边精心取值使每轮松弛恰好只前进一小步。动手搭一个二十个菱形的图，先跑 Bellman-Ford 记录轮数，再跑 SPFA 记录总出队次数——你会看到 SPFA 的出队次数远超点数，最坏情形的阴影具象化了。这个实验的价值不在记住构造本身，而在建立"平均复杂度的承诺需要数据分布背书"的直觉，它同样适用于哈希表、快排等一切平均情形优秀的结构。

负权场景的业务清单

真实系统里出现负权边时，建议按序过一遍：确认负权的业务语义（收益、折扣还是数据错误）；确认不存在可达负环（用检测环节拿证据）；评估能否重赋权消除负权（约翰逊套路的前半段就能用）；最后才把 Bellman-Ford 或 SPFA 放进关键路径，并配好监控（松弛轮数超阈值告警）。四步走完，负权从隐患变成可控参数。

队列版和栈版的 SPFA，工程上怎么选？

默认队列版（最短路场景平均更稳）；仅在做负环检测且希望尽快"钻进"环里时考虑栈版。更实用的建议是给两者都配上"入队次数监控"——超过点数即告警终止，无论哪种容器都不会失控。容器选择是微优化，失控保护才是必需品。

再补一个实用细节：Bellman-Ford 的边遍历顺序对收敛速度有实际影响——按"接近源点的边在前"的启发式排序，常能减少有效轮数；竞赛圈的"队列优化加松弛序调整"正是这个思路的极致化，工程上做个简单的边重排就能白拿一截加速。

一句话总结：Bellman-Ford 贵在确定，SPFA 险在侥幸；选哪个，取决于你的输入是天下太平还是暗流涌动。

本章回顾

• 存在理由：负权边让 Dijkstra 的贪心失效，Bellman-Ford 用无差别多轮迭代换正确性。
• 轮数上限：任何最短路至多含点数减一条边，故点数减一轮全量松弛必然收敛。
• 负环检测：第 n 轮仍可松弛即存在（可达）负环，此时最短路不存在。
• 提前终止：某轮无更新即收敛，是 Bellman-Ford 最实用的工程加速。
• SPFA 机制：队列装"刚被更新的点"，只松弛其出边；平均快、最坏同 Bellman-Ford。
• SPFA 风险：可被构造数据卡到最坏复杂度，线上服务慎用；可用入队次数检测负环。
• 选型铁律：非负权用 Dijkstra；负权小图用 Bellman-Ford；负权大图酌情 SPFA。

到这里，单源问题已经闭环。下一节把镜头拉远——当问题变成"图中每对顶点间的最短路径"，三重循环的 Floyd-Warshall 和组合拳式的 Johnson 将接手。