图论算法：生成树与最短路径

9.1 统一约定与贯穿全章的示例图

9.1.1 四个统一约定

图论算法的细节特别容易被「下标从 0 还是从 1 开始」「有向还是无向」「边权能不能为负」这类约定搞乱。 为了避免你在本章里反复切换脑子，我们先一次性把约定钉死，全章不再变：

9.1.2 两种存储结构的代码骨架

后面所有算法的代码都建立在这两个骨架之上。链式前向星的名字听起来吓人，其实就是 「用数组模拟链表」：head[u] 指向顶点 u 的第一条边，每条边记录 to（终点）、w（权值）、nxt（同起点的下一条边）， 插入时用头插法。它比 vector<vector<Edge>> 更快、更省内存， 是算法竞赛的标准写法。

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

const int MAXN = 1005;          // 最大顶点数
const int MAXM = 200005;        // 最大边数（无向图要开 2 倍）
const int INF  = 0x3f3f3f3f;    // 1e9 级别，"无穷大"的安全取值

int n, m;                       // n 个顶点（0 ~ n-1），m 条边
int g[MAXN][MAXN];              // ① 邻接矩阵：g[u][v] = 边权，无边为 INF

/* ② 链式前向星：数组模拟邻接表 */
int head[MAXN], etot = 0;       // head[u] = 顶点 u 的第一条边的下标，-1 表示没有
struct Edge {
    int to, w, nxt;             // 终点、边权、同起点的下一条边
} e[MAXM];

void init() {
    memset(g, 0x3f, sizeof(g));                 // 邻接矩阵全部置为 INF
    for (int i = 0; i < n; i++) g[i][i] = 0;
    memset(head, -1, sizeof(head));
    etot = 0;
}

/* 加一条 u -> v 权值为 w 的有向边（无向图调用两次即可） */
void addEdge(int u, int v, int w) {
    e[etot] = {v, w, head[u]};
    head[u] = etot++;
}

/* 遍历顶点 u 的所有出边：这是链式前向星唯一需要背下来的循环 */
void traverse(int u) {
    for (int i = head[u]; i != -1; i = e[i].nxt) {
        int v = e[i].to, w = e[i].w;
        // 在这里处理边 (u, v, w)
    }
}

int main() {
    n = 7; m = 11;
    init();
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < m; i++) {
        int u = E[i][0], v = E[i][1], w = E[i][2];
        g[u][v] = g[v][u] = w;          // 无向图：矩阵对称
        addEdge(u, v, w); addEdge(v, u, w);
    }
    cout << "n = " << n << ", m = " << m << ", etot = " << etot << "\n";
    cout << "g[0][1] = " << g[0][1] << ",  g[0][4] = " << (g[0][4] == INF ? -1 : g[0][4]) << "\n";
    return 0;
}

9.1.3 贯穿全章的示例图 G

下面这张图是本章的「主角」：7 个顶点、11 条带权无向边，权值全是正整数。 它规模不大，手推得动；又足够「有故事」——既有等权边（可以造出多个不同的最小生成树）， 又有「直连不如绕路」（比如 0 到 6 直连是 11，绕 0→1→2→6 只要 7）， 所以我们能用同一张图把 Prim、Kruskal、Dijkstra、Floyd 全部演一遍。 请把它抄到草稿纸上，后面每张手推表都对着它看。

把这张图整理成两种存储结构，就是下面这样（后文所有代码都用这两张表初始化）：

9.2 最小生成树（MST）：把图连通得最便宜

9.2.1 生成树与最小生成树的定义

生成树（spanning tree）：连通无向图 G 的一个子图，它包含 G 的全部 n 个顶点， 并且恰好有 n−1 条边、本身是一棵树（连通且无环）。 一个连通图的生成树一般不止一棵，比如一个三角形（3 个顶点 3 条边）就有 3 棵生成树。

最小生成树（Minimum Spanning Tree, MST）：在带权连通无向图中， 边权总和最小的那棵生成树。注意三个前提：

• 连通：不连通就谈不上「生成树」，只能求「最小生成森林」（每个连通块各求一棵 MST）。
• 无向：有向图对应的是「最小树形图（朱刘算法）」，那是另一个话题。
• 带权：权值可以理解为造价、距离、时间，目标就是总代价最小。

现实中的原型非常多：用最少的网线把 n 个城市连起来、用最短的线路给一片小区供气、 电路板上用最少的铜箔连通所有焊点……只要满足「连通所有点 + 总代价最小」，就是 MST 问题。

9.2.2 MST 的两条性质：割性质与环性质

Prim 和 Kruskal 表面上差别很大（一个长点、一个长边），但它们背后站的是同一条定理。 理解了这条定理，你就知道这两个算法不是碰巧对，而是必然对。

把这两条性质对着示例图 G 用一遍，你立刻就能「不跑算法」判断出一些边的命运：

• 环 0–1–2–0 的三条边是 2、2、3。最大的是 (0,2) 权 3，所以(0,2) 不在任何 MST 中。这解释了为什么 Kruskal 在第 4 条边就把它丢掉。
• 环 1–2–6–4–3–1 …… 直接看环 2–6–4–3–1–2？其实不用绕这么远：环 0–1–2–6–0 的边为 2、2、4、11，最大的是 (0,6) 权 11，所以 (0,6) 不在 MST 中。
• 环 1–3–5–1 的边为 5、5、6，最大的是 (1,5) 权 6 —— 但注意这一轮里 5 与 5 并列最小，所以 (1,3) 或 (3,5) 谁进 MST 都可以，但 (1,5) 一定不进。

9.2.3 Prim 算法：一个顶点一个顶点地「长大」

一句话本质

把生成树想象成一个正在扩张的「国家」，树外的顶点是「邻国」。每个邻国都有一个「到该国的最短代价」 lowcost[i]，还有一个「是通过哪座城市连过去的」closest[i]。 每一轮，Prim 挑 lowcost 最小的邻国吞并，然后用新吞并的城市去更新其它邻国的代价。 整个过程其实就是 9.2.2 的割性质：已入树的点集 S 与树外的点集 V−S 构成一个割， 而 lowcost 最小的那个邻国对应的边，正是这个割的最小割边。

算法流程（4 步）

1. 初始化：任选一个起点 s，令 lowcost[s] = 0（其它为 ∞）， lowcost[i] = w(s,i)（不可达则 ∞），closest[i] = s，标记 visited[s] = true。
2. 选点：在 visited = false 的顶点中，找 lowcost 最小的顶点 k。若 lowcost[k] == ∞， 说明图不连通，算法结束。否则把 k 加入生成树，边 (closest[k], k) 入选，visited[k] = true。
3. 松弛：对 k 的每个未访问邻接点 j，若 w(k,j) < lowcost[j]， 则 lowcost[j] = w(k,j)、closest[j] = k。 注意这条式子左边是「到树的距离」，右边是「一条边的权」——不需要累加，因为只要接到树上就只花一条边的代价。
4. 重复第 2、3 步 n−1 次，得到 n−1 条边，即最小生成树。

完整手推过程（以示例图 G 为例，从顶点 0 出发）

下表是 408 最常考的形式：每一轮记录 lowcost[]、closest[]、选中的顶点、加入的边与当前总权值。 「∞」表示当前还够不着。灰色的格子表示该顶点已经进树了。请务必自己动手抄一遍、遮住答案推一遍。

下面这个动画把上面的表格逐步演一遍，注意观察橙色候选格与绿色已入树的边：

Prim 朴素版 O(n²)：邻接矩阵实现

朴素版的复杂度由「找最小值」这一动作决定：每轮扫一遍 lowcost 数组 O(n)， 共 n 轮，所以是 O(n²)；松弛操作总共 O(m)。当图很稠密（m 接近 n²）时， O(n²) 反而比 O(m log n) 更优——这就是 Prim 适合稠密图的原因。

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

const int MAXN = 1005;
const int INF  = 0x3f3f3f3f;

int n, m;
int g[MAXN][MAXN];      // 邻接矩阵，无边为 INF
int lowcost[MAXN];      // lowcost[i]：顶点 i 到当前生成树的最小边权
int closest[MAXN];      // closest[i]：上面那条边在树内的那一个端点
bool vis[MAXN];         // 是否已加入生成树

/* 返回最小生成树的权值和；图不连通时返回 -1
   时间复杂度 O(n^2)，与边数 m 无关 —— 适合稠密图 */
int prim(int start) {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++) {
        lowcost[i] = g[start][i];
        closest[i] = start;
    }
    vis[start] = true;
    lowcost[start] = 0;

    int sum = 0, cnt = 0;
    for (int round = 1; round < n; round++) {
        /* 第 2 步：在未入树的顶点中找 lowcost 最小的 */
        int k = -1, best = INF;
        for (int i = 0; i < n; i++) {
            if (!vis[i] && lowcost[i] < best) { best = lowcost[i]; k = i; }
        }
        if (k == -1) return -1;                 // 图不连通
        vis[k] = true;
        sum += lowcost[k];
        cnt++;
        printf("第 %d 轮：加入顶点 %d，边 (%d,%d) 权 %d，累计 %d\n",
               round, k, closest[k], k, lowcost[k], sum);

        /* 第 3 步：用新顶点 k 去松弛其它未入树的点 */
        for (int j = 0; j < n; j++) {
            if (!vis[j] && g[k][j] < lowcost[j]) {
                lowcost[j] = g[k][j];           // 只取一条边的权，不累加！
                closest[j] = k;
            }
        }
    }
    return cnt == n - 1 ? sum : -1;
}

int main() {
    n = 7; m = 11;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < n; i++) g[i][i] = 0;
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < m; i++) {
        int u = E[i][0], v = E[i][1], w = E[i][2];
        g[u][v] = g[v][u] = w;
    }
    printf("MST 总权值 = %d\n", prim(0));
    return 0;
}

Prim 堆优化版 O(m log n)：链式前向星 + priority_queue

朴素版的瓶颈在「每轮扫一遍数组找最小」，这是 O(n²)。用一个小根堆维护候选边， 就能把每次找最小降到 O(log m)。总复杂度 O(m log m) = O(m log n)（因为 m ≤ n²，log m ≤ 2 log n）。 在稀疏图上这比 O(n²) 快得多。

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

const int MAXN = 100005;
const int MAXM = 400005;
const int INF  = 0x3f3f3f3f;

int n, m;
int head[MAXN], etot = 0;
struct Edge { int to, w, nxt; } e[MAXM];
void addEdge(int u, int v, int w) { e[etot] = {v, w, head[u]}; head[u] = etot++; }

bool vis[MAXN];
int dist_[MAXN];                 // 各顶点到「已选点集」的最小边权

/* 堆里存 pair<边权, 顶点>，按第一关键字排序 ⇒ 小根堆 */
int prim(int s) {
    memset(vis, 0, sizeof(vis));
    memset(dist_, 0x3f, sizeof(dist_));
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    dist_[s] = 0;
    pq.push(make_pair(0, s));

    int sum = 0, cnt = 0;
    while (!pq.empty()) {
        pair<int,int> t = pq.top(); pq.pop();
        int d = t.first, u = t.second;
        if (vis[u]) continue;               // 过期元素：这个点早就进树了，跳过
        vis[u] = true;
        sum += d; cnt++;
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (!vis[v] && w < dist_[v]) {  // 同样是「一条边的权」，不累加
                dist_[v] = w;
                pq.push(make_pair(w, v));
            }
        }
    }
    return cnt == n ? sum : -1;
}

int main() {
    n = 7;
    memset(head, -1, sizeof(head));
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < 11; i++) {
        addEdge(E[i][0], E[i][1], E[i][2]);
        addEdge(E[i][1], E[i][0], E[i][2]);     // 无向边存两次
    }
    printf("堆优化 Prim：MST 总权值 = %d\n", prim(0));
    return 0;
}

