最短路二：Floyd、Bellman-Ford、SPFA 与负环

为什么不是「图里有没有负环」？因为走不到的负环不影响答案： 图的角落里躺着一个负环，可 s 根本过不去，那这道题的答案照样是一串老老实实的距离。

而这句话对三种算法的代价完全不一样：

	「只算 s 能走到的」这件事
Floyd	要手动补一句 d[s][k] < INF —— 它算的是全图，天生不知道 s 是谁
Bellman-Ford / SPFA	白送 —— dist 从 s 初始化，走不到的点永远是 INF

★ 同一个题面，一个天生满足、一个必须自己补 —— 这种地方最容易在两份代码之间写出不一致，而且两边各自看都「没毛病」。 第 8 步那个 wrongGlobalNeg.cpp 就是漏了那半句。

7 9 5
5 6 4      ┐
6 7 -2     ├ 5 →(4) 6 →(-2) 7 →(3) 4     ← 拐两个弯才最近
7 4 3      ┘
5 4 9      ← 一步直达 4 号，长 9（更差）
6 4 8      ← 从 6 号一步到 4 号，4+8 = 12（也更差）
1 2 -5     ┐
2 3 2      ├ 1 → 2 → 3 → 1，总长 -5+2+1 = -2 ★ 一个负环
3 1 1      ┘
2 5 7      ← 只有这一条把那块连过来，而且是单向的：s 过不去

手算：d[5]=0，d[6]=4，d[7]=4-2=2，d[4]=2+3=5（比 9 和 12 都小）。 1、2、3 号从 5 号根本走不到。答案：

x x x 5 0 4 2

★ 注意 4 号那个 5：它是拐了两个弯得来的，而两条「一步到位」的近路都更差 —— 这是第 5 步用来照 Floyd 那个 bug 的。

4 4 1
1 2 3
2 3 -2
3 2 -2     ← 2 → 3 → 2 绕一圈是 -4，而 s = 1 走得到 2 号
3 4 1

答案：NEGATIVE。绕那个圈可以让距离无限小，「最短路」这三个字失去意义。

5 5 1
4 5 1      ┐
3 4 1      │ 边故意倒着排 —— 第 6 步会看到这一点有多要命
2 3 1      │
1 2 1      ┘  链：1 →(1) 2 →(1) 3 →(1) 4 →(1) 5
1 5 10     ← 一步直达 5 号，长 10（更差）

答案 0 1 2 3 4。★ 到 5 号的最短路必须走满 4 条边 —— 也就是 n−1 条。 这张图是专门用来说明「n−1 轮一轮都不能少」的。

点「运行 ▶」看结果

Floyd 看起来是三行循环，其实它本来是个三维 DP：

f[k][i][j] = 只允许拿 1..k 当中转站时，i 到 j 的最短距离

f[k][i][j] = min( f[k-1][i][j],  f[k-1][i][k] + f[k-1][k][j] )
                    ↑ 不用 k        ↑ 用 k（而且只用一次，用两次没意义）

k 是阶段，i、j 只是表格里的格子。 阶段必须在最外层 —— 这就是第 21 章那句「依赖谁，就先填谁」，这是它第七次登场。

而「转移右边用的必须是 k−1 那一层」，和第 23 章 01 背包那句 「转移右边的第一维必须是 i−1」是同一个形状： 那里滚动掉的是物品，这里滚动掉的是中转站。

⚠ 第一维能滚掉（写成二维 d[i][j]）是因为 f[k][i][k] == f[k-1][i][k]： 多一个 k 可以中转，对「到 k 的距离」毫无帮助 —— 绕经自己只会更远。

if (d[i][k] >= INF) continue;
… if (d[k][j] < INF) …

for (int k = 1; k <= n; k++)
    if (d[k][k] < 0 && d[s][k] < INF) { cout << "NEGATIVE\n"; return 0; }

点「运行 ▶」看结果

点「运行 ▶」看结果

外层固定 i、j 之后，内层把 k 从 1 扫到 n。 可它用到的 d[i][k] 和 d[k][j] 里，很多格子这时候压根还没被更新过 —— 拿半成品去算，结果就是半成品。

