本节专注于最短路径，从情景开始引出三个经典算法。最终你会发现它们是同一个微观操作在三种调度策略下的产物。

引子：一次配送任务

小镇上有 $6$ 个地点。骑手从餐厅 $A$ 出发，要把外卖送到顾客 $F$ 手里。每条路单向通行，路旁标注的数字是骑行耗时（分钟）：

              1            3            2            1
      A ──────────► B ──────────► D ──────────► E ──────────► F
      │             │             ▲             ▲             ▲
      │             │             │             │             │
    4 │           8 │           1 │           5 │             │
      ▼             ▼             │             │             │
      └─────► C ────┴─────────────┴─────────────┘             │
      └────────────────────────── 10 ─────────────────────────┘

delivery-map.txt

为了不依赖示意图的绘制精度，下面给出权威的边表（本页所有算法都依赖这张图，希望能够烂熟于心）： 注：边表就是把图中所有路线整理成一张清单，每行写明起点、终点和耗时（即权重）

起点	终点	耗时 $w$		起点	终点	耗时 $w$
$A$	$B$	$1$		$C$	$D$	$1$
$A$	$C$	$4$		$C$	$E$	$5$
$A$	$F$	$10$		$D$	$E$	$2$
$B$	$C$	$8$		$D$	$F$	$6$
$B$	$D$	$3$		$E$	$F$	$1$

骑手的问题：从 $A$ 到 $F$，走哪条路总耗时最少？

DEF定义 · 路径、路径长度与最短路径

在图 $G=(V,E)$ 中，从顶点 $u$ 到 $v$ 的路径是一个顶点序列 $u=v_0,v_1,\dots ,v_k=v$，其中每对相邻顶点之间都有边。路径的长度是各边权之和 $\sum _{i=0}^{k-1}w(v_i,v_{i+1})$；无权图视为每条边权为 $1$，此时长度即边数。所有 $u\to v$ 路径中长度最小者称为最短路径，其长度记为 $d(u,v)$；不可达时 $d(u,v)=\mathrm{\infty }$。

DEF定义 · 问题的两种规模

• 单源最短路径（Single-Source Shortest Path，SSSP）：给定源点 $s$，求所有 $v\in V$ 的 $d(s,v)$——骑手只关心"从餐厅出发到每个地点多久"。
• 全源最短路径（All-Pairs Shortest Path，APSP）：求所有点对 $(u,v)$ 之间的 $d(u,v)$——平台想预计算一张任意两点间的运费表。

在学习算法之前，先找到提纲挈领的关键。

统一的主线：松弛

想象你手里维护着一张距离估计表 dist[]：dist[v] 是你当前对 $d(s,v)$ 的估计（下文在不致混淆处，把 $d(s,v)$ 简写为 $d(v)$）。所谓松弛（relaxation），就是拿一条已知的路，去尝试压短某个估计：

DEF定义 · 松弛操作

对一条边 $(u,v)$，执行

$$\mathrm{relax}(u,v):\text{若 }\mathrm{dist}[u]+w(u,v)<\mathrm{dist}[v],\text{则令 }\mathrm{dist}[v]\leftarrow \mathrm{dist}[u]+w(u,v).$$

简单地说："如果绕道 $u$ 再走一步能更快到 $v$，就更新 $v$ 的估计。" 若更新确实发生，称这次松弛生效。

松弛之所以成为算法的核心，靠两个不变量：

PROP性质 · 松弛的两条不变量

1. 上界性：任何时刻，dist[v] 要么是 $\mathrm{\infty }$，要么等于某条真实 $s\to v$ 路径的长度。因此恒有 $\mathrm{dist}[v]\ge d(v)$——估计永远不会低于真相。
2. 单调性：dist[v] 只会减小，不会增大。每次生效的松弛都严格压低了某个估计。

第 1 条的证明是两行归纳：初始 dist[s]=0 是真实路径（零条边的路径）；每次生效的松弛令 dist[v] = dist[u] + w(u,v)，由归纳假设 dist[u] 对应一条真实路径，再接上边 $(u,v)$ 仍是一条真实路径。注意这一论证不要求边权非负——负边也只会把上界往下压。

而"压到什么时候才算完"，依赖一条更深的结构性质：

THM定理 · 最优子结构（子路径最优性）

设 $P$ 是 $s\to v$ 的一条最短路径，$Q$ 是 $P$ 中从 $x$ 到 $y$ 的一段子路径，则 $Q$ 是 $x\to y$ 的最短路径。

PROOF证明

反设存在更短的 $x\to y$ 路径 $Q^{\prime }$。把 $P$ 中的 $Q$ 剪下、贴上 $Q^{\prime }$，得到一条更短的 $s\to v$ 路径，与 $P$ 最短矛盾。（论证只用到"路径长度是各段之和"，因此允许负边；唯一的前提是图中不存在负环——否则"最短路径"本身就无定义。）