9.2.4 Kruskal 算法：按边权从小到大「能用就用」

一句话本质

Kruskal 的思路比 Prim 更「朴素」：既然要总权最小，那就从最便宜的边开始买。 但便宜边可能连的是已经连通的两个点，硬加进去就成环了，而生成树不允许有环 —— 于是丢弃。 这个「判断两端点是否已连通」的动作，正好是并查集（Disjoint Set Union, DSU）的拿手好戏： 查询与合并几乎都是 O(1)。

并查集：Kruskal 的心脏

并查集维护若干个不相交的集合，支持两种操作： find(x) 返回 x 所在集合的「代表元（树根）」， union(x,y) 把两个集合合并。两个优化是它的精髓：

• 路径压缩（path compression）：find 时把沿途所有结点直接挂到根上， 下次查询就是 O(1)。写法就是递归里的 fa[x] = find(fa[x])。
• 按秩合并（union by rank/size）：合并时把「矮树」挂到「高树」下， 避免树退化成链。用 siz[] 或 rank[] 记录。

两个优化一起用，单次操作的均摊复杂度是 O(α(n))，其中 α 是反阿克曼函数， 在 n 取到宇宙原子总数级别时也不超过 4 —— 工程上直接当成常数。

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

const int MAXN = 100005;
int fa[MAXN], rnk[MAXN];        // fa: 父指针；rnk: 秩（树高上界）

void dsuInit(int n) {
    for (int i = 0; i < n; i++) { fa[i] = i; rnk[i] = 0; }
}

/* 路径压缩：递归写法最简洁；写成非递归可避免深递归爆栈 */
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);         // 关键：顺手把 x 挂到根上
}

/* 按秩合并：返回是否真的合并了（false 表示原本就在同一集合） */
bool unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;         // 同集合，不需要合并
    if (rnk[rx] < rnk[ry]) swap(rx, ry);   // 让 rx 成为较高的那棵
    fa[ry] = rx;
    if (rnk[rx] == rnk[ry]) rnk[rx]++;
    return true;
}

/* 批量合并的标准写法：第一遍只查根（不修改树），第二遍才真正挂接。
   这样 rank 的比较用的都是合并前的真实树高，按秩合并才真正有效。 */
bool uniteAll(int (*edges)[2], int cnt) {
    int rx[MAXN], ry[MAXN];
    for (int i = 0; i < cnt; i++) {
        int a = find(edges[i][0]), b = find(edges[i][1]);
        if (a != b) { rx[i] = a; ry[i] = b; } else { rx[i] = ry[i] = -1; }
    }
    bool any = false;
    for (int i = 0; i < cnt; i++) {
        if (rx[i] < 0) continue;
        int ra = find(rx[i]), rb = find(ry[i]);   // 可能已被前几次合并影响，需重新查根
        if (ra == rb) continue;
        if (rnk[ra] < rnk[rb]) swap(ra, rb);
        fa[rb] = ra;
        if (rnk[ra] == rnk[rb]) rnk[ra]++;
        any = true;
    }
    return any;
}

/* 更朴素的按大小合并版本（等价，且不用处理 rnk 的细节） */
int siz[MAXN];
void dsuInit2(int n) { for (int i = 0; i < n; i++) { fa[i] = i; siz[i] = 1; } }
bool unite2(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;
    if (siz[rx] < siz[ry]) swap(rx, ry);   // 小集合挂到大集合上
    fa[ry] = rx; siz[rx] += siz[ry];
    return true;
}

int main() {
    dsuInit(7);
    /* 依次加入 Kruskal 选中的边，观察集合变化 */
    int pick[6][2] = {{0,1},{1,2},{3,4},{0,3},{2,6},{3,5}};
    for (int i = 0; i < 6; i++) {
        bool ok = unite(pick[i][0], pick[i][1]);
        printf("合并 (%d,%d) ？ %s   集合根：", pick[i][0], pick[i][1], ok ? "成功" : "已在同一集合");
        for (int v = 0; v < 7; v++) printf("%d ", find(v));
        printf("\n");
    }
    /* 再试一条会成环的边 */
    printf("尝试 (0,2)：%s\n", unite(0, 2) ? "合并成功" : "两端已连通 → 丢弃");
    return 0;
}

Kruskal 手推过程表（同一个示例图 G）

Kruskal 的第一步是排序，这一步本身就是考点。排序后的边序列（权值相同时按端点编号排）：

第 7 条边 (1,3) 被丢弃的原因值得说清楚：此时 1 已在集合 {0,1,2,3,4,6} 中（路径 1–0–3 已经连通）， 3 也在同一个集合里，再加上 (1,3) 就形成了环 1–0–3–1。 丢弃的判据永远只有一个：两端点 find 的结果是否相同。

下面动画把每一条边的判定过程演一遍，注意右侧并查集集合的变化：

Kruskal 完整实现 O(m log m)

复杂度由排序主导：排序 O(m log m)，并查集部分 O(m α(n))，合计 O(m log m)。 与顶点数 n 关系不大，只看边数 —— 所以 Kruskal 适合稀疏图。

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

const int MAXN = 100005;
const int MAXM = 200005;

int n, m;
int fa[MAXN], siz[MAXN];

int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }
bool unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;
    if (siz[rx] < siz[ry]) swap(rx, ry);
    fa[ry] = rx; siz[rx] += siz[ry];
    return true;
}
void dsuInit() { for (int i = 0; i < n; i++) { fa[i] = i; siz[i] = 1; } }

struct Edge { int u, v, w; };
Edge e[MAXM];

bool cmp(const Edge& a, const Edge& b) {
    if (a.w != b.w) return a.w < b.w;       // 先按权值升序
    if (a.u != b.u) return a.u < b.u;       // 权值相同按端点编号（让结果可复现）
    return a.v < b.v;
}

/* 返回最小生成树权值和；图不连通时返回 -1（此时得到的是最小生成森林） */
int kruskal() {
    sort(e, e + m, cmp);
    dsuInit();
    int sum = 0, cnt = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        if (unite(e[i].u, e[i].v)) {        // 不同集合 → 采纳
            sum += e[i].w; cnt++;
            printf("采纳第 %d 条边 (%d,%d) 权 %d，累计 %d\n", i + 1, e[i].u, e[i].v, e[i].w, sum);
        } else {
            printf("丢弃第 %d 条边 (%d,%d) 权 %d：两端已连通，会成环\n", i + 1, e[i].u, e[i].v, e[i].w);
        }
    }
    return cnt == n - 1 ? sum : -1;
}

int main() {
    n = 7; m = 11;
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < m; i++) e[i] = {E[i][0], E[i][1], E[i][2]};
    printf("MST 总权值 = %d\n", kruskal());
    return 0;
}

9.2.5 Prim vs Kruskal：怎么选

9.3 最短路径（一）：Dijkstra 单源最短路

9.3.1 问题定义与「松弛」的本质

单源最短路径（Single Source Shortest Path, SSSP）：给定带权图和源点 s， 求 s 到其余每个顶点的最短路径长度 dist[]。 注意「最短」指的是路径上所有边权之和最小，而不是边数最少。

所有最短路算法都建立在同一个动作之上：松弛（relaxation）。 它只有一行：

为什么松弛是对的？用一句直观的话说： 「如果你已经知道到 u 的最短路长度是 dist[u]，那么从 u 再走一条权为 w 的边到 v， 就得到了一条到 v 的长度为 dist[u]+w 的候选路线；既然是个候选，就该和现有的最好成绩比一比，谁小留谁。」
严谨一点的说法：设 s→v 的真实最短路径最后一条边是 (u,v)，那么这条路径的前半段必然是 s→u 的最短路径 （否则换掉前半段能得到更短的 s→v 路径，矛盾）—— 这条「最优子结构」性质保证了 只要我们把每条边的两端都松弛到位，最终一定能算出所有最短路。 区别只在于：Dijkstra 用贪心决定「先松弛谁」，Bellman-Ford 无脑地把所有边松弛 n−1 轮。

9.3.2 算法流程与贪心前提

1. 初始化：dist[s] = 0，其余 dist[i] = ∞；visited[] 全为 false；pre[] 全为 −1。
2. 选点（贪心）：在 visited = false 的顶点中，选 dist 最小的那个顶点 u。
3. 确定：标记 visited[u] = true。此时 dist[u] 就永远定下来了，之后不再修改。
4. 松弛：对 u 的每个未确定邻接点 v，执行 dist[v] = min(dist[v], dist[u] + w(u,v))。
5. 重复 2~4 共 n 次（每次确定一个顶点）。若某轮选出的最小 dist 仍为 ∞，说明剩下的点都不可达，可以提前结束。

贪心前提（正确性根据）：为什么「当前 dist 最小的未确定顶点」一定已经是最优解？ 设选出的顶点是 u，dist[u] = d。假设真实最短路更短，那么存在一条从 s 到 u 的路径， 它必然要先经过某个「未确定」的顶点 x（因为所有已确定顶点的 dist 都是最终的）， 于是 dist[x] ≤ d（前缀长度不超过全路径长度，权值非负！）。 既然 u 是 dist 最小的未确定顶点，就有 dist[x] ≥ d，于是 dist[x] = d —— 那选 x 也一样， 不会得到更短的结果，矛盾。
看清最后一步用了什么：边的权值非负。如果允许负权，「前缀长度不超过全路径长度」就不再成立， 整个论证崩塌。这就是 Dijkstra 不能处理负权边的根本原因（详见 9.3.7）。

9.3.3 Dijkstra 手推过程表（考点中的考点）

以示例图 G 为例，从顶点 0 出发。每轮记录 dist[]、visited[]、 选中的顶点以及被松弛的边。表中加粗的数值表示本轮被更新。

下面动画逐轮演示选点与松弛，橙色表示本轮被更新的顶点：

9.3.4 朴素实现 O(n²)

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

const int MAXN = 1005;
const int INF  = 0x3f3f3f3f;

int n;
int g[MAXN][MAXN];
int dist_[MAXN];
bool vis[MAXN];
int pre[MAXN];                  // 记录前驱，用于路径还原

void dijkstra(int s) {
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    for (int i = 0; i < n; i++) dist_[i] = g[s][i];   // 邻接矩阵直接给出初始估计
    dist_[s] = 0; vis[s] = true;

    for (int round = 1; round < n; round++) {
        /* 选点：未确定顶点中 dist 最小的 */
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!vis[i] && (u == -1 || dist_[i] < dist_[u])) u = i;
        if (u == -1 || dist_[u] == INF) break;         // 剩下的都不可达
        vis[u] = true;
        /* 松弛：注意这里是 dist_[u] + g[u][v]，要累加！ */
        for (int v = 0; v < n; v++) {
            if (!vis[v] && g[u][v] < INF && dist_[u] + g[u][v] < dist_[v]) {
                dist_[v] = dist_[u] + g[u][v];
                pre[v] = u;
            }
        }
    }
}

int main() {
    n = 7;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < n; i++) g[i][i] = 0;
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < 11; i++) {
        g[E[i][0]][E[i][1]] = E[i][2];
        g[E[i][1]][E[i][0]] = E[i][2];
    }
    dijkstra(0);
    printf("dist = ");
    for (int i = 0; i < n; i++) printf("%d ", dist_[i]);
    printf("\n");
    return 0;
}

9.3.5 堆优化实现 O(m log n)

和 Prim 一样，瓶颈在「找最小值」。把候选的 (dist, v) 压进小根堆， 每轮取出堆顶即可。总复杂度 O(m log m)。 堆优化的 Dijkstra 必须用邻接表（链式前向星），否则光是遍历矩阵就是 O(n²)。

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

const int MAXN = 100005;
const int MAXM = 400005;
const int INF  = 0x3f3f3f3f;