⚠ 它最可怕的地方是大部分时候是对的：不崩溃、不报错， 只有当最短路必须拐好几个弯、而且那些弯的编号顺序不巧时才现形。 第 9 步那张表里，300 轮它只错 85 轮 —— 也就是说， 你随手造几组数据试一试，很可能一次都碰不到。

★ 所以它是给生成器出的一道题：数据里得有「绕好几个中转点才最短」的路。

点「运行 ▶」看结果

不变量只有一句，归纳一行就证完了：

跑完第 i 轮之后，dist[v] ≤「从 s 出发、最多走 i 条边能到 v 的最短长度」。

（第 i 轮松弛边 (u,v) 时，dist[u] 已经不差于「最多 i−1 条边」的答案。）

而没有负环时，最短路一定是一条简单路径 —— 它最多经过 n 个点、也就是 n−1 条边。

★ 所以「n−1」不是背下来的，它就是「简单路径最多 n−1 条边」这句话。

点「运行 ▶」看结果

它输出 NEGATIVE。可图 C 里一条负权边都没有。

道理很简单，但值得停一下：判负环的方法是「再多跑一轮，看还能不能松弛成功」。 少跑一轮 ⇒ 还没收敛 ⇒ 那一轮当然还能松弛成功 ⇒ 它把「没收敛」当成了「有负环」。

★ 一个 bug 同时污染两种输出 —— 这类 bug 最难从现象倒推回原因， 因为你会盯着「为什么误报负环」去查判环那段代码，而毛病根本不在那儿。

for (auto [u, v, w] : es) {
    if (dist[u] == INF) continue;
    if (dist[u] + w < dist[v]) { cout << "NEGATIVE\n"; return 0; }
}

为什么它对，两句话：能松弛成功说明存在一条「用了 n 条边还更短」的走法； n 条边的走法必然重复经过某个点、也就是绕了一个环，而绕它让距离变小 —— 那就是负环。

⚠ 而且它天生只报告「从 s 能走到的」负环（dist 从 s 初始化，走不到的永远是 INF）—— 这就是第 1 步那张表里 Floyd 要手动补、它却白送的那件事。

点「运行 ▶」看结果

点「运行 ▶」看结果

第 32 章的 fast.cpp 在负权图上 300 轮一次都没错，当时给的解释是 「它已经不是 Dijkstra 了」。现在可以把话说完：

// 第 32 章 fast.cpp（堆优化 Dijkstra）
auto [d, u] = q.top(); q.pop();
if (d > dist[u]) continue;                 // 过期的就扔掉
for (auto [v, w] : g[u])
    if (d + w < dist[v]) { dist[v] = d + w; q.push({dist[v], v}); }

// 这一章 spfa.cpp
int u = q.front(); q.pop(); inq[u] = 0;    // 出队就清标记
for (auto [v, w] : g[u])
    if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inq[v]) q.push(v); }

同一个算法，只差用什么容器。 把 SPFA 的队列换成小根堆，它就长成上一章那副样子； 而那句 if (d > dist[u]) continue; 顶替的正是这里的 inq 判重。

★ 所以第 32 章那句结论要这样收尾： 上一章的堆优化在负权图上给出正确答案，不是因为 Dijkstra 对负权成立， 而是因为它执行的是这一章的 SPFA。

点「运行 ▶」看结果

点「运行 ▶」看结果

第 32 章我写过一个几乎一模一样的错误版本，然后被实测打脸： 那一章边权非负，INF + w 比 INF 大，松弛条件 dist[u] + w < dist[v] 根本不成立 —— 所以「不判可达」在那里一点事都没有，那份代码和正解一模一样。

这一章边权可以是负的。INF + (-5) 比 INF 小，那一句当场成立：

走不到的点会被刷出一个「比 INF 小一点」的距离，然后顺着边一路传染出去。

而图 A 里走不到的那三个点之间还有一个负环 —— 于是它一路刷下去， 最后连负环都误报了。一个 bug 同时污染两种输出（第二次）。