这条定理是全文的隐形骨架：Dijkstra 靠它保证"确定顶点的最短路只经过更早确定的顶点"，Floyd 靠它把一条路径从中转点处干净地切成两半。

接下来全部问题简化成一句话：按什么顺序施加松弛？ 三种答案，对应本页三幕：

算法	松弛的调度策略	思想阵营	适用
BFS	按层：先松弛离源点近的边	按层自然有序	无权图
Dijkstra	每轮挑当前 dist 最小的顶点，松弛其所有出边	贪心	非负权
Floyd	按中转点：第 $k$ 轮松弛所有"经 $k$ 中转"的组合	动态规划	全源、可有负边
Bellman-Ford（拓展）	无差别：全部边松弛 $n-1$ 轮	迭代收敛	有负权、可检测负环

第一幕 · 无权图：BFS 为什么天然正确

先考察最简单的版本：假设骑手只关心经过的路段数（每条路耗时相同），即无权图。这个问题 7.1 的 BFS 已经能解，但在接受答案之前，先复盘两个"想当然"的方案是怎么被pass掉的。

两条歧路

歧路一：每步走眼前最短的边。 以从 $A$ 去 $C$ 为例：从 $A$ 出发，可选 $A\to B$（$1$）、$A\to C$（$4$）、$A\to F$（$10$），贪心策略会挑最便宜的 $A\to B$。可到了 $B$ 才发现，通往 $C$ 的路只剩 $B\to C$（$8$）这一条，总计 $9$——而直接 $A\to C$ 只要 $4$。

ANTI反例 · 局部最优 ≠ 全局最优

"每步选当前最优"的贪心在图上没有免疫力：一条便宜的开局边可能把你引向一片昂贵的区域。后面 Dijkstra 的成功恰恰在于它不是这样贪心的——它贪心的是"整个顶点的当前总距离"，而非"单条边"。

歧路二：枚举所有路径，取最短。 数学上无懈可击，工程上是天方夜谭：$n$ 个顶点的图中两点间简单路径可以多到指数级（本页的小图从 $A$ 到 $F$ 已有 $9$ 条简单路径，且一旦允许绕环，"所有路径"直接变成无穷多条）。穷举不可行，必须利用结构。

转机：距离是"分层"的

无权图有一个带权图没有的美妙性质：距离为 $k+1$ 的顶点，只能从距离为 $k$ 的顶点一步到达。换句话说，顶点天然按距离分层，而 BFS 的队列恰好按层分发。

// graph[u] = {u 的所有出边邻居}；返回 s 到各顶点的边数距离（不可达为 -1）
std::vector<int> bfs(const std::vector<std::vector<int>>& graph, int s) {
    int n = static_cast<int>(graph.size());
    std::vector<int> dist(n, -1);          // -1 兼作"未访问"标记
    std::queue<int> q;
    dist[s] = 0;                           // 入队即赋距离
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u])
            if (dist[v] == -1) {           // 只在第一次到达时处理
                dist[v] = dist[u] + 1;     // 本质：relax(u, v)，且必生效
                q.push(v);
            }
    }
    return dist;
}

bfs.cpp

注意第 12 行正是松弛：dist[u] + 1 < dist[v]（此处 dist[v] 为 $\mathrm{\infty }$）恒成立、必生效。BFS 就是一种松弛顺序——每条边至多被检查一次（只有未访问的邻居才触发松弛），且触发松弛时 dist[u] 已是最终值。

在例图上运行（邻居按字母序）：

层	顶点	本层新发现（来源）
$0$	$A$	—
$1$	$B,C,F$	$B,C,F$ 均由 $A$ 直达
$2$	$D,E$	$D$ 由 $B$，$E$ 由 $C$

即跳数意义上 $A\to F$ 的"最短路"是直达边 $A\to F$（$1$ 跳）。

论证 BFS 的正确性

THM定理 · BFS 的正确性（归纳证明）

无权图中，BFS 结束时 $\mathrm{dist}[v]=d(v)$ 对所有可达顶点成立。

PROOF证明

对出队次序归纳，证明更强的命题：顶点按 $d$ 值非降的次序出队，且每个顶点入队的那一刻 dist 已经正确。

先看队列的结构：任何时刻队列中只存在距离为 $d$ 与 $d+1$ 的顶点，且 $d$ 在前 $d+1$ 在后（初始只有 $d=0$ 的 $s$；出队一个 $d$ 层顶点，至多向队尾加入 $d+1$ 层顶点）。因此出队次序按 $d$ 非降。

再看赋值的正确性。注意 BFS 中每个顶点的 dist 只在入队时被赋值一次、此后不再改变。对出队次序归纳，归纳假设是"此前每次出队所引发的赋值都正确"。基础：$\mathrm{dist}[s]=0=d(s)$。归纳步骤：$u$ 是被某个更早出队的顶点 $x$ 入队的，由归纳假设 $\mathrm{dist}[u]$ 的赋值正确。出队 $u$（$d(u)=d$）时，考察它的任一未访问邻居 $v$：