int n, m;
int head[MAXN], etot = 0;
struct Edge { int to, w, nxt; } e[MAXM];
void addEdge(int u, int v, int w) { e[etot] = {v, w, head[u]}; head[u] = etot++; }

int dist_[MAXN];
bool vis[MAXN];
int pre[MAXN];

void dijkstra(int s) {
    memset(dist_, 0x3f, sizeof(dist_));
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));

    /* 小根堆：pair 默认按 first 比较，greater 让它变成小根堆 */
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    dist_[s] = 0;
    pq.push(make_pair(0, s));

    while (!pq.empty()) {
        pair<int,int> top = pq.top(); pq.pop();
        int d = top.first, u = top.second;
        if (vis[u]) continue;              // 过期元素：u 已经被确定过了，跳过
        vis[u] = true;
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (dist_[u] + w < dist_[v]) { // 这里是「累加」，与 Prim 不同！
                dist_[v] = dist_[u] + w;
                pre[v] = u;
                pq.push(make_pair(dist_[v], v));
            }
        }
    }
}

int main() {
    n = 7;
    memset(head, -1, sizeof(head));
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < 11; i++) {
        addEdge(E[i][0], E[i][1], E[i][2]);
        addEdge(E[i][1], E[i][0], E[i][2]);
    }
    dijkstra(0);
    printf("dist = ");
    for (int i = 0; i < n; i++) printf("%d ", dist_[i]);
    printf("\n");
    return 0;
}

9.3.6 路径还原：pre[] 数组

只求长度太浪费了 —— 只要在松弛成功时记下 pre[v] = u， 就能在算法结束后从终点一路往回退，把整条路径还原出来。 由于每个顶点最多有一个 pre，所有顶点连起来是一棵以源点为根的树， 称为最短路树（shortest path tree）。

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

const int MAXN = 1005;
const int INF  = 0x3f3f3f3f;

int n;
int g[MAXN][MAXN], dist_[MAXN], pre[MAXN];
bool vis[MAXN];

void dijkstra(int s) {
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    for (int i = 0; i < n; i++) {
        dist_[i] = g[s][i];
        if (i != s && g[s][i] < INF) pre[i] = s;   // 关键：一步可达的点，前驱就是 s
    }
    dist_[s] = 0; vis[s] = true;
    for (int r = 1; r < n; r++) {
        int u = -1;
        for (int i = 0; i < n; i++) if (!vis[i] && (u == -1 || dist_[i] < dist_[u])) u = i;
        if (u == -1 || dist_[u] == INF) break;
        vis[u] = true;
        for (int v = 0; v < n; v++)
            if (!vis[v] && g[u][v] < INF && dist_[u] + g[u][v] < dist_[v]) {
                dist_[v] = dist_[u] + g[u][v];
                pre[v] = u;                     // 关键：记下前驱
            }
    }
}

/* 迭代法还原路径：从 t 往前推，再反转。顺序 O(路径长度) */
vector<int> getPath(int s, int t) {
    vector<int> path;
    if (dist_[t] == INF) return path;            // 不可达
    for (int cur = t; cur != -1; cur = pre[cur]) path.push_back(cur);
    reverse(path.begin(), path.end());
    if (path.empty() || path[0] != s) return vector<int>();   // 保护
    return path;
}

/* 递归法还原路径（正序输出，思路更直观，但路径长时递归深度大） */
void printPath(int s, int t) {
    if (t == s) { printf("%d", s); return; }
    if (pre[t] == -1) { printf("不可达"); return; }
    printPath(s, pre[t]);
    printf(" -> %d", t);
}

int main() {
    n = 7;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < n; i++) g[i][i] = 0;
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < 11; i++) g[E[i][0]][E[i][1]] = g[E[i][1]][E[i][0]] = E[i][2];
    dijkstra(0);

    vector<int> p = getPath(0, 5);
    printf("0 到 5 的最短路径：");
    for (size_t i = 0; i < p.size(); i++) printf("%d%s", p[i], i + 1 < p.size() ? " -> " : "");
    printf("，长度 %d\n", dist_[5]);

    printf("递归输出 0 到 6："); printPath(0, 6); printf("，长度 %d\n", dist_[6]);
    return 0;
}

9.3.7 为什么 Dijkstra 不能处理负权边

这是 408 与面试的高频追问。答案分两层：一层是「贪心前提被破坏」的原理， 一层是「拿一个反例把它算错」的实证。两层都要会。

原理层：Dijkstra 每轮把 dist 最小的未确定顶点「永久锁定」，依据是 「它的 dist 不可能再变小了」。这个依据成立的前提是后面发现的任何绕行路径都不会更短， 而绕行路径 = 已在路上的长度 + 一条非负的边。一旦允许负权边， 「绕一圈回来反而更短」就出现了，被锁定的值可能是错的，而且错了还改不回来。

把上面这个反例完整地算一遍（四条有向边：0→1 权 1、0→2 权 2、2→1 权 −2、1→3 权 4，源点为 0）：

请特别注意第 3 轮那件事有多讽刺：算法确实「看见」了更短的路径（dist[1] 本可以降到 0）， 但它已经没有资格修改 dist[1] 了。更糟的是，错误的 dist[1] 早已在上一轮把 dist[3] 也带偏了 —— 一个被过早锁定的错误值，会沿着后续的松弛一路污染下去。

更极端的情形是「负权回路」：如果存在一个总权为负的环， 绕着它多走一圈总长度就更小，最短路径根本不存在（可以无限小）。 这种图上任何最短路算法都给不出有意义的结果，只能用 Bellman-Ford 把负环检测出来并报告。

9.3.8 与 BFS 求无权最短路的联系

回忆第 04 讲的 BFS：在无权图（或所有边权都为 1 的图）上， BFS 第一次访问到某个顶点时的层数，就是从源点到它的最短路径长度。 BFS 其实就是 Dijkstra 在「权值全为 1」时的特例：

顺带一提，还有一个「0-1 BFS」的经典技巧：如果边权只有 0 和 1， 把普通队列换成双端队列 deque（权 0 的边把新点压到队首，权 1 的压到队尾）， 就能在 O(n + m) 内求出最短路，比堆优化更快。它是 BFS 与 Dijkstra 之间的中间形态。

9.4 最短路径（二）：Floyd 全源最短路

9.4.1 全源最短路问题

Dijkstra 解决的是「一个源点到所有点」；如果要求「任意两点之间」的距离（全源最短路，All-Pairs Shortest Paths）， 最简单的做法是「对每个顶点跑一遍 Dijkstra」，复杂度 O(n·m log n)； 而 Floyd-Warshall 算法用三重循环、O(n³) 一次性求出所有点对的距离， 代码只有 5 行，是「短小精悍」的典范。

它的适用条件：允许有负权边，但不允许有负环（有负环时结果无意义，不过我们可以顺便检测出来）。

9.4.2 动态规划的思想：从 dp[k][i][j] 到二维滚动

先想一个「笨」但清晰的 DP。定义：

注意「只允许经过 ≤ k 的顶点中转」这句话的准确含义：路径的中间点只能从 {0,1,…,k} 里挑， 但起点 i 和终点 j 可以是任意顶点，而且路径的中间点允许重复经过编号更小的点。

考虑第 k 个中转点「用还是不用」，只有两种可能：

• 不用 k 中转：那路径的中间点都在 {0,…,k−1} 里，长度就是 dp[k−1][i][j]。
• 用 k 中转：路径形如 i → … → k → … → j，其中 i 到 k 的那段和 k 到 j 的那段， 中间点都只用 {0,…,k−1}（k 本身只作为端点出现一次），长度就是 dp[k−1][i][k] + dp[k−1][k][j]。

取两者较小值，得到状态转移方程：

边界（k = −1，即不允许任何中转）：dp[i][j] = w(i,j)，无边为 ∞，dp[i][i] = 0。 这正好就是邻接矩阵。

二维滚动（就地更新）：注意 k 这一维只依赖 k−1，所以可以把这一维省掉， 直接在邻接矩阵上原地更新：

但「省掉一维」是有条件的：k 必须放在最外层。下一小节专门讲这个坑。

9.4.3 为什么 k 必须在最外层（最经典的易错点）

为什么？回看状态方程：dp[k][i][j] 依赖的是 dp[k−1][i][k] 与 dp[k−1][k][j]， 这两个值必须在「处理 k 这一轮」时全部是已经算好的 k−1 轮结果。 省掉 k 维后，「k−1 轮的结果」和「k 轮的结果」共用同一块内存， 这就要求：当我们要用 dist[i][k] 和 dist[k][j] 时，它们必须还没有被本轮（k 轮）修改过。

把 k 放在最外层时，枚举到 (i,j) 时 dist[i][k] 与 dist[k][j] 长什么样？ dist[i][k] 的下标里有一维等于 k —— 它在「本轮」会不会被改？ 本轮所有更新都发生在 dist[k][*] 这一行与 dist[*][k] 这一列上， 而 dist[i][k] 恰好在第 k 列、dist[k][j] 恰好在第 k 行。 那不就正好被改了吗？关键在这里：第 k 行/列上的元素在本轮根本不会变小。 因为更新第 k 行需要 dist[k][k] + dist[k][j]，而 dist[k][k] = 0（无负环时）， 算出来等于 dist[k][j] 自身，不可能变小；第 k 列同理。 所以第 k 行、第 k 列在整个第 k 轮里保持的正是 k−1 轮的旧值 —— 滚动更新合法。

反过来，把 i 放在最外层（for i → for k → for j）会发生什么？

• 处理 i = 0 时，我们用 k = 3 去更新 dist[0][j]，这时 dist[3][j] 里的值 可能还只是「完全没有中转」的原始值（因为 i = 3 那一行还没轮到处理）， 甚至 dist[0][3] 自己都还没被 k = 1、k = 2 更新过。
• 结果就是：有些中转组合被漏掉了，最后得到的矩阵偏大，答案错误。
• 最直观的表现：算法跑完之后，矩阵还没有收敛—— 你再跑一遍三重循环，矩阵还会变小（正确的 Floyd 跑第二遍时矩阵不变，这是检验写法的土办法）。

一句话记忆法：「先放开中转点，再枚举起点终点」。 k 是「本轮新增的自由度」，必须作为最外层的一层「阶段」； i、j 只是同一阶段内的状态枚举，谁在外谁在内无所谓（但都必须在 k 里面）。

9.4.4 完整实现与手推矩阵变化

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

const int MAXN = 505;
const int INF  = 0x3f3f3f3f;

int n, m;
int dist_[MAXN][MAXN];      // 直接在邻接矩阵上滚动更新

void floyd() {
    for (int k = 0; k < n; k++)               // ① 中转点必须是最外层！
        for (int i = 0; i < n; i++)           // ② 起点
            for (int j = 0; j < n; j++)       // ③ 终点
                if (dist_[i][k] + dist_[k][j] < dist_[i][j])
                    dist_[i][j] = dist_[i][k] + dist_[k][j];
}

/* 常用小优化：跳过不可达的中转点，稀疏图上能省不少时间 */
void floyd_fast() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist_[i][k] == INF) continue;          // i 到不了 k，k 中转无意义
            int dik = dist_[i][k];
            for (int j = 0; j < n; j++)
                if (dik + dist_[k][j] < dist_[i][j])
                    dist_[i][j] = dik + dist_[k][j];
        }
    }
}

int main() {
    n = 4; m = 5;
    memset(dist_, 0x3f, sizeof(dist_));
    for (int i = 0; i < n; i++) dist_[i][i] = 0;
    int E[5][3] = {{0,1,1},{1,2,1},{2,3,1},{0,3,10},{1,3,4}};
    for (int i = 0; i < m; i++) {
        int u = E[i][0], v = E[i][1], w = E[i][2];
        dist_[u][v] = min(dist_[u][v], w);       // 重边取最小！
        dist_[v][u] = min(dist_[v][u], w);       // 无向图；有向图删掉这一行
    }
    floyd();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            printf("%4d", dist_[i][j] == INF ? -1 : dist_[i][j]);
        printf("\n");
    }
    return 0;
}

