Lesson 0412 · 最短路 II：Bellman-Ford / SPFA / Floyd

④ 数据结构与算法 — 第 12 课

上节课：Dijkstra —— 每次挑 dis 最小的未确定点，就地「盖章」确定，靠一条前提保证盖下去不反悔：边权非负。
这节课：把那条前提拆掉。边权可以是负数，Dijkstra 立刻失效（下面第一件事就是看它怎么错）。修法意外地朴素 —— 不盖章，让所有点反复松弛，这就是 Bellman-Ford；给它加一个队列，就是 SPFA；如果要做「所有点对」，还有五行代码的 Floyd。配题 P3385（负环模板）。
三句话速览
先把你上次那道手推题结掉（0411 留的：①-7->②、①-2->③、③-3->②、②-1->④、③-100->④）
dis 初始 ①0 ②∞ ③∞ ④∞，然后：
① 未定点里最小的是 ① (0) → 松弛出边：②=7，③=2
② 未定点里最小的是 ③ (2) → ②=min(7, 2+3)=5，④=2+100=102
③ 未定点里最小的是 ② (5) → ④=min(102, 5+1)=6
④ 未定点里只剩 ④ (6) → 结束
答案：①0 ②5 ③2 ④6。
「第 2 步为什么敢认定 ③ 定型？」因为此刻未定点里 ③ 的 dis=2 最小。要从别处绕到 ③，必须先经过某个未定点 x，而 dis[x] ≥ 2（③ 是最小的那个），再加上边权 ≥ 0，绕过去只会更贵 —— 所以 2 就是最终答案。这句推理里「边权 ≥ 0」正是今天要拆掉的砖。

1. 负权把 Dijkstra 弄坏在哪

四个点，一条负权边：

1 --2--> 2 --1--> 4
1 --3--> 3
3 --(-2)--> 2

真值：d2 = 3 + (-2) = 1，d4 = d2 + 1 = 2

把上节课那份朴素 Dijkstra 原样跑一遍（下面这段是程序实际打印出来的过程）：

finalize 1 (d=0) : relax 1->2 => d2=2   relax 1->3 => d3=3
finalize 2 (d=2) : relax 2->4 => d4=3
finalize 3 (d=3) : relax 3->2 => d2=1      <-- 2 号已经盖过章了
finalize 4 (d=3) :
d1=0  d2=1  d3=3  d4=3      <-- d4 错，真值 2

错在哪一步？4 号的距离 3 是拿「2 号 = 2」这个旧值算出来的。后来 3 号把 2 号压到了 1，可 2 号已经盖过章 —— 它的出边不会再被走一遍，4 号就永远停在 3。

更阴的是：d2 最后显示 1，是对的。因为数组里的值确实被改小了，只是「改了也不会重新往外传播」。所以负权图上的错误常常不是一眼可见的崩，而是有的点对、有的点错。

Dijkstra 的每一次盖章，都在赌一件事：以后不会再有更便宜的路通到这个点。
非负权时这个赌必赢（0411 证明过）；一旦出现负权边，它就可能输 —— 而且输了不报警。

2. Bellman-Ford：不盖章，全体反复松弛

既然「盖章」是问题，那就干脆不盖。规则只有一句：

把所有边松弛 n-1 轮。每轮从头到尾扫一遍边数组，只要 dis[u] + w < dis[v] 就更新 dis[v]。一个点被改小多少次都行，从不「定死」。
为什么是 n-1：没有负环时，最短路一定是简单路径（绕圈只会变贵或白走），最多 n-1 条边；每松弛一轮，至少能把「路径上再多走一条边」的信息往外传一层。

代码（原样用 g++ -O2 -std=c++17 -Wall -Wextra 编译过，零警告）：

const int INF = 0x3f3f3f3f;

struct Edge { int u, v, w; };      // 有向边 u -> v，权 w
vector<Edge> edges;

// 返回 true = 没有负环；顺便把 dis 算好
bool bellman_ford(int s, vector<int>& dis) {
    dis.assign(n + 1, INF);
    dis[s] = 0;
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;
        for (auto& e : edges) {
            if (dis[e.u] == INF) continue;              // 不可达的点别拿去加
            if (dis[e.u] + e.w < dis[e.v]) {
                dis[e.v] = dis[e.u] + e.w;
                changed = true;
            }
        }
        if (!changed) break;                            // 整轮没变化 → 提前收工
    }
    for (auto& e : edges)                              // 第 n 轮还能松弛 → 有负环
        if (dis[e.u] != INF && dis[e.u] + e.w < dis[e.v]) return false;
    return true;
}