• 若 $d(v)<d$，取 $s\to v$ 最短路径上 $v$ 的前驱 $w$，则 $d(w)=d(v)-1<d=d(u)$。由出队次序非降，$w$ 在 $u$ 之前出队；而 $v$ 此刻仍未访问，在 $w$ 出队时必然也未访问，故当时就该被标记——矛盾。
• 若 $d(v)=d$，同样取前驱 $w$，$d(w)=d-1<d$，$w$ 在 $u$ 之前出队，$v$ 当时未访问，同样矛盾。
• 故 $d(v)=d+1$，赋值 $\mathrm{dist}[v]=\mathrm{dist}[u]+1=d+1$ 正确。

归纳完成。

本幕理论概要

结论	数学依据
BFS 求出的就是无权最短路	归纳法：出队序 = 距离非降序；层 $k$ 恰由层 $k-1$ 一步到达
dist 始终是真实路径长度（上界）	松弛不变量 1，与边权符号无关
每条边至多检查一次，$O(n+m)$	入队即标记，每个顶点至多产生一轮出边扫描
贪"单条边"不可行	反例：$A\to B\to C=9>A\to C=4$
穷举不可行	简单路径数指数级；含环则路径无穷

第二幕 · 非负权图：Dijkstra 的贪心

崩溃现场

路段耗时不尽相同——这才是现实。第一幕的结论在此处作废：

ANTI反例 · BFS 在带权图上失效

例图中 $A\to F$ 直达 $1$ 跳、耗时 $10$；而 $A\to B\to D\to E\to F$ 共 $4$ 跳、耗时 $1+3+2+1=7$。BFS 只数跳数，会理直气壮地推荐直达边，多花 $3$ 分钟。

问题在于：跳数的层序等于距离的序，只当每条边权相等时才成立。边权一旦不均匀，"先访问"就不再意味着"更近"。

从"按层"到"按距离"

修补的思路是直面崩溃的原因：既然层序失效，就改成按当前估计距离排序——每一轮，把估计表中数字最小且尚未敲定的顶点找出来，宣布它的估计就是最终答案，然后用它的出边做一轮松弛。这就是 Dijkstra 算法。

它的算法正确性由一条不变量支撑：

PROP性质 · Dijkstra 的核心不变量

边权非负时，每当顶点 $u$ 以最小 dist[u] 被选出，必有 $\mathrm{dist}[u]=d(u)$。已确定顶点的 dist 从此永不反悔。

// graph[u] = {(邻居, 边权), ...}，边权非负；prev 记录前驱用于还原路径
std::vector<int> dijkstra(int s, const std::vector<std::vector<std::pair<int,int>>>& graph,
                          std::vector<int>& prev) {
    int n = static_cast<int>(graph.size());
    prev.assign(n, -1);
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> dist(n, INF);
    std::vector<bool> done(n, false);      // done[u]：u 是否已确定
    using P = std::pair<int,int>;          // (dist, vertex)，小根堆
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (done[u]) continue;             // 堆里的过期记录，丢弃
        done[u] = true;                    // 此刻 dist[u] 即最终答案
        for (auto [v, w] : graph[u])
            if (!done[v] && dist[u] + w < dist[v]) {   // relax(u, v)
                dist[v] = dist[u] + w;
                prev[v] = u;               // 记住"是谁把我压短的"
                pq.push({dist[v], v});
            }
    }
    return dist;
}

dijkstra.cpp

两个细节值得关注：

• 第 15 行跳过 done[u] 的记录：懒惰删除的堆里同一个顶点可能有多条过期记录，只有等于当前 dist[u] 的那条是新鲜的。确定即永不再动。
• 第 18 行对已确定顶点不再松弛——保证（并要求）不变量成立。

手算 Dijkstra：例图全程

源点 $A$。下表每行记录一次"出队确定"及本轮松弛效果（加粗为变化；平手时按字母序出队，不影响最终结果）：

轮次	出队（确定）	dist[B]	dist[C]	dist[D]	dist[E]	dist[F]	本轮松弛记录
初始	—	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$A$ 入队，$\mathrm{dist}[A]=0$，其余 $\mathrm{\infty }$
1	$A(0)$	$1$	$4$	$\mathrm{\infty }$	$\mathrm{\infty }$	$10$	初始化三条出边
2	$B(1)$	$1$	$4$	$4$	$\mathrm{\infty }$	$10$	$D$：$\mathrm{\infty }\to 4$（$A\to B\to D$）；经 $B$ 到 $C$ 需 $9>4$，不动
3	$C(4)$	$1$	$4$	$4$	$9$	$10$	$E$：$\mathrm{\infty }\to 9$（$A\to C\to E$）；$C\to D$ 需 $5>4$，不动
4	$D(4)$	$1$	$4$	$4$	$6$	$10$	$E$：$9\to 6$（改走 $A\to B\to D\to E$）；$D\to F$ 需 $10$，与现状并列，不动
5	$E(6)$	$1$	$4$	$4$	$6$	$7$	$F$：$10\to 7$（经 $E$ 最后一跳）
6	$F(7)$	—	—	—	—	—	全部确定，算法结束