下面用贯穿全章的示例图 G 手推 Floyd 的完整矩阵变化（n = 7，k = 0..6）。 为了便于对照，我把每一轮的变化单独列一张表，加粗的格子是本轮被更新的元素。 （自己手推时不必写满 7 张表，写 2~3 张并说清「哪些格子会变」即可。）

k = −1（初始矩阵 = 邻接矩阵）：

k = 0（允许经过顶点 0 中转）——例如 dist[3][2] = min(∞, dist[3][0]+dist[0][2]) = 3+3 = 6；

k = 1（再允许顶点 1）——这一轮产生了 dist[0][5] = 2+6 = 8、dist[5][6] = 6+13 = 19 等；

k = 2（再允许顶点 2）——dist[0][6] 从 11 降到 3+4 = 7，「直连不如绕路」在这里第一次体现；

k = 3（再允许顶点 3）——dist[0][4] = 3+2 = 5，顶点 4 第一次变得可达；

k = 4（再允许顶点 4）——dist[3][6] 从 10 降到 2+5 = 7，dist[6][3] 对称更新；

k = 5（再允许顶点 5）与 k = 6（再允许顶点 6）——矩阵不再变化，算法收敛：

下面动画把 k = 0..6 的矩阵变化逐步演一遍，橙色格子是本轮被更新的元素：

9.4.5 Floyd 的扩展应用

① 传递闭包（可达性）

如果只关心「i 能不能到 j」而不关心距离，把 min / + 换成 或 / 与（逻辑运算），Floyd 就变成了传递闭包算法： reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])。 用 bitset 可以把内层循环压成 64 位一次运算，复杂度降到 O(n³/64)。

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

const int MAXN = 2005;
bitset<MAXN> reach_[MAXN];      // reach_[i] 的第 j 位为 1 表示 i 可达 j

/* 传递闭包：O(n^3 / 64)，n = 2000 时非常快 */
void transitiveClosure(int n) {
    for (int i = 0; i < n; i++) reach_[i][i] = 1;
    for (int k = 0; k < n; k++)                 // k 依然必须最外层
        for (int i = 0; i < n; i++)
            if (reach_[i][k])                   // 只有 i 能到 k，才需要并上 k 的后继
                reach_[i] |= reach_[k];
}

int main() {
    int n = 4;
    /* 有向图：0->1, 1->2, 2->3 */
    reach_[0][1] = 1; reach_[1][2] = 1; reach_[2][3] = 1;
    transitiveClosure(n);
    for (int i = 0; i < n; i++) {
        printf("从 %d 可达：", i);
        for (int j = 0; j < n; j++) if (reach_[i][j]) printf("%d ", j);
        printf("\n");
    }
    /* 输出：从 0 可达 0 1 2 3；从 1 可达 1 2 3；从 2 可达 2 3；从 3 可达 3 */
    return 0;
}

② 判断负环

Floyd 跑完之后，若存在某个 i 使得 dist[i][i] < 0，则图中存在负环， 而且这个负环是从 i 出发可以绕回来的。 原理：dist[i][i] 正常情况下应为 0（原地不动）， 如果它变成负数，说明找到了一条从 i 出发、绕一圈回到 i 且总权为负的路径。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505, INF = 0x3f3f3f3f;

int n, dist_[MAXN][MAXN];

/* 返回负环上的一个顶点编号，没有负环返回 -1 */
int findNegativeCycle() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist_[i][k] < INF && dist_[k][j] < INF &&
                    dist_[i][k] + dist_[k][j] < dist_[i][j])
                    dist_[i][j] = dist_[i][k] + dist_[k][j];

    for (int i = 0; i < n; i++)
        if (dist_[i][i] < 0) return i;          // 自己到自己变成负的 ⇒ 有负环
    return -1;
}

int main() {
    n = 3;
    memset(dist_, 0x3f, sizeof(dist_));
    for (int i = 0; i < n; i++) dist_[i][i] = 0;
    dist_[0][1] = 1; dist_[1][2] = -2; dist_[2][0] = -3;   // 环长 1-2-3 = -4 < 0
    int v = findNegativeCycle();
    if (v >= 0) printf("存在负环，经过顶点 %d，dist[%d][%d] = %d\n", v, v, v, dist_[v][v]);
    else        printf("无负环\n");
    return 0;
}

③ 最小环

最小环指图中总权最小的环。用 Floyd 求最小环是一个非常巧妙的技巧： 在「只允许 0..k−1 中转」的时刻，考虑一条边 (i,k)（或 (k,i)）加上 k→i 之间只经过 < k 的顶点的路径，就构成一个包含 k 的环， 取所有这样的环的最小值即可。

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

const int MAXN = 105;
const long long INF = 1e15;

int n, m;
long long g[MAXN][MAXN], dist_[MAXN][MAXN];

/* 无向图最小环：O(n^3) */
long long minCycle() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) dist_[i][j] = g[i][j];

    long long ans = INF;
    for (int k = 0; k < n; k++) {
        /* 此时 dist_[i][j] 只允许经过 0..k-1 中转 ⇒ i-j-k-i 构成一个环 */
        for (int i = 0; i < k; i++)
            for (int j = i + 1; j < k; j++)
                if (dist_[i][j] < INF && g[j][k] < INF && g[k][i] < INF)
                    ans = min(ans, dist_[i][j] + g[j][k] + g[k][i]);
        /* 再用 k 去松弛，进入下一轮 */
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist_[i][k] + dist_[k][j] < dist_[i][j])
                    dist_[i][j] = dist_[i][k] + dist_[k][j];
    }
    return ans;
}

int main() {
    n = 4; m = 5;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) g[i][j] = (i == j ? 0 : INF);
    int E[5][3] = {{0,1,3},{1,2,4},{2,3,5},{3,0,6},{0,2,20}};
    for (int i = 0; i < m; i++) {
        int u = E[i][0], v = E[i][1], w = E[i][2];
        g[u][v] = g[v][u] = min(g[u][v], (long long)w);   // 重边取最小
    }
    long long ans = minCycle();
    printf("最小环长度 = %lld\n", ans);
    /* 环 0-1-2-3-0 长度 3+4+5+6 = 18，是最小环 */
    return 0;
}

④ 字典序最小的最短路径

Floyd 的另一个好处是「顺手记路径」：加一个 nxt[i][j] 记录 i→j 最短路上 i 的下一跳。 初始化 nxt[i][j] = j（有边时）；当用 k 更新成功时令 nxt[i][j] = nxt[i][k]。 如果要字典序最小，把更新条件写成 「dist 更小，或者 dist 相等但新路径的下一跳编号更小」即可。 注意 Dijkstra 不能这么干（等值时它不会回头改路径），所以「最短路 + 字典序最小」通常用 Floyd。

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

const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int n, dist_[MAXN][MAXN], nxt[MAXN][MAXN];

void floydLex() {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) {
            if (dist_[i][k] == INF) continue;
            for (int j = 0; j < n; j++) {
                if (dist_[k][j] == INF) continue;
                int nd = dist_[i][k] + dist_[k][j];
                /* ① 更短；或 ② 一样长但「下一跳」更小（字典序更优）。
                   注意条件里比较的是 k（新的下一跳就是 nxt[i][k]），不能写成 nxt[i][j] 自己，
                   否则等长时永远不会更新，路径也无法变短，还可能死循环。 */
                if (nd < dist_[i][j] || (nd == dist_[i][j] && k < nxt[i][j])) {
                    dist_[i][j] = nd;
                    nxt[i][j] = (i == k) ? j : nxt[i][k];
                }
            }
        }
}

/* 输出 i 到 j 的完整路径 */
void printPath(int i, int j) {
    if (dist_[i][j] == INF || nxt[i][j] == -1) { printf("不可达\n"); return; }
    printf("%d", i);
    int cur = i, guard = 0;
    while (cur != j && guard++ <= n) {       // guard 防止意外死循环
        cur = nxt[cur][j];
        printf(" -> %d", cur);
    }
    printf("\n");
}

int main() {
    n = 4;
    memset(dist_, 0x3f, sizeof(dist_));
    memset(nxt, -1, sizeof(nxt));
    for (int i = 0; i < n; i++) { dist_[i][i] = 0; nxt[i][i] = i; }
    int E[4][3] = {{0,1,1},{1,3,1},{0,2,1},{2,3,1}};   // 0->3 有两条等长路径
    for (int i = 0; i < 4; i++) {
        int u = E[i][0], v = E[i][1], w = E[i][2];
        dist_[u][v] = w; nxt[u][v] = v;
    }
    floydLex();
    printf("0 到 3 的最短路长度 = %d，字典序最小的路径：", dist_[0][3]);
    printPath(0, 3);        /* 0 -> 1 -> 3 （而不是 0 -> 2 -> 3） */
    return 0;
}

9.5 其他最短路算法：Bellman-Ford 与 SPFA

9.5.1 Bellman-Ford：n−1 轮暴力松弛

Dijkstra 的失效场景只有一个原因：贪心地锁定顶点。 Bellman-Ford 的思路是「彻底不贪心」——每一轮把所有的边都松弛一遍，重复 n−1 轮。 它慢（O(nm)），但换来两个能力：可以处理负权边，可以判定负环。

为什么最多 n−1 轮？因为任何一条最短路径都不会包含环（有环就能去掉，除非是负环 —— 而负环意味着没有最短路）， 所以一条最短路最多经过 n 个顶点、n−1 条边。 第 1 轮扫描后，「只含 1 条边的最短路」一定已经确定； 归纳地，第 r 轮之后，「含 r 条边的最短路」一定已经确定 （因为它由「含 r−1 条边的最短路」再加一条边得到，而那一轮的扫描会松弛这条边）。 所以 n−1 轮之后，所有最短路都确定了。

如何判定负环？再跑第 n 轮（也就是第 n 次扫描所有边），如果还能松弛成功，说明存在负环。 因为此时已经没有「不含环的最短路」可以改进了，能改进只能是因为绕了负数环。

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

const int MAXN = 1005;
const int MAXM = 20005;
const int INF  = 0x3f3f3f3f;

int n, m;
struct Edge { int u, v, w; } e[MAXM];       // 只需要能枚举所有边即可，不必用邻接表
int dist_[MAXN], pre[MAXN];

/* 返回 true 表示存在从 s 可达的负环；否则 dist_ 为正确答案 */
bool bellmanFord(int s) {
    memset(dist_, 0x3f, sizeof(dist_));
    memset(pre, -1, sizeof(pre));
    dist_[s] = 0;

    /* n-1 轮松弛 */
    for (int round = 1; round <= n - 1; round++) {
        bool changed = false;                       // 小优化：本轮没更新就可以提前退出
        for (int i = 0; i < m; i++) {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            if (dist_[u] != INF && dist_[u] + w < dist_[v]) {
                dist_[v] = dist_[u] + w;
                pre[v] = u;
                changed = true;
            }
        }
        if (!changed) { printf("第 %d 轮已收敛，提前结束\n", round); break; }
    }

    /* 第 n 轮：只为检测负环（不要再改 dist_，否则答案会被污染） */
    for (int i = 0; i < m; i++) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (dist_[u] != INF && dist_[u] + w < dist_[v]) return true;   // 还能松弛 ⇒ 负环
    }
    return false;
}