★ 同一句代码危不危险，取决于数据的取值范围。 「这句判断是不是多余的」这种问题，没有脱离数据的答案。

点「运行 ▶」看结果

要什么	为了打假谁
① 负权边	没有它，这一章讲的东西一件都验不到（退化成第 32 章）
② 从 s 走不到的点	「不判可达就松弛」（第 30、32 章那条第三次）
③ 从 s 走不到的负环	「判负环不看可达」—— 本章最刁的一条
④ 长链	「Floyd 的 k 放错层」和「少跑一轮」：随机图上最短路两三条边就走完了

⚠ 而它们互相打架：

• 负权边一随机，就很容易撞出负环，那一组的答案就成了 NEGATIVE，长链白造了；
• 负环一多，一大半数据的答案都是 NEGATIVE，别的 bug 全被挤没 （第 31、32 章「某一支占得太多」的第三次，档位 4 那一行就是现场）；
• 图一碎（为了造走不到的点），长链就不容易连起来。

★ 解法是把它们拆开分别控制，两招都是从前面章节搬来的：

招一：势函数（第 32 章那个）。 造边时先随机一个非负的 w0，再令

w(u → v) = w0 + h[u] − h[v]

任何环上 h 首尾相消 → 环长 = Σw0 ≥ 0 → 绝不可能有负环，但单条边可以是负的。 于是负环只在我故意注入的时候才出现（往回加一条特意配平过头的边）。 负权边的浓度归势函数管，负环的比例归注入管，两件事解耦了。

招二：把点分成两块。

R = id[0 .. L-1]（起点 s 就在里面）      U = id[L .. n-1]

边只允许 R→R、U→U、U→R，永远不连 R→U —— 于是 U 天生从 s 走不到。 两块各串一条链保证内部连通，负环想注入哪一块都行。 把负环注入到 U 里，它就是「一个 s 永远走不到的负环」 —— 第 ③ 件事有了。

gen.cpp 带了十个档位（./gen 种子 档位），种子固定 1..300：

档位	改了什么	NEGATIVE	有 x	k 放错层	少跑一轮	不判可达	不看可达	inq 没清
0（最初）	非负权 + 处处可达 + 纯随机边	0	0	83	2	0	0	12
1	用势函数 → 出现负权边	0	0	83	2	0	0	12
2	L 可以小于 n → 出现走不到的点	0	239	31	0	97	0	4
3	R 那条链的 w0 全压成 0 → 逼出长最短路	0	239	73	4	97	0	69
4	注入负环（只往 R 里注）	300	0	1	0	0	0	284
5	负环也可能注入进 U	241	59	11	0	59	59	233

⚠ 档位 1 一个数字都没变。 光有负权边、没有别的配套，五个 bug 一个都没多抓到 —— 这条老实账要写在这儿：「加了个好东西」不等于「数据变好了」。

★ 档位 4 那一行是这一章最刺眼的地方：300 轮全是 NEGATIVE， 于是「k 放错层」从 73 掉到 1、「不判可达」从 97 掉到 0。 负环那一支占满了整张表，别的 bug 连出场的机会都没有。

档位	改了什么	NEGATIVE	有 x	k 放错层	少跑一轮	不判可达	不看可达	inq 没清
5	（上一张表的最后一行）	241	59	11	0	59	59	233
6	注入比例降到 2/3	133	152	33	0	113	77	148
7	★ 最坏边序 + 链拉满全图	152	98	48	37	71	57	170
8	注入比例再降到 1/3	74	129	84	71	73	35	145
9（在用）	注入尽量往 U 里放	62	141	85	71	85	47	135

★ 档位 7 那一行是这一章最费劲的一处，而且它教了一条新东西：

「少跑一轮」这个 bug，要现形得同时满足两件事 —— 最短路真的用满 n−1 条边（链得跨过所有点），而且边是按最坏顺序给的。

实测：只把边打乱 → 0 / 300；只把链拉满 → 4 / 300；两样一起 → 37 / 300。