三轮细节各藏一个教学点：

1. 估计可以反复压低：$E$ 的估计先被 $C$ 压到 $9$，再被 $D$ 压到 $6$——松弛不是依赖一次性判决，而是持续逼近。
2. 并列不更新：第 4 轮 $D\to F$ 给出的 $10$ 与当前值并列，松弛不生效。若写成 $\le$，路径记录会被无意义地覆盖。
3. 迟来的翻盘：直达边 $A\to F$（$10$）从第 1 轮起就躺在表里，但直到第 5 轮才被 $A\to B\to D\to E\to F$（$7$）淘汰。贪心选的是顶点的总距离，所以"开局便宜但后劲不足"的路径骗不了它——这正是它与第一幕"歧路一"的本质区别。

由 prev 链 $F\leftarrow E\leftarrow D\leftarrow B\leftarrow A$ 还原出路径 $A\to B\to D\to E\to F$，总耗时 $7$。

O(·)复杂度

邻接表 + 二叉堆：每个可达顶点至多被确定一次，确定时扫描其全部出边，因此每条边在整个算法中至多被扫描一次。每次生效的松弛会产生一条新堆记录，最多 $m$ 次；连同源点的初始记录，以及随后弹出的过期记录，入堆与出堆操作总数均为 $O(n+m)$。每次堆操作耗时 $O(\log n)$，总计 $O((n+m)\log n)$。稠密图（$m\approx n^2$）改用朴素数组版（每轮线性扫最小、总 $O(n^2)$）反而更优。

论证 Dijkstra 的正确性

THM定理 · Dijkstra 的正确性（非负权前提）

所有边权 $w\ge 0$ 时，Dijkstra 每次出队确定的顶点 $u$ 都满足 $\mathrm{dist}[u]=d(u)$。

PROOF证明

反证法。设 $u$ 是第一个被错误确定的顶点（此前的确定全部正确）。

取一条真正的最短路径 $P:s\to \cdots \to u$。$s$ 已正确确定，$u$ 未确定，故 $P$ 上存在第一条"由已确定跨向未确定"的边 $(x,y)$。

• $x$ 在 $u$ 之前确定且确定无误，故 $\mathrm{dist}[x]=d(x)$；
• $x$ 确定时松弛过 $(x,y)$，因此 $\mathrm{dist}[y]\le d(x)+w(x,y)$，恰是 $P$ 上 $s\to y$ 前缀的长度 $\ell$；
• 前缀不超过整条路径：$\ell \le d(u)$，这一步用到 $P$ 的 $y\to u$ 尾段权非负；
• $u$ 是本轮未确定顶点中 dist 最小者：$\mathrm{dist}[u]\le \mathrm{dist}[y]$。

串起来：$\mathrm{dist}[u]\le \mathrm{dist}[y]\le \ell \le d(u)\le \mathrm{dist}[u]$（最后一步是上界不变量）。全部取等号，故 $\mathrm{dist}[u]=d(u)$，与"错误"矛盾。证毕。

请特别注意非负权在哪里上场：仅在"前缀 $\le$ 整条路径"一步。整条证明的其余部分对负边同样成立——所以负边摧毁 Dijkstra 的方式非常精准，见下节。

它也有软肋：负权边

ANTI反例 · Dijkstra 遇负边不可用

三点图：$A\to B$ 权 $1$，$A\to C$ 权 $2$，$C\to B$ 权 $-2$。真实最短路 $d(A,B)=0$（走 $A\to C\to B$）。但 Dijkstra 第一个出队的就是 $B$（估计 $1<2$），宣布 $\mathrm{dist}[B]=1$ 并盖上"已确定"的封印；随后 $C$ 出队想松弛 $C\to B$ 时，$B$ 已 done，更新被第 17 行的 !done[v] 拦截。最终答案 $1\ne 0$。

对照上节证明：$y\to u$ 尾段权为负，"前缀 $\le$ 整条路径"失效，反证链条在关键一环断裂。

本幕理论概要

结论	数学依据
出队即最终（核心不变量）	反证法 + "第一个错误顶点"论证；非负权保证路径前缀 $\le$ 全长
dist 始终 $\ge d$，只降不升	松弛的两条不变量
已确定顶点的最短路只经过更早确定的顶点	最优子结构：最短路径的每个前缀也是最短的
平列（$\le$ vs $<$）会污染路径还原	松弛定义取严格小于
负边下失效，且失效点可精确定位	反例 + 证明中唯一使用非负性的一步
$O((n+m)\log n)$；稠密图 $O(n^2)$	堆操作计数；稠密时堆反成负担

第三幕 · 全源：Floyd 的动态规划

新问法

