专题：最短路（二）—— Bellman-Ford、SPFA 与负环

本讲定位：图论系列第六讲。第 05 讲的 Dijkstra 有一个致命前提——边权非负，那个 3 个点的反例已经把它推翻了。本讲给出替代方案：既然不能贪心地”定”点，那就别定了，把每条边老老实实松弛够次数。这就是 Bellman-Ford，以及它的队列优化 SPFA。本讲做了六组实测：SPFA 与 Bellman-Ford 在 8000 组负权图上结果一致；$n-1$ 轮这个上界是紧的——同一条链，边倒序给出时少跑一轮就得不到答案，边顺序给出时 2 轮就够（差别全在边的给出顺序）；“最多经过 $k$ 条边”不备份数组实测错 6.9%，最小反例只要 3 个点 2 条边；SPFA 的两面性——随机稀疏图上它比 Dijkstra 快 3 倍，网格图上慢 49 倍（出队次数达点数的 366.8 倍）；判负环三法全部正确，但速度差了三个数量级，DFS 版比”入队次数”版快 2800 倍；最后是一个容易被忽略的陷阱——负环上 dis 会一直减到 int 溢出，然后 SPFA 反而报告”无负环”（实测 $200\times200$ 网格上跑了 19.84 秒后给出错误答案）。文中所有代码经 g++ -O2 -std=c++14 -Wall 编译运行，P3385 与洛谷官方样例核对通过。

前置知识：第 05 讲的松弛操作与 Dijkstra（必须先学，本讲从它的失败讲起）；第 05 讲 6.3 节那张”三种写法在负权下表现不同”的表——本讲第 4 节就是它的展开。第 01 讲的邻接表；queue 的基本用法。

适合对象：第 2、4、5 节标 J（CSP-J 复赛偶尔出现负权/判负环题）；第 3 节（限边数）标 S；本讲整体的重要性不在考频，而在于它是差分约束（番外 A）的唯一执行引擎，也是理解”为什么正权一律用 Dijkstra”的必经之路。

1. 从上一讲那个反例说起

第 05 讲 6.1 节的反例：$1\to2$ 权 $2$，$1\to3$ 权 $1$，$2\to3$ 权 $-3$。真实 $dis[3] = -1$，而 Dijkstra 给出 $1$。

病根在 05 讲 3.2 节的正确性证明里那一句：

“$P$ 上从 $x$ 到 $u$ 的那一段长度 $\ge 0$（这里用到了边权非负）”

有负边时，“当前 dis 最小的点”不再保证已经最优——后面可能冒出一条负边，让一条看起来更远的路反而更短。贪心的地基塌了。

那就别贪心了。回到第 05 讲第 2 节那个更朴素的事实：

只要 dis 数组里每个值都对应一条真实路径，它就是上界；当没有任何边还能被松弛时，dis 就是答案。

于是有了一个笨到不能再笨的办法：把所有边反复松弛，直到松不动为止。 这就是 Bellman-Ford。剩下的唯一问题是：要松弛多少轮才够？

2. Bellman-Ford：把每条边松弛够

2.1 算法

struct E { int u, v, w; };
vector<E> es;                              // 直接存边表，不需要邻接表

memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
for (int it = 1; it <= n - 1; it++) {      // 跑 n-1 轮
    bool upd = false;
    for (size_t i = 0; i < es.size(); i++) {
        int u = es[i].u, v = es[i].v, w = es[i].w;
        if (dis[u] < INF && dis[u] + w < dis[v]) {   // 松弛（注意判 dis[u] 可达）
            dis[v] = dis[u] + w;
            upd = true;
        }
    }
    if (!upd) break;                       // 本轮一次都没松弛动，提前结束
}

复杂度 $O(nm)$。代码比 Dijkstra 还短，而且不需要邻接表，直接遍历边表就行——这是它在差分约束里好用的原因之一。

2.2 为什么 $n-1$ 轮够

关键结论：无负环时，最短路最多经过 $n-1$ 条边。

理由一句话：最短路上不会出现重复的点。若重复了，说明路径里含一个环；这个环的权值 $\ge 0$（无负环），去掉它只会更短或一样长——所以总存在一条不含环的最短路。不含环的路径最多有 $n$ 个点，也就最多 $n-1$ 条边。

再看每一轮松弛做了什么：用归纳法——