⚠ 为什么边序这么要命：Bellman-Ford 一轮里是按输入顺序挨个松弛边的。 链要是正好顺着排，一轮就能从头传到尾，n−2 轮绰绰有余。 随机顺序下一轮平均也能往前推两三格。 只有把链倒着放，才逼得它一轮只推进一格 —— ★ 「n−1 轮」这个下界，只在最坏的边顺序下才是紧的。

⚠ 由此得到一条以前没写过的规矩：边的顺序也是数据的一部分。 而且更一般地：要证明一个下界是紧的，就得自己造出那个最坏情况 —— 随机数据永远碰不到它。这是随机对拍的又一个盲区 （第 20 章「对拍只能证伪」、第 31 章「验证器的盲区」之后的第三个）。

档位 9 的选法照旧是第 32 章那条：让最弱的那一支尽量强 （档位 8 最弱的是 35，档位 9 是 47）。

gen.cpp（十个档位）九次改动全部可重跑

展开：势函数 + 分两块 + 最坏边序，具体怎么写

g++ -O2 -std=c++17 -o genBig genBig.cpp && g++ -O2 -std=c++17 -o brute brute.cpp
g++ -O2 -std=c++17 -o bell bell.cpp && g++ -O2 -std=c++17 -o spfa spfa.cpp
./genBig 2400 > big.txt
time ./brute < big.txt > /dev/null      # 5.77 秒
time ./bell  < big.txt > /dev/null      # 0.00 秒

	复杂度	负权	负环	什么时候用它
Dijkstra（第 32 章）	O(m log n)	✗	✗	边权非负 —— 能用它就用它，快一个数量级
Floyd	O(n³)	✓	✓（全图）	要所有点对之间的距离，而且 n 很小（几百）
Bellman-Ford	O(nm)	✓	✓（s 可达）	有负权 / 要判负环；代码最短，而且常数极小
SPFA	最坏 O(nm)	✓	✓（s 可达）	同上，通常更快 —— 但最坏情况会被卡

★ 一句话：先问边权有没有负数。 没有就 Dijkstra，有就 Bellman-Ford 那一族； 要所有点对、而且 n 小，才轮到 Floyd。

【1】★ Floyd 的 k 是阶段，必须在最外层。 f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j]) —— k 是阶段，i、j 只是格子。这就是第 21 章「依赖谁就先填谁」的第七次登场， 也和第 23 章「转移右边的第一维必须是 i−1」是同一个形状。 ⚠ 放错层不崩溃、不报错，300 轮里只错 85 轮。

【2】★ Bellman-Ford 的 n−1 不是背的。 跑完第 i 轮，dist 就不差于「最多走 i 条边」的答案； 而没有负环时最短路是简单路径，最多 n−1 条边。判负环是白送的：多跑一轮还能松弛就有环。 ⚠ 少跑一轮不是答案错，是误报负环（没收敛而已）。

【3】★ SPFA 就是第 32 章那份「不小心答对了」的堆优化。 同一个算法，只差用什么容器。所以上一章那句结论要收尾成： 堆优化在负权图上答对了，不是因为 Dijkstra 对负权成立，而是因为它执行的是 SPFA。 ⚠ inq 记的是「在不在队里」，出队要清 —— 别和第 30 章 BFS 的 vis 记混。

【4】★ 同一句代码危不危险，取决于数据的取值范围。 「不判可达就松弛」在第 32 章（非负权）里完全没事，在这一章会一路传染、还连带误报负环。 同理，「走不到」这一章不能再用 -1 当记号 —— 因为距离本身可以是负的。 没有脱离数据的代码审查。

【5】★ 边的顺序也是数据的一部分。 「n−1 轮」这个下界只在最坏的边顺序下才紧：只打乱边 → 0 / 300；只把链拉满 → 4 / 300； 两样一起才 37 / 300。 更一般地：要证明一个下界是紧的，就得自己造出那个最坏情况 —— 随机数据永远碰不到它。这是随机对拍的第三个盲区 （前两个：第 20 章「只能证伪」、第 31 章「验证器证明不了没漏报」）。