平台要把生意做大：预计算任意两个地点之间的最短耗时，生成一张 $6\times 6$ 的运费表。最直接的想法是"单源跑 $6$ 遍"——Dijkstra 跑 $n$ 遍，非负权下 $O(nm\log n)$。可行，但换个思路，就能得到一个短得惊人、且兼容负权的算法。

与其选边，不如选中转点

前两幕的松弛都沿着边推进。Floyd 换了枚举的维度：不问"下一条边选谁"，而问"允许谁当中转站"。

DEF定义 · Floyd 的状态

记 $d^{(k)}(i,j)$ 为只允许 $v_1,\dots ,v_k$ 充当中间顶点时，$i\to j$ 的最短路径长度。$d^{(0)}(i,j)$ 就是邻接矩阵：不经任何中转，直达边权或 $\mathrm{\infty }$。

THM定理 · Floyd 递推式

$$d^{(k)}(i,j)=min(d^{(k-1)}(i,j),d^{(k-1)}(i,k)+d^{(k-1)}(k,j)).$$

PROOF证明

对最优路径是否经过 $v_k$ 分类讨论：

• 不经过 $v_k$：中间顶点仍全部落在 $\{v_1,\dots ,v_{k-1}\}$，答案即 $d^{(k-1)}(i,j)$；
• 经过 $v_k$：由子路径最优性，从 $v_k$ 处把路径切成 $i\to v_k$ 与 $v_k\to j$ 两半，两半都是各自端点间的最短路，且中间顶点只能来自前 $k-1$ 个（一条无负环的最短路不会两次经过 $v_k$），故长度为 $d^{(k-1)}(i,k)+d^{(k-1)}(k,j)$。

两者取小即得。

代码极短：

// d 初始为邻接矩阵（无边处 INF，对角线 0）；nxt 记录后继用于还原路径
void floyd(std::vector<std::vector<int>>& d, std::vector<std::vector<int>>& nxt, int n) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            nxt[i][j] = (i == j || d[i][j] == INF) ? -1 : j;
    for (int k = 0; k < n; ++k)                    // 中转点必须是【最外层】
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (d[i][k] < INF && d[k][j] < INF &&
                    d[i][k] + d[k][j] < d[i][j]) { // relax：经 k 中转
                    d[i][j] = d[i][k] + d[k][j];
                    nxt[i][j] = nxt[i][k];         // 路径第一跳改为 i 的去向
                }
}

floyd.cpp

两个细节：

WARN易错点 · 三个细节

1. $k$ 必须在最外层。递推式从 $k-1$ 推到 $k$，把 $k$ 放进内层等于在同一轮里混用新旧状态，某些需要"先经 $k$ 中转两段、再拼起来"的路径会算错。$i,j$ 两层可以互换，$k$ 不行。
2. 二维数组为什么够：按理需要三维 $d(k,i,j)$。但第 $k$ 轮里想修改 $d(i,k)$，唯一的候选是"经 $k$ 自己中转"，即要求 $d(i,k)+d(k,k)<d(i,k)$，等价于 $d(k,k)<0$——这意味着存在一条过 $k$ 的负环，无负环的图中不可能发生。$d(k,j)$ 同理。因此第 $k$ 轮原地读到的旧值与"上一轮的值"完全一致，第三维可以安全滚掉。
3. nxt[i][j] = nxt[i][k] 而非 = k：后继矩阵记录的是"下一步去哪"。改经 $k$ 中转后，第一步走的是 $i$ 原本通往 $k$ 的第一步，不是 $k$ 本身。

手算 Floyd：例图全程

为与代码的下标对应，约定顶点编号 $v_1=A,v_2=B,v_3=C,v_4=D,v_5=E,v_6=F$；"第 $k$ 轮"即允许 $v_1,\dots ,v_k$ 充当中转点。初始矩阵 $D^{(0)}$（行是起点 $i$，列是终点 $j$，$\mathrm{\infty }$ 表示暂不可达）：

$D^{(0)}$	$A$	$B$	$C$	$D$	$E$	$F$
$A$	$0$	$1$	$4$	$\mathrm{\infty }$	$\mathrm{\infty }$	$10$
$B$	$\mathrm{\infty }$	$0$	$8$	$3$	$\mathrm{\infty }$	$\mathrm{\infty }$
$C$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$	$1$	$5$	$\mathrm{\infty }$
$D$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$	$2$	$6$
$E$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$	$1$
$F$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$

六轮迭代中只有四轮有更新（这也提示：Floyd 对"稀疏无环味的图"做了很多无用功，见终幕选型表）：

中转点 $k$	生效的松弛	说明
$A$	无	没有任何边指向 $A$，$A$ 当不了中转站
$B$	$(A,D):\mathrm{\infty }\to 4$	发现 $A\to B\to D$
$C$	$(A,E):\mathrm{\infty }\to 9$；$(B,E):\mathrm{\infty }\to 13$	经 $C$ 到 $E$；$(A,D)$ 尝试 $4+1=5>4$ 不动
$D$	$(A,E):9\to 6$；$(B,E):13\to 5$；$(C,E):5\to 3$；$(B,F):\mathrm{\infty }\to 9$；$(C,F):\mathrm{\infty }\to 7$	大丰收；$(A,F)$ 尝试 $4+6=10$ 与现状并列，不动
$E$	$(A,F):10\to 7$；$(B,F):9\to 6$；$(C,F):7\to 4$；$(D,F):6\to 3$	每行都经 $E$ 最后一跳压低
$F$	无	$F$ 没有出边，当不了中转站