int main() {
    n = 5; m = 6;
    int E[6][3] = {{0,1,2},{1,2,2},{0,2,5},{2,4,4},{1,4,7},{4,3,4}};
    for (int i = 0; i < m; i++) e[i] = {E[i][0], E[i][1], E[i][2]};

    if (bellmanFord(0)) printf("存在负环！\n");
    else {
        printf("dist = ");
        for (int i = 0; i < n; i++) printf("%d ", dist_[i]);
        printf("\n");     /* dist = [0, 2, 4, 12, 8] */
    }
    return 0;
}

上面的图（5 个顶点、6 条有向边）逐轮推演如下：

下面动画逐轮演示 Bellman-Ford 的松弛过程，并给出负环的样子：

9.5.2 SPFA：队列优化的 Bellman-Ford

Bellman-Ford 有个明显的浪费：每一轮都把所有边扫一遍，但只有上一轮被更新过的顶点， 它的出边才可能引发新的更新。于是自然想到：用一个队列保存「刚刚被松弛过的顶点」， 每次取出一个顶点，只松弛它的出边。这就是 SPFA（Shortest Path Faster Algorithm）， 由段凡丁在 1994 年提出。

SPFA 的实现要点：

• inq[v] 标记 v 是否已在队列中，避免重复入队。
• cnt[v] 记录 v 的入队次数；若某顶点入队次数 ≥ n，说明存在负环。
• 可以用 deque 做 SLF 优化（Small Label First）：入队时若新点的 dist 比队首还小， 就压到队首，否则压到队尾 —— 让更优的点先扩展，实践中常常快很多。

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

const int MAXN = 100005;
const int MAXM = 400005;
const int INF  = 0x3f3f3f3f;

int n, m;
int head[MAXN], etot = 0;
struct Edge { int to, w, nxt; } e[MAXM];
void addEdge(int u, int v, int w) { e[etot] = {v, w, head[u]}; head[u] = etot++; }

int dist_[MAXN], cnt[MAXN];
bool inq[MAXN];

/* 返回 true 表示存在从 s 可达的负环 */
bool spfa(int s) {
    memset(dist_, 0x3f, sizeof(dist_));
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));

    deque<int> q;                      // 用 deque 以便做 SLF 优化
    dist_[s] = 0; q.push_back(s); inq[s] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        inq[u] = false;
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (dist_[u] + w < dist_[v]) {
                dist_[v] = dist_[u] + w;
                if (!inq[v]) {
                    /* SLF：新点的 dist 比队首小就插到队首 */
                    if (!q.empty() && dist_[v] < dist_[q.front()]) q.push_front(v);
                    else q.push_back(v);
                    inq[v] = true;
                    if (++cnt[v] >= n) return true;   // 入队次数 ≥ n ⇒ 负环
                }
            }
        }
    }
    return false;
}

int main() {
    n = 7;
    memset(head, -1, sizeof(head));
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < 11; i++) {
        addEdge(E[i][0], E[i][1], E[i][2]);
        addEdge(E[i][1], E[i][0], E[i][2]);
    }
    if (spfa(0)) printf("存在负环\n");
    else {
        printf("dist = ");
        for (int i = 0; i < n; i++) printf("%d ", dist_[i]);
        printf("\n");     /* 与 Dijkstra 结果一致：[0, 2, 3, 3, 5, 8, 7] */
    }
    return 0;
}

9.5.3 三种最短路算法对比表

9.6 拓扑排序：AOV 网与活动先后关系

9.6.1 AOV 网：顶点表示活动

有些图关心的不是「距离」而是「顺序」：学「数据结构」之前得先学「C 语言」， 装「显卡驱动」之前得先装「操作系统」。 把这类关系画成图，就是 AOV 网（Activity On Vertex Network）：

拓扑排序（topological sort）：把 AOV 网的所有顶点排成一个线性序列， 使得对图中任意一条弧 <u,v>，u 都排在 v 的前面。 这个序列称为拓扑序列。它的意义就是「一个可行的做事顺序」。

9.6.2 Kahn 算法：不断摘掉入度为 0 的顶点

一句话本质

直觉极简单：入度为 0 的顶点意味着「没有前置任务」，可以立刻执行。 执行完之后，它指向的那些顶点就少了一个前置条件 —— 对应「把它的出边删掉，邻接点入度减 1」。 如果某个邻接点的入度因此变成 0，它就可以进入待办队列了。 当队列空了却还有顶点没输出时，说明剩下的顶点互相牵制，即存在环。

算法步骤

1. 统计每个顶点的入度 indeg[]；把所有入度为 0 的顶点入队。
2. 队列非空时：取出队首顶点 u，把 u 追加到输出序列。
3. 遍历 u 的每条出边 <u,v>：indeg[v]--；若减到 0，把 v 入队。
4. 重复 2~3 直到队列为空。若输出序列的长度 = n，则是 DAG；否则图中存在环。

手推过程表

用一个 6 个顶点、7 条弧的 AOV 网做例子。为方便与 9.7 的关键路径对照， 这里保留每条弧的「持续时间」，拓扑排序本身只用其中的先后关系（忽略权值）：

下面动画逐步骤演示 Kahn 算法，注意入度数组与队列的变化：

Kahn 算法完整实现

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

const int MAXN = 100005;
const int MAXM = 400005;

int n, m;
int head[MAXN], etot = 0;
struct Edge { int to, nxt; } e[MAXM];        // 拓扑排序不需要边权
void addEdge(int u, int v) { e[etot] = {v, head[u]}; head[u] = etot++; }

int indeg[MAXN];
vector<int> topo;                            // 拓扑序列

/* 返回 true 表示是 DAG（拓扑序已存入 topo）；false 表示有环 */
bool kahn() {
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to;
            if (--indeg[v] == 0) q.push(v);   // 前驱全部完成 ⇒ 可以做了
        }
    }
    return (int)topo.size() == n;             // 没输出完 ⇒ 有环
}

/* 字典序最小的拓扑序：把 queue 换成小根堆即可 */
bool kahnLexSmallest() {
    topo.clear();
    int deg[MAXN];
    for (int i = 0; i < n; i++) deg[i] = indeg[i];   // 注意：不要破坏原数组，这里先备份
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i = 0; i < n; i++) if (deg[i] == 0) pq.push(i);

    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        topo.push_back(u);
        for (int i = head[u]; i != -1; i = e[i].nxt)
            if (--deg[e[i].to] == 0) pq.push(e[i].to);
    }
    return (int)topo.size() == n;
}

int main() {
    n = 6;
    memset(head, -1, sizeof(head));
    int E[7][2] = {{0,1},{0,2},{1,3},{2,3},{2,4},{3,5},{4,5}};
    for (int i = 0; i < 7; i++) { addEdge(E[i][0], E[i][1]); indeg[E[i][1]]++; }

    int backup[MAXN];
    for (int i = 0; i < n; i++) backup[i] = indeg[i];

    if (kahn()) {
        printf("拓扑序（普通队列）：");
        for (size_t i = 0; i < topo.size(); i++) printf("%d ", topo[i]);
        printf("\n");
    } else printf("有环，没有拓扑序\n");

    for (int i = 0; i < n; i++) indeg[i] = backup[i];    // 还原入度
    if (kahnLexSmallest()) {
        printf("拓扑序（小根堆，字典序最小）：");
        for (size_t i = 0; i < topo.size(); i++) printf("%d ", topo[i]);
        printf("\n");
    }
    return 0;
}

DFS 版拓扑排序：后序的逆序

另一种更「隐式」的写法：对图做深度优先搜索，在回溯（后序）时把顶点压入栈， 最后依次弹出栈中元素，就得到拓扑序。 原理：当 DFS 访问完 u 的所有后继之后，u 才会被压栈 —— 所以u 一定排在后继之前（由栈的逆序输出保证）。 如果 DFS 过程中遇到一个「正在访问中（灰色）」的顶点，说明存在环。

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

const int MAXN = 100005;
const int MAXM = 400005;

int n, m;
int head[MAXN], etot = 0;
struct Edge { int to, nxt; } e[MAXM];
void addEdge(int u, int v) { e[etot] = {v, head[u]}; head[u] = etot++; }

int color[MAXN];             // 0 = 未访问，1 = 正在访问（在递归栈上），2 = 已完成
vector<int> order_;          // 后序
bool hasCycle = false;

void dfs(int u) {
    color[u] = 1;
    for (int i = head[u]; i != -1; i = e[i].nxt) {
        int v = e[i].to;
        if (color[v] == 1) { hasCycle = true; return; }   // 回到自己 ⇒ 有环
        if (color[v] == 0) { dfs(v); if (hasCycle) return; }
    }
    color[u] = 2;
    order_.push_back(u);      // 关键：后序位置压入（回溯时）
}

/* 返回是否有拓扑序 */
bool topoByDfs() {
    memset(color, 0, sizeof(color));
    order_.clear(); hasCycle = false;
    for (int i = 0; i < n; i++) if (color[i] == 0) { dfs(i); if (hasCycle) return false; }
    reverse(order_.begin(), order_.end());     // 后序的逆序就是拓扑序
    return true;
}

int main() {
    n = 6;
    memset(head, -1, sizeof(head));
    int E[7][2] = {{0,1},{0,2},{1,3},{2,3},{2,4},{3,5},{4,5}};
    for (int i = 0; i < 7; i++) addEdge(E[i][0], E[i][1]);

    if (topoByDfs()) {
        printf("DFS 版拓扑序：");
        for (size_t i = 0; i < order_.size(); i++) printf("%d ", order_[i]);
        printf("\n");
    } else printf("有环\n");
    /* 注意：DFS 版给出的顺序与 Kahn 版可能不同，但都是合法拓扑序 */
    return 0;
}

9.6.3 拓扑排序的应用

课程安排 / 任务调度

给定「先修课」关系，求一个可行的修课顺序；若不存在，说明课程要求自相矛盾（有环），需要报错给用户。

判断有向图是否有环

跑一遍 Kahn：输出顶点数等于 n 就是 DAG；小于 n 就有环。这比 DFS 判环更直观。

字典序最小的拓扑序

把队列换成小根堆：每次输出当前能做的编号最小的任务。常用于「要求输出方案且字典序最小」的题目。

依赖管理与构建系统

make / CMake / npm 解析模块依赖、编译器决定编译顺序、电子表格的公式求值顺序，都是拓扑排序。

DAG 上的动态规划

这是与第 13 讲最重要的联系：只要一张图是 DAG，就可以按拓扑序做 DP —— 因为拓扑序保证「算到某个点时，它的所有前驱都已经算完了」，天然满足 DP 的无后效性。 例如「DAG 上最长路」：f[v] = max(f[u] + w(u,v))，按拓扑序递推一次即可，复杂度 O(n + m)。

关键路径（下一节）

关键路径算法 = 拓扑排序（正推 ve）+ 逆拓扑序（倒推 vl），可见拓扑排序是它的地基。

9.7 关键路径：AOE 网与工程工期

9.7.1 AOE 网：弧表示活动

与 AOV 网的区别一句话说清：AOV 的顶点是活动、弧只表示先后；AOE 的弧是活动、权表示耗时。 前者回答「按什么顺序做」，后者回答「最快多久做完、哪些活动不能拖」。

9.7.2 四个核心参数

9.7.3 四步手推全过程（408 高频大题）

仍用图 9-9 那张网：弧集为 0→1(7)、0→2(5)、1→3(6)、2→3(4)、2→4(3)、3→5(6)、4→5(8)。 我们按「① 拓扑序正推 ve → ② 逆拓扑序倒推 vl → ③ 求 e、l → ④ 找出关键活动」四步来做。

① 正推 ve（取 max）：拓扑序为 0, 1, 2, 3, 4, 5。

② 逆推 vl（取 min）：逆拓扑序为 5, 4, 3, 2, 1, 0；vl[5] = ve[5] = 16。