拿第 1 节那张图实测（同一个程序里跑的）：

bellman_ford ok=1 : d1=0 d2=1 d3=3 d4=2      <-- d4 对了
spfa         ok=1 : d1=0 d2=1 d3=3 d4=2
floyd        : d(1,2)=1 d(1,3)=3 d(1,4)=2

Bellman-Ford 在第 1 轮就把 d4 修正成了 2 —— 因为它不认「盖子」，每轮都重新看所有边。

轮数取决于边的扫描顺序（实测）

「最多 n-1 轮」是最坏情况，实际要几轮和边的排列顺序关系很大。实测一张链 1→2→3→4→5→6（每条边权 1，真值 d6 = 5）：

边数组的给出顺序实际用了多少轮d6
1→2, 2→3, 3→4, 4→5, 5→6（顺着路径）1 轮5
5→6, 4→5, 3→4, 2→3, 1→2（逆着路径）5 轮（= n-1）5

顺着扫时，一轮之内信息就能一路传到链尾；逆着扫时每轮只往前挪一条边。所以：最坏是 n-1 轮，别指望它总是快；而 if (!changed) break; 这个提前退出，在多数图上能省掉大量无用轮次。

复杂度 O(n·m)。用 300 组随机小图（点数 4-7、边权 -5…7，含负权、剔除含负环的）与 Floyd 交叉验证：可比 73 组全部一致，0 组不一致（另外 227 组因为含负环被跳过）。

3. 负环检测：第 n 轮还能松弛，就说明有负环

沿着上面的思路再推一步。既然 n-1 轮足以求出所有最短路，那么第 n 轮还能把某个点改小，只能意味着一件事：存在一条「边权和为负的回路」，可以无限绕圈、永远更便宜 —— 这就是负环。

检测代码就是上面那份的第 n 轮那三行：

for (auto& e : edges)
    if (dis[e.u] != INF && dis[e.u] + e.w < dis[e.v]) return false;   // 有负环
P3385 的原话是「从顶点 1 出发能到达的负环」，不是「图里有没有负环」。
所以那个 dis[e.u] != INF（continue 那一行）不能省：不可达的点本来就等于没被松弛过，不筛掉就会把「另一个连通块里的负环」也算进来，答案直接错。

实测两种判据在两张图上的表现 —— 完全一致：

图Bellman-Ford 第 n 轮SPFA 计数法
A：环 2→3→2，权 1 + (-3) = -2，从 1 可达YESYES
B：同一个环搬到 5、6，从 1 不可达NONO

4. SPFA：Bellman-Ford 的队列版

回头看 Bellman-Ford：每一轮它把所有边都扫一遍，可一轮里真正能引起变化的，只有「刚刚被改小」的那些点的出边。其余的点全是白扫。

那就用队列记下「哪些点刚变过，值得去松弛它的邻居」：

struct Arc { int to, w; };
vector<vector<Arc>> adj;      // 邻接表

// 返回 true = 没有负环
bool spfa(int s, vector<int>& dis) {
    dis.assign(n + 1, INF);
    vector<int> cnt(n + 1, 0);          // cnt[v]：当前这条最短路用了多少条边
    vector<bool> inq(n + 1, false);     // 是否已在队列里（避免重复入队）
    deque<int> q;
    dis[s] = 0; q.push_back(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop_front(); inq[u] = false;
        for (auto& a : adj[u]) {
            if (dis[u] + a.w < dis[a.to]) {
                dis[a.to] = dis[u] + a.w;
                cnt[a.to] = cnt[u] + 1;
                if (cnt[a.to] >= n) return false;      // 走了 n 条边还在变短 → 负环
                if (!inq[a.to]) { q.push_back(a.to); inq[a.to] = true; }
            }
        }
    }
    return true;
}

负环判据换了个说法：一条最短路如果用了 ≥ n 条边，就必然重复经过了某个点 —— 也就是绕了一个负环。（另一种等价写法是统计「入队次数 ≥ n」，效果一样。）

SPFA 到底快不快：三组实测

图堆优化 DijkstraSPFA结论
随机稀疏：n = 105、m = 3×10515.3 ms6.2 msSPFA 快 2.5×（两边答案完全一致）
网格 400×400（16 万点 / 63.84 万条有向边）19.9 ms52.0 msSPFA 慢 2.6×（就是它被卡的那种图）
P3385 规模：T = 10、n = 2000、m = 3000——60.9 ms同规模下 Bellman-Ford 48.6 ms，反而更快