最终矩阵 $D^{(6)}$：

$D^{(6)}$	$A$	$B$	$C$	$D$	$E$	$F$
$A$	$0$	$1$	$4$	$4$	$6$	$\mathbf{7}$
$B$	$\mathrm{\infty }$	$0$	$8$	$3$	$5$	$6$
$C$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$	$1$	$3$	$4$
$D$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$	$2$	$3$
$E$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$	$1$
$F$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$0$

交叉验证：加粗的 $d(A,F)=7$ 与第二幕 Dijkstra 手算结果完全一致——两个阵营的算法在同一张图上会师。另请注意第 $k$ 轮真正可能改善的，是能以 $k$ 为中转、且 $d(i,k)$ 与 $d(k,j)$ 均有限的格子——例如第 $C$ 轮更新的 $(A,E)$ 与 $C$ 的行、列毫无关系；而 $A$ 没有入边、$F$ 没有出边，各自都当不了中转站，所以第 $A$、$F$ 轮颗粒无收。此图是无环有向图（DAG），终表中的 $\mathrm{\infty }$ 都对应"根本无路可达"的点对。

负权与负环

Floyd 的递推式不要求边权非负——它单纯枚举所有中转组合，负边带来的"更短"会被正常捕捉。但它有一个死穴：

WARN易错点 · 负环

若图中存在总权为负的环，绕环每圈都更短，最短路径趋于 $-\mathrm{\infty }$，问题本身失去定义。Floyd 跑完后若发现 $d(i,i)<0$，即判定 $i$ 处于某条总权为负的闭路上（负闭路中必然包含负环）——对角线是一个现成的负环探测器。同理，递推式证明中"最短路不会两次经过 $v_k$"也以无负环为前提。

本幕理论概要

结论	数学依据
递推式 $d^{(k)}=min(d^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})$	DP：按"是否经 $v_k$ 中转"分类 + 子路径最优性切分
三维可滚动为二维	第 $k$ 轮不改第 $k$ 行/列（$d(k,k)=0$，无负环）
$k$ 必须最外层	状态转移要求"先备齐前 $k-1$ 轮的结果"
允许负边、不能有负环	反例即机理：负环使 $d\to -\mathrm{\infty }$；$d(i,i)<0$ 可检测
$O(n^3)$、$O(n^2)$ 空间	三重定长循环、二维矩阵

终幕 · 选型：挑装备

三个算法同源于松弛，分流于调度。选型的第一步是看清图的性质：

边权情况？── 无权 ──────────────► BFS            O(n+m)
        ├── 非负 + 单源 ─────────► Dijkstra      O((n+m)log n)（稠密 O(n²)）
        ├── 含负权 + 单源 ────────► Bellman-Ford  O(nm)（拓展阅读）
        └── 全源（任意点对）──────► Floyd         O(n³)（顶点少时最省心）

decision.txt

维度	BFS	Dijkstra	Floyd	Bellman-Ford
解决的问题	无权单源	非负权单源	全源	任意权单源
思想	按层松弛	贪心（按距离选顶点）	DP（按中转点）	全边迭代收敛
复杂度	$O(n+m)$	$O((n+m)\log n)$ / $O(n^2)$	$O(n^3)$	$O(nm)$
负边	—（无权）	不允许	允许	允许
负环检测	—	—	$d(i,i)<0$	第 $n$ 轮仍可松弛
典型场景	社交关系度数	地图导航、网络路由	$n\le$ 数百的运费表	带折扣/返利的费用图

回到骑手：例图同源三问的答案放在同一张表里对照——

问题	算法	答案
$A$ 到 $F$ 最少几跳？	BFS	$1$ 跳（直达）
$A$ 到 $F$ 最少几分钟？	Dijkstra	$7$ 分钟（$A\to B\to D\to E\to F$）
任意两地的耗时表？	Floyd	$D^{(6)}$ 全矩阵

小结

• 松弛是全文的主线：dist[v] = min(dist[v], dist[u] + w) 这一个操作，配上"上界、单调"两条不变量，构成了所有最短路算法的公共内核；算法之间真正的差别只是施加松弛的顺序。
• BFS 的正确性来自无权图的分层结构（归纳证明：出队序即距离非降序）。
• Dijkstra 的正确性来自非负权下的"前缀 $\le$ 全长"（反证法：第一个被错确定的顶点导致整条不等式链闭合为等号）；它贪心的是顶点总距离，不是单条边。
• Floyd 的正确性来自动态规划：按中转点扩张可选集，递推式由"是否经过 $v_k$"的分类与子路径最优性保证；$k$ 在最外层、二维滚动安全、负环可由对角线检测。
• 选型先看图：权值有无与符号、单源还是全源、稠密还是稀疏——先回答这三个问题，算法基本就选定了。