这是非常宝贵的一课：如果手推时算出 vl < ve，先别怀疑自己的算术，要回头检查网本身。 下面把 1→3 的持续时间从 6 改成 2，让网自洽（同时把 3→5 调整为 5，使总工期仍为 19）， 重新设计出一张规范、自洽、适合出题的 AOE 网：

为什么把 1→3 的时长改成 2 就自洽了？因为此时 ve[3] = max(ve[1]+2, ve[2]+4) = max(9, 9) = 9， 事件 1 的最迟时间 vl[1] = vl[3] − 2 = 9 − 2 = 7 = ve[1]，全部 vl ≥ ve，网自洽。 但这张网的「关键路径」变成了两条并列（0→1→3→5 与 0→2→3→5 都是 15）， 为了演示「唯一关键路径」，我们最终采用下面这张网 —— 它与图 9-9 的拓扑结构完全相同，只是权值调过：

就是图 9-6 里的数据。下面直接给出它的完整四步手推结果（请你先自己算一遍，再对照）：

① 正推求 ve（拓扑序 0 → 1 → 2 → 3 → 4 → 5）：

② 逆推求 vl（逆拓扑序 5 → 4 → 3 → 2 → 1 → 0，初值全部设为 ve[5] = 19）：

校验：所有顶点都满足 vl(v) ≥ ve(v)，且源点 vl(0) = 0 = ve(0) —— 网是自洽的。

③ 求每条活动的 e 与 l（e(a) = ve(起点)，l(a) = vl(终点) − w(a)）：

④ 找出关键活动与关键路径：

• 关键活动：a₀(0→1)、a₂(1→3)、a₅(3→5)。
• 把它们首尾相接：0 → 1 → 3 → 5，长度 7 + 6 + 6 = 19，正好等于 ve(5)。
• 其余活动的机动时间：a₁ 有 3、a₃ 有 4、a₄ 有 3、a₆ 有 3。它们在余量范围内晚开始，不影响总工期。
• 次长路径 0 → 2 → 4 → 5 长度 5 + 3 + 8 = 16，比关键路径短 3 —— 这与 a₁、a₄、a₆ 的余量 3 完全吻合， 说明这三条活动串起来的那条路径整体可以推迟 3 个单位。

下面动画把四步完整演一遍，可以看到 ve、vl、余量数组与关键路径逐渐浮现：

9.7.4 C++ 完整实现

实现要点：先跑一次拓扑排序拿到拓扑序（顺便判环），再正推 ve；然后按拓扑序的逆序倒推 vl； 最后枚举每条弧算 e、l 并输出关键活动。整个过程 O(n + m)。

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

const int MAXN = 100005;
const int MAXM = 400005;

int n, m;
int head[MAXN], etot = 0;
struct Edge { int to, w, nxt; } e[MAXM];     // 有向边，带权（活动持续时间）
int inDeg[MAXN];                             // 原图入度（拓扑排序用）

void addEdge(int u, int v, int w) { e[etot] = {v, w, head[u]}; head[u] = etot++; }

int ve[MAXN], vl[MAXN];                      // 事件最早 / 最迟发生时间
vector<int> topo;                            // 拓扑序

/* 返回 true 表示是 DAG */
bool topoSort() {
    int deg[MAXN];
    for (int i = 0; i < n; i++) deg[i] = inDeg[i];
    queue<int> q;
    for (int i = 0; i < n; i++) if (deg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int i = head[u]; i != -1; i = e[i].nxt)
            if (--deg[e[i].to] == 0) q.push(e[i].to);
    }
    return (int)topo.size() == n;
}

/* 关键路径：返回总工期；有环时返回 -1 */
int criticalPath(int src, int sink) {
    if (!topoSort()) return -1;

    /* ① 正推 ve：按拓扑序，用出边更新后继，取 max */
    for (int i = 0; i < n; i++) ve[i] = 0;
    for (size_t i = 0; i < topo.size(); i++) {
        int u = topo[i];
        for (int j = head[u]; j != -1; j = e[j].nxt)
            ve[e[j].to] = max(ve[e[j].to], ve[u] + e[j].w);
    }

    /* ② 逆推 vl：初值为 ve(汇点)，按逆拓扑序用出边更新自己，取 min */
    for (int i = 0; i < n; i++) vl[i] = ve[sink];
    for (int i = (int)topo.size() - 1; i >= 0; i--) {
        int u = topo[i];
        bool hasOut = false;
        for (int j = head[u]; j != -1; j = e[j].nxt) {
            hasOut = true;
            vl[u] = min(vl[u], vl[e[j].to] - e[j].w);
        }
        if (!hasOut) vl[u] = ve[sink];       // 汇点（以及其它无出边的点）
    }

    /* ③④ 枚举每条弧求 e、l，判断关键活动 */
    printf("事件时间：\n");
    for (int i = 0; i < n; i++)
        printf("  v%d: ve=%2d  vl=%2d  %s\n", i, ve[i], vl[i],
               ve[i] == vl[i] ? "← 关键事件" : "");
    printf("活动分析：\n");
    for (int u = 0; u < n; u++) {
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            int ee = ve[u];                  // 最早开始
            int ll = vl[v] - w;              // 最迟开始
            printf("  活动 %d->%d (时长 %d): e=%2d  l=%2d  余量=%d  %s\n",
                   u, v, w, ee, ll, ll - ee, (ee == ll) ? "★关键活动" : "");
        }
    }
    return ve[sink];
}

int main() {
    n = 6; m = 7;
    memset(head, -1, sizeof(head));          // 千万别忘！否则遍历邻接表会越界读
    memset(inDeg, 0, sizeof(inDeg));
    int E[7][3] = {{0,1,7},{0,2,5},{1,3,6},{2,3,4},{2,4,3},{3,5,6},{4,5,8}};
    for (int i = 0; i < m; i++) {
        addEdge(E[i][0], E[i][1], E[i][2]);
        inDeg[E[i][1]]++;
    }
    int total = criticalPath(0, 5);
    printf("工程最短完成时间（关键路径长度）= %d\n", total);
    return 0;
}

9.7.5 四个关键结论

9.8 连通性进阶与 MST 的进一步性质

9.8.1 瓶颈生成树：MST 一定是最小瓶颈生成树

瓶颈生成树（bottleneck spanning tree）：在所有生成树中， 最大边权最小的那棵。它的目标是「让最贵的那条边尽可能便宜」， 典型场景是「让整条运输线路中最窄的那一段尽可能宽」。

对示例图 G：MST 是 {(0,1)2, (1,2)2, (0,3)3, (3,4)2, (2,6)4, (3,5)5}，最大边权是 5。 意思是「存在一棵生成树，让所有边都不超过 5」，而你不可能做到「所有边都不超过 4」 （顶点 5 只有两条边：5 和 6，必然要选一条 ≥ 5 的）。

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

const int MAXN = 100005, MAXM = 200005;
int n, m, fa[MAXN], siz[MAXN];
struct Edge { int u, v, w; } e[MAXM];
int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }

/* 最小瓶颈生成树：Kruskal 一跑到全连通，最后加入的那条边就是答案
   本质：Kruskal 加入的边权递增，所以最后一条边就是生成树中的最大边 */
int bottleneck() {
    sort(e, e + m, [](const Edge& a, const Edge& b) { return a.w < b.w; });
    for (int i = 0; i < n; i++) { fa[i] = i; siz[i] = 1; }
    int cnt = 0, last = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        int ru = find(e[i].u), rv = find(e[i].v);
        if (ru == rv) continue;
        if (siz[ru] < siz[rv]) swap(ru, rv);
        fa[rv] = ru; siz[ru] += siz[rv];
        cnt++; last = e[i].w;
    }
    return cnt == n - 1 ? last : -1;      // -1 表示图不连通
}

int main() {
    n = 7; m = 11;
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < m; i++) e[i] = {E[i][0], E[i][1], E[i][2]};
    printf("瓶颈值（生成树中最大边权的最小可能值）= %d\n", bottleneck());   // 5
    return 0;
}

9.8.2 次小生成树（简要）

次小生成树：权值和严格大于最小生成树的那些生成树中，权值最小的那棵。 求法有两大类：

• 枚举换边法 O(m log n)：先求一棵 MST。对每条不在 MST 中的边 (u,v,w)， 把它加进树会形成一个环；为了让总权增加最少，应该在这个环上去掉权值最大的一条边 （且不能是刚加进去的这条）。于是答案 = MST总权 + min{ w − 环上最大边权 }。 树上的「u 到 v 路径上的最大边权」可以用倍增 LCA 预处理，O(log n) 查询。
• 枚举断边法 O(n·m)：对 MST 上的每条边，强制「不使用」它再求一次 MST，取最小值。 实现简单但慢，适合 n 很小的情况（考试手推常这么算）。

对示例图 G 手推一下：MST 权值 18。把 MST 上的边 (0,3)去掉（权 3）， 图被切成 {0,1,2,6} 与 {3,4,5} 两块，能连通它们的最小边是从 6 到 4 的 (4,6) 权 5 → 得到生成树权值 18 − 3 + 5 = 20。再试去掉 (3,4)（权 2）：两块为 {4,6,2,1,0,3,5}? —— 去掉 (3,4) 后 4 只与 6 相连，仍连通，最小替代边是 (4,6) 权 5，得到 18 − 2 + 5 = 21。 去掉 (1,2)（权 2）：替代边需跨 {2,6} 与其余，最小是 (0,2) 权 3 → 18 − 2 + 3 = 19。 把所有可能算一遍，最小值是 19，所以次小生成树权值为 19 （它由 MST 交换 (1,2)→(0,2) 得到）。

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

const int MAXN = 505;
const int INF  = 0x3f3f3f3f;

int n, m;
struct Edge { int u, v, w, used; } e[MAXN * MAXN];
int fa[MAXN];
int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }

/* 求最小生成树，标记用到的边；blocked = 强制不使用的边编号 */
int mst(int blocked, vector<int>* chosen) {
    for (int i = 0; i < n; i++) fa[i] = i;
    int sum = 0, cnt = 0, ret = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        if (i == blocked) continue;
        int ru = find(e[i].u), rv = find(e[i].v);
        if (ru == rv) continue;
        fa[ru] = rv; sum += e[i].w; cnt++;
        if (chosen) chosen->push_back(i);
        ret = sum;
    }
    return cnt == n - 1 ? sum : INF;
}

int main() {
    n = 7; m = 11;
    int E[11][3] = {{0,1,2},{1,2,2},{2,6,4},{0,2,3},{0,3,3},
                    {1,3,5},{3,4,2},{4,6,5},{3,5,5},{1,5,6},{0,6,11}};
    for (int i = 0; i < m; i++) e[i] = {E[i][0], E[i][1], E[i][2], 0};
    sort(e, e + m, [](const Edge& a, const Edge& b) { return a.w < b.w; });

    vector<int> chosen;
    int best = mst(-1, &chosen);
    printf("最小生成树权值 = %d\n", best);

    /* 枚举断掉 MST 上的每条边，重求 MST，取最小的「不是 best 的结果」 */
    int second = INF;
    for (size_t k = 0; k < chosen.size(); k++) {
        int v = mst(chosen[k], nullptr);
        if (v > best && v < second) second = v;
    }
    printf("次小生成树权值 = %d\n", second);      /* 19 */
    return 0;
}

9.8.3 回顾：并查集在 Kruskal 中的核心地位

最后再强调一次：Kruskal 的整个正确性都压在「如何快速判断两端点是否已连通」上。 如果不用并查集，每加一条边就做一次 BFS/DFS 判连通，复杂度会退化成 O(m·(n+m))； 用并查集则是 O(m α(n))，几乎线性。 并查集的三大要素请务必记牢：父指针数组 fa[]、路径压缩、按秩（或按大小）合并。