三行数据连起来就是一句话：SPFA 是「平均很快」，不是「很快」。它的最坏复杂度仍是 O(n·m)，出题人只要造一张网格图或特殊构造的图，就能让它退化。P4779 的题目背景讲的就是这件事（那位同学用 SPFA 交了 60 分）。

所以怎么用：能用 Dijkstra 就用 Dijkstra（非负权时它稳定 O(m log m)）。SPFA 的价值在负权 + 单源，以及作为负环检测的顺手工具。

5. Floyd：一次算出所有点对的距离

前面三个都是「单源」：一个起点，算出它到所有点的距离。如果题目要问任意两点之间的距离，而且 n 不大，那就用它 —— 代码五行：

for (int k = 1; k <= n; k++)          // 中转点，必须最外层
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (f[i][k] + f[k][j] < f[i][j])
                f[i][j] = f[i][k] + f[k][j];

它其实是一个三维 DP：f[k][i][j] = 「只允许把 1…k 这些点当中转点，i 到 j 的最短路」。k 是 DP 的阶段，所以滚动成二维数组之后，k 那一层必须留在最外面。

顺序一换就出错（实测）

图：1→3 (1)、3→2 (1)、2→4 (1)、1→4 (10)，真值 d(1,4) = 1+1+1 = 3。三种循环顺序各跑一遍：

循环顺序算出的 d(1,4)结果
(k, i, j)：k 最外层（教科书写法）3正确
(i, k, j)：k 挪到中间10错
(i, j, k)：k 放最内层3正确

在这张图上，中间那种写法把答案算成了 10 —— 因为轮到它处理 (i=1, j=4) 时，f[1][3] 还没被算出来，等它算出来时那个 k 已经过去了。

这张实验同时说明另一件事：顺序错误不一定在每组数据上都暴露（同一程序在 1→2→3→4 那条链上三种顺序都对）。所以不要靠「我这样写也过了」来判断 —— 背下 k 在最外层。

INF 的坑：INT_MAX 会溢出（实测）

如果图里有不可达的点对，Floyd 也要跟 INF 打交道。同一张图（只有 2→3 一条边、1 号孤立）三种写法实测：

写法f[1][2]f[1][3]该有的值
INF = INT_MAX，不判断214748363721474836312147483647（不可达）
INF = 0x3f3f3f3f，不判断10611095671061109567
INF = INT_MAX + >= INF 判断21474836472147483647

第一行就是经典溢出：INF + INF 溢出成负数，比 f[i][j] 还小，于是「不可达」被写成了一个奇怪的巨大值。第二行侥幸没事，是因为 2 × 0x3f3f3f3f 还没溢出 int —— 所以用 0x3f3f3f3f 当 INF，或者老老实实加上判断，两者选一个。

复杂度与适用范围

n运算次数实测耗时二维数组内存
3002.7×10717.9 ms≈ 0.36 MB
1000109462.8 ms≈ 4 MB
20008×109约 3.7 秒（按上面的比例外推）≈ 16 MB

结论：n 在 500 以内、又需要多源或稠密图时用 Floyd；n 上千就别想了。
负权它也吃得下（这正是它的长处）。判负环也顺手：跑完之后只要有任何 f[i][i] < 0，就存在负环 —— 注意 Floyd 判的是「全图」，不区分是否从某个起点可达。

6. 四种算法怎么选

情形用什么复杂度
单源、边权全部非负堆优化 Dijkstra（0411）O(m log m)
单源、有负权、n·m 不大Bellman-FordO(n·m)
单源、有负权、想赌它快SPFA（会被卡）平均快，最坏 O(n·m)
要判负环Bellman-Ford 第 n 轮 / SPFA 计数同上
多源（任意两点），n ≤ 500FloydO(n3)

7. P3385 专项：坑全在「怎么读入」

题面的读入规则（这是本题最大的坑）
每行 u v w：若 w ≥ 0，表示 u→v 和 v→u 两条边都存在、权都是 w；若 w < 0，只有 u→v 一条边。
所以题面那句提示是真的：m 不是图的边数 —— 邻接表要按情况 push 一次或两次，用边数组的话要开 2m。