练习与自测

（答案已折叠）

1. 改权再算 Dijkstra

把例图的 $A\to F$ 权从 $10$ 改成 $6$，完整手算 Dijkstra 全过程。$\mathrm{dist}[F]$ 与最短路径如何变化？哪一轮出现"直达边反超"？

点击展开答案

只有初始状态与最后两轮发生变化：

轮次	出队（确定）	dist[B]	dist[C]	dist[D]	dist[E]	dist[F]	本轮松弛记录
初始	—	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	$\mathrm{\infty }$	直达边权改为 $6$；$A$ 入队，其余 $\mathrm{\infty }$
1	$A(0)$	$1$	$4$	$\mathrm{\infty }$	$\mathrm{\infty }$	$6$	初始化三条出边
2	$B(1)$	$1$	$4$	$4$	$\mathrm{\infty }$	$6$	$D$：$\mathrm{\infty }\to 4$
3	$C(4)$	$1$	$4$	$4$	$9$	$6$	$E$：$\mathrm{\infty }\to 9$
4	$D(4)$	$1$	$4$	$4$	$6$	$6$	$E$：$9\to 6$；$D\to F$ 需 $10>6$，不动
5	$E(6)$	$1$	$4$	$4$	$6$	$6$	$E\to F$ 需 $7>6$，不动
6	$F(6)$	—	—	—	—	—	全部确定

$\mathrm{dist}[F]=6$，最短路径就是直达边 $A\to F$。"直达边反超"一轮都不会出现——反超的前提是"绕行比直达便宜"，而 $10\to 6$ 之后直达边从第一轮起就一路领先。原例中"迟来的翻盘"在这里变成了"先发制人"。

2. 构造反例

构造一个只有 $4$ 个顶点的图，使得"跳数最少的路径"与"边权和最小的路径"不是同一条；再构造一个"每步走当前最短边"策略会失败的例子。

点击展开答案

(1) 跳数最少 $\ne$ 权和最小：取顶点 $S,X,Y,T$ 与边 $S\to T(10)$、$S\to Y(1)$、$Y\to T(1)$、$S\to X(5)$、$X\to T(5)$。跳数最少的路径是直达 $S\to T$（$1$ 跳，权 $10$）；权和最小的路径是 $S\to Y\to T$（$2$ 跳，权 $2$）。BFS 只认跳数，会推荐错误的那条。

(2) 每步走当前最短边失败：取顶点 $S,A,B,T$ 与边 $S\to A(1)$、$A\to T(100)$、$S\to B(3)$、$B\to T(1)$。贪心策略在 $S$ 处选了便宜的 $A$（$1<3$），之后只能硬着头皮走 $A\to T$，总计 $101$；而 $S\to B\to T$ 只要 $4$。

两个反例的共同病根：单条边的便宜不代表整条路径的便宜——这正是第二幕 Dijkstra"按顶点总距离贪心"要修正的对象。

3. 定位非负权上场的唯一一步

复述 Dijkstra 正确性证明中唯一用到"边权非负"的一步，并解释为什么去掉这个前提该步不成立（配一个 3 顶点反例图）。

点击展开答案

唯一的一步是："路径前缀不超过整条路径"，即 $\ell \le d(u)$——它依赖 $P$ 上 $y\to u$ 尾段的边权非负。一旦尾段含负边，"更长"反而可能"更短"，前缀长度可以超过整条路径，反证法的不等式链在此断裂。

反例（3 顶点）：$A\to B$ 权 $1$，$A\to C$ 权 $2$，$C\to B$ 权 $-2$。真实最短路 $d(A,B)=0$（走 $A\to C\to B$）。对应到证明里：第一个被（错误）确定的顶点 $u=B$，跨边 $(x,y)=(A,C)$，前缀 $\ell =d(A,C)=2$，尾段 $C\to B$ 权 $-2$ 为负，"$\ell \le d(u)$"变成 $2\le 0$，恰好不成立——出错的位置与证明断裂的位置精确重合。

4. $k$ 放进内层的代价

把 Floyd 的三重循环改为 $i,j,k$ 顺序（$k$ 在最内层），构造一个会得到错误答案的具体小图。

点击展开答案

取 4 个顶点 $A,B,C,D$ 与三条边 $A\to B(1)$、$B\to D(1)$、$D\to C(1)$（一条链）。

按 $i,j,k$ 顺序（$k$ 最内层）处理 $(A,C)$：$k$ 依次尝试 $A$（$d(A,A)+d(A,C)=\mathrm{\infty }$）、$B$（$d(A,B)+d(B,C)=1+\mathrm{\infty }$）、$C$（$\mathrm{\infty }+0$）、$D$（$d(A,D)+d(D,C)=\mathrm{\infty }+1$）——注意此时 $d(A,D)$ 还是 $\mathrm{\infty }$，因为它要靠 $(A,D)$ 这对点在 $k=B$ 时才能算出，而 $j=D$ 排在 $j=C$ 之后。于是 $d(A,C)$ 全程保持 $\mathrm{\infty }$，正确答案却是 $3$（$A\to B\to D\to C$）。