另外，并查集本身也是「无向图连通性 / 连通块计数」的通用工具： 把所有边 union 一遍，最后数一数有几个不同的根，就是连通块的个数； 也可以用来判断「加一条边会不会形成环」（这正是 Kruskal 在做的事）。

9.9 工程视角：图论算法在真实系统里跑在哪

前面八节我们把 Prim、Kruskal、Dijkstra、Floyd、Bellman-Ford、拓扑排序、关键路径逐个拆开看透了， 但一直有个问题没回答：这些算法在真正的软件和硬件里，究竟跑在什么地方？ 这一节换一个视角 —— 不看复杂度表，而是看这些算法被「装进」了哪些系统，以及工程上为了让它跑得动，又做了哪些改造。 你会发现一件有意思的事：课本算法几乎从不会原样上线，它们总是被「削一刀、加一层、换个方向」之后才投入使用； 而每一处改造背后的理由，恰恰就是前面讲过的那些性质（可采纳性、负权、收敛性、松弛时间……）。

9.9.1 地图导航与路线规划：Dijkstra 的规模危机与 A* 的救援

打开高德地图输入起点终点，几百毫秒内就要给出路线。这背后是一个单源最短路问题， 最标准的解法当然是第 9.3 节的 Dijkstra。可是工程上第一个撞上的墙是规模：

• 全国路网大约有 1 亿个结点（路口、路段端点）和 3 亿条边；
• 朴素 Dijkstra 是 O(n²)，在 n = 10⁸ 时是 10¹⁶ 次操作，根本跑不动；
• 就算换成堆优化 O(m log n)，一次跨城查询也可能要扩展上百万个结点 —— 单次还能忍，但导航要求的是毫秒级返回、且要扛住每秒几十万次并发查询， 这个量级就完全顶不住了。

问题的根子在于：Dijkstra 完全不知道终点在哪一个方向。 它对所有顶点一视同仁，以起点为中心「一圈一圈」均匀向外扩散，直到把终点也圈进来才停手。 也就是说，为了找一条朝东走的路，它把西边、南边、北边的路也全算了一遍 —— 这些计算纯属浪费。 而路网恰恰有一个 Dijkstra 没有利用的宝贵性质：它是画在平面上的，结点有坐标， 「往哪个方向走大概能靠近终点」是能估出来的。

A*：给搜索装一个「指南针」

A*（读作 A-star）的改法非常简洁：给每个结点再多估一个数 h(v) = 「从 v 到终点大概还要走多远」，然后优先队列不再按 g 排序，改按 f = g + h 排序。 含义一目了然：g 是已经花掉的钱，h 是估计还要花的钱，两者相加就是「走这条路总共大概要花多少」。 于是搜索会优先去试探那些看起来最有希望的方向，而不是平均用力。

把 h 直接取成 0，f = g + 0 = g，A* 就退化回 Dijkstra。 所以二者其实是同一个算法，唯一的区别就是「要不要用启发函数」。 下面这段程序就利用这一点：同一个搜索函数，用一个参数控制启发式的开关， 在同一张地图上跑两遍，直接量出 A* 到底省了多少。

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

/* ============================================================
   实验一：40 x 40 网格 + 障碍墙（游戏 / 机器人寻路的典型场景）
   实验二：41 x 41 完美迷宫（启发式严重失真的极端场景）
   两次都用同一套搜索：启发函数乘 1 是 A*，乘 0 就退化成 Dijkstra

   优先队列里放的是 (f, h, 编号) 三元组：
   f 相同时比 h（离终点越近越优先），再相同比编号。
   这样队列的先后顺序是【唯一确定】的，
   换编译器、换平台，扩展结点数都一模一样。
   ============================================================ */

const int N = 41, M = 41;          /* 网格规模（41 = 2*20+1，方便摆迷宫） */
const int MAXV = N * M;
int grid[N][M];

int gx, gy;                        /* 终点坐标，算曼哈顿距离用 */
int g[MAXV], h[MAXV], f[MAXV];     /* 三个数组：已花费 / 估计剩余 / 两者之和 */
int pre[MAXV];                     /* 路径还原 */
bool done[MAXV];                   /* 是否已确定最优（出队并扩展过） */

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
const int INF = 1000000000;

/* 曼哈顿距离：4 邻域里每走一步代价恰好是 1，所以它永远不高估真实剩余代价 */
int heur(int x, int y) { return abs(x - gx) + abs(y - gy); }

void initArrays() {
    for (int i = 0; i < MAXV; i++) {
        g[i] = f[i] = INF;
        pre[i] = -1;
        done[i] = false;
    }
}

/* 通用搜索：hScale = 1 就是 A*，hScale = 0 就是 Dijkstra（启发式恒为 0） */
int search(int sx, int sy, int tx, int ty, int hScale) {
    gx = tx; gy = ty;
    initArrays();

    typedef pair<int, pair<int, int> > Node;        /* (f, (h, 编号)) */
    priority_queue<Node, vector<Node>, greater<Node> > pq;
    int s = sx * M + sy, t = tx * M + ty;
    g[s] = 0;
    h[s] = hScale * heur(sx, sy);
    f[s] = g[s] + h[s];
    pq.push(make_pair(f[s], make_pair(h[s], s)));

    int cnt = 0;                       /* 关键指标：扩展了多少个结点 */
    while (!pq.empty()) {
        int u = pq.top().second.second;
        pq.pop();
        /* 每个点可能被压入多次（每找到一条更短的 g 就压一次）。
           A* 的启发式不高估时，出队顺序与 Dijkstra 一样是单调的，
           所以第一次出队时的 g 就是最优值 —— 第 9.3 节讲的「贪心前提」。 */
        if (done[u]) continue;         /* 已确定最优，重复入队的旧副本扔掉 */
        done[u] = true;
        cnt++;
        if (u == t) break;             /* 终点确定最优，可以收工 */

        int ux = u / M, uy = u % M;
        for (int k = 0; k < 4; k++) {
            int vx = ux + dx[k], vy = uy + dy[k];
            if (vx < 0 || vx >= N || vy < 0 || vy >= M) continue;
            if (grid[vx][vy] == 1) continue;          /* 撞墙 */
            int v = vx * M + vy;
            if (done[v]) continue;
            int ng = g[u] + 1;                        /* 每步代价 1 */
            if (ng < g[v]) {                          /* 松弛 */
                g[v] = ng;
                pre[v] = u;
                h[v] = hScale * heur(vx, vy);
                f[v] = g[v] + h[v];
                pq.push(make_pair(f[v], make_pair(h[v], v)));
            }
        }
    }
    return cnt;
}

/* 把路径打回 grid，方便打印：2 = 路径，3 = 起点，4 = 终点 */
void markPath(int sx, int sy, int tx, int ty) {
    for (int cur = tx * M + ty; cur != -1; cur = pre[cur]) grid[cur / M][cur % M] = 2;
    grid[sx][sy] = 3;
    grid[tx][ty] = 4;
}

void drawGrid() {
    for (int i = 0; i < N; i++) {
        printf("  ");
        for (int j = 0; j < M; j++) {
            int v = grid[i][j];
            putchar(v == 0 ? '.' : v == 1 ? '#' : v == 2 ? '*' : v == 3 ? 'S' : 'T');
        }
        putchar('\n');
    }
}

/* 实验一的障碍：竖墙 + 横墙各留一个缺口，路径必须绕行 */
void buildWalls() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) grid[i][j] = 0;
    for (int i = 0; i < 30; i++) {
        if (i == 25) continue;             /* 缺口 */
        grid[i][13] = 1;
    }
    for (int j = 13; j < 34; j++) {
        if (j == 20) continue;             /* 缺口 */
        grid[26][j] = 1;
    }
}

/* 实验二：41 x 41 完美迷宫（'#' 墙，'.' 通路），由递归分割算法生成后固化在这里 */
const char *MAZE[41] = {
    "#########################################",
    "#.#.#...#...#.....#...#.#.....#...#.....#",
    "#.#.###.#.#.#.#.#.#.###.###.#####.###.#.#",
    "#.#.#.#.#.#...#.#.#.#...#.#...#.#.#...#.#",
    "#.#.#.#.#######.###.#.#.#.#.###.#.###.###",
    "#.#.#...#.#.....#.....#.......#...#...#.#",
    "#.#.###.#.#.#####.#.###.#####.#.#####.#.#",
    "#.#.....#.#...#...#...#.#.....#...#.....#",
    "#.#.###.#.#.#.#.#.#.###.#.#####.#####.#.#",
    "#.#.#...#...#...#.#.#.#.#.....#...#...#.#",
    "#.#.###.#.###.#.#.#.#.#.###.#.#.###.#####",
    "#...#.....#...#.#.#...#.#...#.....#.....#",
    "#################.###################.###",
    "#.#.........#...#...#...#.#.......#.....#",
    "#.#.###.###.###.#.#.#.###.#.#####.#.#####",
    "#.....#.#...#...#.#.......#.....#.#...#.#",
    "#.#####.#.###.###.#####.#.#.#.###.#.#.#.#",
    "#.....#.#.......#.#.....#.#.#...#.#.#...#",
    "###########.#.#.#.###.###.#######.#.#####",
    "#.....#.#...#.#...#.....#.#.#.#...#.....#",
    "#####.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.###",
    "#...#.#...#.#.#.#.#.#.#.#.#.....#.#.#...#",
    "#.#.#.#.#.###.#.#.#.###.#.###.#####.###.#",
    "#.#.....#...#...#.#...#.#...#.#.#.#.#...#",
    "###.###.#.#####.#.#####.#.#.#.#.#.###.###",
    "#.....#.#...#...#.#.....#.#.....#.#.....#",
    "###########.#################.#.#.###.###",
    "#...#.......#.#...#.#.....#...#...#.#...#",
    "#.#########.#.#.#.#.###.#########.#.#.#.#",
    "#...#.......#...#.#.#...#.#.#.#...#...#.#",
    "#.#.###.#########.#.#.#.#.#.#.#.#.#.#####",
    "#.#.#.#.#...#.....#...#...#.....#...#...#",
    "###.#.###.#####.#.###.###.#####.#.#.#.#.#",
    "#...........#.#.#...#.....#.#.....#...#.#",
    "###.#.###.###.#.#.#.#######.#######.#####",
    "#.#.#...#...#.....#.......#.......#...#.#",
    "#.#.#####.#######.#.#####.#.#########.#.#",
    "#...#.............#.#...#.#...#...#.....#",
    "#######.#####.#.###.###.#.###.#.###.###.#",
    "#...........#.#...#.....#.#.......#...#.#",
    "#########################################"
};

void buildMaze() {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) grid[i][j] = (MAZE[i][j] == '#') ? 1 : 0;
}

int main() {
    int sx = 0, sy = 0, tx = N - 1, ty = M - 1;

    /* ---------- 实验一：40 x 40 带墙网格 ---------- */
    buildWalls();
    int a1 = search(sx, sy, tx, ty, 1);
    int c1 = g[tx * M + ty];
    markPath(sx, sy, tx, ty);

    buildWalls();
    int d1 = search(sx, sy, tx, ty, 0);
    markPath(sx, sy, tx, ty);

    printf("=== 实验一：40 x 40 网格（带障碍墙）===\n");
    printf("  A*       最短路 %d 步，扩展 %d 个结点\n", c1, a1);
    printf("  Dijkstra 最短路 %d 步，扩展 %d 个结点\n", c1, d1);
    printf("  A* 只需 Dijkstra 的 %.1f%%\n\n", 100.0 * a1 / d1);
    drawGrid();

    /* ---------- 实验二：41 x 41 完美迷宫 ---------- */
    buildMaze();
    sx = 1; sy = 1; tx = N - 2; ty = M - 2;
    int a2 = search(sx, sy, tx, ty, 1);
    int c2 = g[tx * M + ty];
    markPath(sx, sy, tx, ty);

    buildMaze();
    int d2 = search(sx, sy, tx, ty, 0);
    markPath(sx, sy, tx, ty);

    printf("\n=== 实验二：41 x 41 完美迷宫 ===\n");
    printf("  A*       最短路 %d 步，扩展 %d 个结点\n", c2, a2);
    printf("  Dijkstra 最短路 %d 步，扩展 %d 个结点\n", c2, d2);
    printf("  A* 只需 Dijkstra 的 %.1f%%\n", 100.0 * a2 / d2);

    return 0;
}