完整解法（原样编译运行过；另外用 300 组随机 P3385 格式数据与一份独立的 Floyd 判环脚本对拍，0 组不一致）：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d %d", &n, &m);
        vector<vector<pair<int,int>>> adj(n + 1);      // 每组重新建，天然清空
        for (int i = 0; i < m; i++) {
            int u, v, w; scanf("%d %d %d", &u, &v, &w);
            if (w >= 0) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); }
            else         { adj[u].push_back({v, w}); }      // 负权只有单向
        }

        const int INF = 1e9;
        vector<int> dis(n + 1, INF), cnt(n + 1, 0);
        vector<bool> inq(n + 1, false);
        deque<int> q;
        dis[1] = 0; q.push_back(1); inq[1] = true;

        bool has = false;
        while (!q.empty() && !has) {
            int u = q.front(); q.pop_front(); inq[u] = false;
            for (auto& e : adj[u]) {
                if (dis[u] + e.second < dis[e.first]) {
                    dis[e.first] = dis[u] + e.second;
                    cnt[e.first] = cnt[u] + 1;
                    if (cnt[e.first] >= n) { has = true; break; }
                    if (!inq[e.first]) { q.push_back(e.first); inq[e.first] = true; }
                }
            }
        }
        puts(has ? "YES" : "NO");
    }
    return 0;
}

用这组输入实测（两组数据，按题面规则手推的结果是 NO 然后 YES，程序输出完全一致）：

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

NO
YES

第一组三个非负权各自是双向边，环 1→3→1 是 4 + (-3) = 1，1→2→3→1 是 0，都不是负的 → NO。第二组 1→2→3→1 = 3 + 4 + (-8) = -1 < 0 → YES。

卡住时的自查顺序
① w ≥ 0 的行是不是只 push 了一次？（要 push 两次）
② 多测：dis / cnt / inq / 邻接表是不是每组都重建？
③ 判据用的是 cnt[v] >= n 还是不小心的 > n？
④ 负环是不是限定「从 1 可达」？（不可达的负环要输出 NO）
⑤ 队列里同一个点重复入队了吗？（inq 没判会变慢，但不会错）
⑥ 还不对就把代码贴过来，我按行给你看

8. 坑点清单

9. 小测

Q1. Dijkstra 在负权图上出错，根本原因是什么？
Q2. Bellman-Ford 为什么松弛 n-1 轮就够了？
Q3. 第 n 轮还能松弛某个点的距离，说明什么？
Q4. Floyd 的三重循环里，k 为什么必须在最外层？
Q5. SPFA 的时间复杂度应该怎么说才准确？
Q6. P3385 里 w ≥ 0 的一行代表什么？

10. 动手练习

  1. P3385 【模板】负环 —— 主战场。n ≤ 2000、m ≤ 3000、T ≤ 10、|w| ≤ 104。三个必须自己踩一遍的点：① w ≥ 0 要加双向边（这是题面最大的坑）；② 多测，每组都要重建 dis / cnt / inq / 邻接表；③ 只判「从 1 可达」的负环。SPFA 或 Bellman-Ford 都能过（实测两者都在 60 ms 内）。
  2. 选做（推荐做）：把 P4779 用 SPFA 交一次 —— 你已经用堆优化 AC 过它了。用 SPFA 再交一遍，看看是不是真的被卡（P4779 的题目背景就是这个）。这件事花 10 分钟，换来的印象比看十篇「SPFA 已死」的帖子深得多。
卡住时的自查顺序
  1. 先对一遍上面第 7 节那 6 条：w ≥ 0 有没有加双向边、多测有没有重建、cnt 判据是不是 >= n、负环有没有限定「从 1 可达」。
  2. 再手推一组最小输入（两三个点、一条负边），先写出你预期的输出，再跑程序对。
  3. 还不对就把代码贴过来，我按行给你看 —— 不过按规矩，我会先让你猜「这组输入应该输出什么」。

本课小结

下一课预告
0413 最小生成树 —— 把图里的边挑出一部分，让整张图连通、总代价最小。Kruskal（0410 的并查集 + 0407 的排序，直接拼起来）和 Prim（0411「每次挑最近的」思路换个场景）。配题 P3366。今天这节的「松弛」和 0410 的「并查集」会在那里各用一次。
这一课的代码都真的编译跑过了：三个模板零警告编译通过，负权反例、负环可达性、Floyd 顺序与 INF 溢出都是本机实测输出，P3385 解法另外用 300 组随机数据与一份独立的 Floyd 判环脚本对拍（0 组不一致）。哪一句看不懂 —— 比如 deque 和 queue 有什么区别、cnt 为什么能判负环、Floyd 的 DP 阶段是什么 —— 直接问我，我从零再讲一遍。

← 上一课：最短路 I：Dijkstra · 课程对照表

书籍 《算法 (第4版)》第 4.4 节（含负权边与负环）· 《算法导论》第 24 章（单源最短路径）与第 25 章（所有结点对）

在线 OI-Wiki · 最短路 · 洛谷 P3385 负环

← 上一课：最短路 I（Dijkstra） 下一课：0413 最小生成树（Kruskal / Prim）（待学）