病根：$A\to C$ 的最短路需要 $B$、$D$ 两个中转依次接力，$k$ 在最内层意味着同一轮 $(i,j)$ 里新旧状态混用，前一个中转的成果还没就绪。$k$ 放最外层则保证：第 $k$ 轮开始时，"只经前 $k-1$ 个中转"的所有最短路都已备齐。

5. 给例图加一条负边

例图中加入一条 $C\to A$ 权为 $-5$ 的边：此时图中有无负环？Dijkstra 与 Floyd 各还能否使用？$d(A,E)$ 会变成多少？

点击展开答案

有负环：$A\to C\to A$ 总权 $4+(-5)=-1<0$。

• Dijkstra：不可用。它根本无法处理负权边（见第二幕反例），何况负环。
• Floyd：可以照常运行，但结果"没有意义"——它不会报错停止，而是忠实地把能绕负环的格子越压越低。运行结束后检查对角线，会发现 $d(A,A)=-1<0$，据此判定负环存在；这就是 Floyd 作为负环探测器的用法。
• $d(A,E)$：不再有有限值。每多绕一圈 $A\to C\to A$，从 $A$ 出发到 $E$ 的花费就再降 $1$，路径长度趋于 $-\mathrm{\infty }$——"最短路径"这个问题本身失去了定义。

6. nxt 记录的是"下一跳"，不是"中转点"

为什么 nxt[i][j] = nxt[i][k] 而不能写 nxt[i][j] = k？画图说明两种写法各自还原出的路径。

点击展开答案

nxt[i][j] 的语义是"从 $i$ 出发去 $j$，第一步走到哪"。当 $(i,j)$ 的最短路改为经 $k$ 中转后，从 $i$ 迈出的第一步是"$i$ 通往 $k$ 的路"的第一步，即 nxt[i][k]，而不是 $k$ 本身——除非 $i\to k$ 恰好是直达边，两者才碰巧相等。

用例图验证 $A\to F$（最短路 $A\to B\to D\to E\to F$）：

• 正确写法：更新链为 $\mathrm{nxt}[A][F]\leftarrow \mathrm{nxt}[A][E]\leftarrow \mathrm{nxt}[A][D]\leftarrow \mathrm{nxt}[A][B]=B$，最终 $\mathrm{nxt}[A][F]=B$。还原时反复查表：$A\to B\to D\to E\to F$，正确。
• 错误写法：最后一次生效松弛发生在第 $E$ 轮（中转 $E$），会记 $\mathrm{nxt}[A][F]=E$。还原时从 $A$ 直接"瞬移"到 $E$，得到 $A\to E\to F$——但 $A\to E$ 根本不是边，这段路走不通；即使按矩阵里的 $d(A,E)=6$ 计价，它描述的也只是"$A$ 经 $B,D$ 到 $E$"的路径，却被错误地当成了可直达的一步。

7. 证明：第 $k$ 轮里第 $k$ 行、第 $k$ 列不动

证明：Floyd 第 $k$ 轮迭代中，矩阵第 $k$ 行与第 $k$ 列的值保持不变（提示：$d(k,k)=0$，分"无负环"与"有负环"讨论）。

点击展开答案

第 $k$ 轮中，格子 $d(k,j)$ 想被更新，唯一的候选是"以 $k$ 自己为中转"：需要 $d(k,k)+d(k,j)<d(k,j)$，即 $d(k,k)<0$。列方向 $d(i,k)$ 同理。

无负环时：对角线恒有 $d(k,k)=0$（"从 $k$ 出发绕一圈回到 $k$"的任何闭路径权非负，否则它就是负环）。于是 $d(k,k)+d(k,j)=d(k,j)$，严格小于不成立，第 $k$ 行、第 $k$ 列纹丝不动——这正是"三维可以滚动成二维"的理论保证。

有负环时：若 $k$ 能到达某负环并返回，则到某一刻 $d(k,k)<0$，此后 $d(k,k)+d(k,j)<d(k,j)$ 严格成立，第 $k$ 行（列）会在本轮内被持续压低——滚动安全性与"最短路存在性"同时被摧毁。这也解释了 Floyd 的负环检测原理：跑完全部轮次后，$d(i,i)<0$ 当且仅当 $i$ 处于某个负闭路上。

参考资料

• 王道《数据结构》考研复习指导：图的应用（最短路径：BFS、Dijkstra、Floyd）
• 严蔚敏《数据结构》（C 语言版）：图的最短路径
• 《算法导论》：第 24 章单源最短路径、第 25 章每对顶点间的最短路径（松弛性质与 Dijkstra 证明的严格版本）