看两处真实输出：实验一（40 × 40 带墙网格，80 步最短路）里 A* 只扩展了 81 个结点，而 Dijkstra 扩展了 1578 个，不到它的 5.1%，快了约 19 倍； 实验二（41 × 41 完美迷宫，96 步最短路）里 A* 扩展 125 个，Dijkstra 扩展 530 个，约 23.6%。 两个实验里 A* 与 Dijkstra 算出的最短路长度完全相等（80 步、96 步）， 这正说明「启发式只管加速、不管改答案」—— 只要它可采纳。

实验一的比例（5.1%）比实验二（23.6%）漂亮得多，原因值得琢磨： 实验一的空地多、启发函数估得准，搜索几乎笔直地冲向终点； 实验二的迷宫里到处是死胡同，曼哈顿距离在弯弯绕绕的走廊里严重失真， A* 会被「看起来很近其实走不通」的方向骗着去撞几次墙。可见： 启发函数越接近真实剩余距离，A* 的优势越大。

A* 之外：工程上真正扛住全国路网的三招

A* 把搜索范围从「一个圆」压成了「一个朝终点拉长的椭圆」，但在 1 亿结点的图上， 这个椭圆依然可能覆盖几百万个结点。所以真实的导航产品还要再加三层：

双向搜索（bidirectional search）

从起点正向搜、从终点反向搜，两边轮流扩展，在中间某处会合。 如果单向要扩展出一个半径 r 的圆（面积 πr²），双向各扩展半径 r/2， 总工作量约 2 · π(r/2)² = πr²/2 —— 理论上直接省掉一半。 实现上要注意「两侧各自的 g 值不能直接相加判断收敛」，正确做法是 当两侧的最小 f 之和 ≥ 目前找到的最好路径长度时才停。

层次化预处理（hierarchical / contraction hierarchies）

把路网分成「高速 / 国道 / 城市小路」几层：长距离查询先在高层（高速）上跑， 只在起点和终点附近才下到小路。 道理很直观：从北京到上海，你绝不会先研究上海的弄堂怎么走 —— 先上高速，快到了再下匝道。 经过预处理（如 CH 收缩层次，把不重要的结点事先「收缩」掉并记下捷径）之后， 全国路网的查询可以压到毫秒级，这是 Google Maps、高德这类产品的核心技术之一。

路网预处理 + 高速缓存

把常用区域的最短路结果、各条高速之间的连接代价预先算好存起来； 再配合「按需分层加载」，让一次查询只触碰图的一小部分。

这三招是可以叠加的：现在的商用导航通常是层次化预处理 + 双向 A* 的组合。 课本上那个朴素的 Dijkstra，在这里只作为「最底层、最后一公里」的部件存在。

9.9.2 网络路由协议：OSPF 与 RIP 的两种活法

路由器要决定「这个包从哪个口发出去」，本质就是在做最短路。 但路由器和地图软件有个根本差别：地图是静态的，网络是动态的 —— 链路会断、会拥塞、会有新路由器接入，而且没有中央服务器能掌握全局。 于是网络界分裂出了两大流派，它们恰好就是我们在第 9.3 与第 9.5 节学的两种最短路算法。

为什么 OSPF 要用 Dijkstra？因为路由器一旦掌握了全网拓扑， 「从我这到目的地走哪条路最短」就是一个标准的单源最短路问题，Dijkstra 正合适，而且它收敛快 —— 对网络来说，链路断了之后「多久能重新绕通」是硬指标，这叫收敛时间。 代价是每个路由器都得存全网拓扑、跑一遍 O(m log n)，还要不停地泛洪状态包。

为什么 RIP 只能用 Bellman-Ford？因为 RIP 里每个路由器根本不知道全网长什么样， 它只知道「我到邻居的距离」加上「邻居告诉我的、它到目的地的距离」。 这正是 Bellman-Ford 的松弛式 dist[v] = min(dist[v], dist[u] + w(u,v))—— 而且是可以分布式、异步地做的：每台路由器各自算自己那一行，周期性换换表，就能慢慢收敛到正确值。 这种「不需要全局信息」的性质，正是距离向量协议能work的根本原因。

9.9.3 任务调度与依赖解析：拓扑排序撑起的半边天

第 9.6 节的拓扑排序看起来朴实无华，但它是这一章里被最多系统直接使用的算法， 因为它回答的问题太普遍了：「有先后约束的一堆事情，按什么顺序做？」

编译构建系统（Make / CMake / Bazel）

每个源文件、每个库、每个可执行文件都是图上的一个点，#include 或者链接依赖就是有向边。 make 必须先算出拓扑序，才知道先编译谁、后链接谁； 并行构建（make -j8）则更进一步：把当前入度为 0 的结点同时开工， 这正是 Kahn 算法（第 9.6.2 节）里「队列里同时待着多个入度 0 顶点」的工程含义。

包管理器（apt / npm / pip / Maven）

安装一个包要先装它的所有依赖，依赖还可能互相依赖。 解析器要算出一个可行的安装顺序，并在遇到循环依赖时报错。 顺带一提：Kruskal 里那个并查集（第 07 讲 7.9 节的并查集）在这里也常被用来快速判断 「这两个包是否已经被同一个依赖组覆盖」，避免重复安装。

电子表格的公式求值

C1 = A1 + B1、D1 = C1 * 2……单元格之间的引用关系天然是个 DAG。 Excel 每次重算都要重新做一次拓扑排序，保证「用到某个格子时它已经算好了」。 如果公式出现循环引用（A1 = B1 + 1 且 B1 = A1 + 1）， 它会直接弹窗报错 —— 那就是拓扑排序发现「队列空了但还有结点没输出」。

课程表排课与任务调度

「数据结构」要求先修「C 语言」，于是后者指向前者。 排课系统要给出一个满足全部先修约束的学期安排；约束自相矛盾（有环）时， 系统必须明确报错而不是硬排出一份不可能的课表。

CI 流水线的 stage 依赖

GitHub Actions / GitLab CI 里的 needs: 声明了 job 之间的依赖。 Runner 调度器按拓扑序启动 job，没有依赖关系的 job 并行跑， 这正是拓扑排序 + 并行的典型用法。

9.9.4 项目管理：关键路径法（CPM / PERT）

盖一栋楼、发射一颗卫星、发布一个软件版本 —— 这类项目的共同点是： 任务极多、任务之间有依赖、而你只关心「最快什么时候能完工」和「哪个环节拖不得」。 管理学界给这套方法起的名字叫 CPM（关键路径法）/ PERT（计划评审技术）， 而它的数学形式，就是第 9.7 节那张 AOE 网和 ve / vl / e / l 四个数组。

「松弛时间」是整个方法里最有工程价值的数字。 它把项目里的任务分成了两类： 松弛时间为 0 的活动一动就出事；松弛时间有 5 天的活动，你晚 3 天开工完全没问题。 项目经理每天真正要盯的，就是那条关键路径上的十几个活动 —— 而不是全部三百个任务。

9.9.5 最小生成树：布线、聚类与图像分割

MST 的工程价值集中在一句话上：用最小的总代价把所有点连成一个整体。 凡是「连线」要花钱的场景，它就会出现。

网络布线（电话线 / 光纤 / 电缆）

要在若干个城市（或楼栋、机房）之间铺设线路，让任意两点都能通信，且总长度最短。 这正是 MST 的定义，Prim / Kruskal 直接可用。 边权就是距离或造价；如果不同地段造价不同（比如过江要贵得多），把权值换成造价即可。

电路板走线

要在板上若干焊点之间连通导线，希望总铜线长度最短 —— 同样是 MST。 更真实的版本还会加上「不允许交叉」等几何约束，那就超出了 MST 的范围， 变成了更难的 斯坦纳树问题（允许增加额外的中转点，MST 则只许用已有点）。

聚类：MST 去掉最长的几条边

把数据点看成完全图上的顶点，两点之间的权 = 它们的距离，求一棵 MST。 然后删掉权值最大的 k−1 条边，MST 就裂成 k 个连通块 —— 这天然就是 k 个簇。 这个方法的妙处是不需要事先指定簇的形状（不像 k-means 假设簇是球形的）， 所以对「长条形、不规则」的簇效果更好。按权值从大到小删边，就得到了层次聚类的完整谱系。

图像分割

把像素当顶点，相邻像素的相似度当边权，做 MST 之后按边权切分， 相似度低的地方（也就是物体边界）会自然成为被切断的位置。 经典的 Felzenszwalb 分割算法就是基于 MST 的，它至今仍是很多视觉系统的预处理步骤。

管网铺设（水 / 气 / 供暖）

和布线同理，但边权要考虑的不只是长度，还有管径、压力损失、施工难度。 注意管网通常是有向的（水只能从高处往低处流），这时就不能直接用无向图的 MST 了， 需要变成「有向最小生成树 / 最小树形图」问题（用朱刘算法求解）。

「Prim 适合稠密图、Kruskal 适合稀疏图」在工程上是什么意思？ 看第 9.2.5 节的复杂度：Prim 朴素版 O(n²) 只跟顶点数有关， Kruskal 是 O(m log m) 主要花在给边排序上。翻译成工程语言就是：

• 稠密图（m 接近 n²）：边太多了，把几千万条边排一遍序本身就非常昂贵， 而 Prim 根本不需要排序，它只反复做「找离树最近的顶点」这一个动作。 所以城市路网、电路板这类「边多到爆炸」的场景选 Prim。
• 稀疏图（m 与 n 同阶）：边很少，排序很快， 而且 Kruskal 有一个 Prim 比不了的好处 —— 它可以只处理「目前拿得到的边」，天然适合分布式和流式场景。 比如把边按权值分批喂进来，或者把图切成几块分别求 MST 再合并。
• 工程上更常见的做法：先用 Prim 或 Kruskal 求出 MST， 再把「必须连通的强制边」（比如已经铺好的线路、必须走地下的那几段）先 union 进去， 然后继续跑 Kruskal —— 这是对「部分边已被固定」这一现实约束的标准处理方式。

9.9.6 工程选型对比表与三条落地心法

表怎么看？重点不在背，而在体会每一列的现实约束：

• 「能否处理负权」这一列，决定了你在「有补贴 / 有折扣」的图（负权边）上能不能用 Dijkstra / A*。 现实的例子：某些计费场景里「打折」会表现为负的成本增量，那就只能用 Bellman-Ford 了。
• 「能否处理动态图」这一列，往往比复杂度更重要。 网络拓扑每秒都在变，所以 RIP 那种「每次只更新一点点」的增量式方法反而有生命力； Floyd 虽然优雅，但每变一条边就要 O(n³) 重算，注定只能用于静态的小图。
• 「单源还是全源」这一列直接决定你要调用几次算法。 只要一次查询，就别上 Floyd；如果需要任意两点的距离，跑 n 次 Dijkstra（O(nm log n)） 和 Floyd 的 O(n³) 各有千秋：稀疏图上 n 次堆优化 Dijkstra 更快，稠密图上 Floyd 的常数更小。

9.10 本章小结、易错点与自测题

9.10.1 一页速查表

9.10.2 易错点清单

9.10.3 自测题（6 道，答案折叠）