本节从一个配送场景引出 BFS、Dijkstra 与 Floyd。三种算法都使用松弛操作，但它们组织状态和安排松弛顺序的方式不同，适用条件也不同。

引子：一次配送任务

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

7.3 配送例图：边上的数字表示从起点到终点的单向骑行耗时

为了避免示意图布局造成误读，下面列出本页例图的完整边集。后续手算均使用这组边。

边表把每条路线的起点、终点和耗时（即权重）列为一行：

起点	终点	耗时 $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$，其中每对相邻顶点之间都有边；在有向图中还必须依次存在 $v_i\to v_{i+1}$。路径的长度是各边权之和 $\sum _{i=0}^{k-1}w(v_i,v_{i+1})$；无权图视为每条边权为 $1$，此时长度就是边数。若所有 $u\to v$ 路径长度存在最小值，对应路径称为最短路径，最小长度记为 $d(u,v)$；不可达时记为 $\mathrm{\infty }$。若可经由负环把长度无限降低，则不存在有限最短距离，可记为 $-\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 与 Floyd，并在拓展中补充 Bellman-Ford：

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

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

先考察最简单的版本：只关心经过的路段数，也就是把每条边的代价都视为 $1$。这个无权最短路问题可以由 7.1 节的 BFS 解决。在推导 BFS 之前，先区分两种针对一般带权最短路的直接做法；它们分别存在正确性或效率问题。

两种不可行的直接做法

做法一：每步选择当前权值最小的边。 以从 $A$ 到 $C$ 为例：从 $A$ 出发，可选 $A\to B$（$1$）、$A\to C$（$4$）、$A\to F$（$10$）。若只比较当前边，就会选择 $A\to B$；但随后只能通过权值为 $8$ 的 $B\to C$ 到达 $C$，总权值为 $9$，反而大于直达边的 $4$。

ANTI反例 · 局部最小边不保证路径总权值最小

单条边权较小，不代表包含它的整条路径权值也较小。Dijkstra 比较的是从源点到候选顶点的当前总距离，而不是只比较下一条边的权值。

做法二：枚举所有路径后取最短。 这种定义直接但计算不可行：$n$ 个顶点的图中，两点间的简单路径数可能达到指数级。本页的小图从 $A$ 到 $F$ 已有 $9$ 条简单路径；在含环图中，若允许重复经过顶点和边，路径集合还可能是无限的。因此算法必须利用最短路径的结构，避免逐条枚举。

BFS 利用距离分层

无权图满足：距离为 $k+1$ 的顶点可以从某个距离为 $k$ 的顶点一步到达。换句话说，顶点可以按最短距离分层，而 BFS 的队列恰好按层处理。

// graph[u] = {u 的所有出边邻居}；dist 保存 s 到各顶点的边数距离（不可达为 -1）
std::vector<std::vector<int>> graph;
std::vector<int> dist;

void bfs(int s) {
    int n = static_cast<int>(graph.size());
    dist.assign(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);
            }
    }
}

bfs.cpp

第 12 行对应一次松弛：对尚未访问的 v，其距离可从 $\mathrm{\infty }$ 更新为 dist[u] + 1。BFS 按层安排这些松弛；每个可达顶点只会出队一次，每条有向边或无向边的每条邻接记录只会被扫描一次。

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

层	顶点	本层新发现（来源）
$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$。因为存在边 $(u,v)$，必有 $d(v)\le d+1$。下面排除更小的两种可能：

• 若 $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 最小化边数，因此会选择直达边，但这不是权值最小的路径。

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

从"按层"到"按距离"

Dijkstra 改为按当前估计距离选择顶点：每一轮找出 dist 最小且尚未确定的顶点，把它的当前估计确定为最终距离，再用它的出边执行松弛。边权非负时，这一步具有正确性保证。

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

PROP性质 · Dijkstra 的核心不变量

边权非负时，每当顶点 $u$ 以最小 dist[u] 被选出，必有 $\mathrm{dist}[u]=d(u)$；后续松弛不会再改变已确定顶点的距离。

// graph[u] = {(邻居, 边权), ...}，边权非负；prev 记录前驱用于还原路径
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<int> dist, prev;

void dijkstra(int s) {
    int n = static_cast<int>(graph.size());
    prev.assign(n, -1);                    // prev[v]：最短路上的前一个顶点
    const int INF = std::numeric_limits<int>::max();
    dist.assign(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;               // 记录使 dist[v] 变小的前驱
                pq.push({dist[v], v});
            }
    }
}

dijkstra.cpp

两个细节值得关注：

• 第 15 行跳过 done[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$，于是更新 dist[F]。Dijkstra 比较的是从源点到候选顶点的总距离，而不是当前单条边的权值——这正是它与前面“只比较当前边权”这一错误策略的本质区别。

由 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)$，与"错误"矛盾。证毕。

请特别注意证明中使用非负权的位置：只有“路径前缀的权值不超过整条路径”这一步依赖它。若允许负边，这个不等式可能不成立，见下节反例。

负权边为何使 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$ 个，故长度为 $d^{(k-1)}(i,k)+d^{(k-1)}(k,j)$。

两者取小即得。

代码极短：

// d 初始为邻接矩阵（无边处 INF，对角线 0）；nxt 记录后继用于还原路径
std::vector<std::vector<int>> dist, next_vertex;
int n;

void floyd() {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            next_vertex[i][j] = (i == j || dist[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 (dist[i][k] < INF && dist[k][j] < INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) { // relax：经 k 中转
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next_vertex[i][j] = next_vertex[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$ 轮读取第 $k$ 行和第 $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$ 处于某条总权为负的闭路上（负闭路中必然包含负环）——对角线是一个现成的负环探测器。要判断点对 $(s,t)$ 是否受负环影响，还需检查是否存在 $k$ 使 $s$ 可达 $k$、$d(k,k)<0$ 且 $k$ 可达 $t$。同理，递推式证明中"最短路不会两次经过 $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)$ 空间	三重定长循环、二维矩阵

算法选型：根据约束选择方法

这四种方法都使用松弛，但状态组织、调度顺序与终止条件不同。选型时先看任务范围和边权条件：

7.4 最短路径入门选型：先看任务范围，再检查边权条件

这是一张入门选型表，不覆盖所有规模组合。例如，大型稀疏非负权图的全源问题可以对每个源点运行 Dijkstra；允许负权的大型稀疏图还可考虑 Johnson 算法。

维度	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)}$ 全矩阵

完整解题范例

范例一：网络延迟时间

题目解读

有 n 个网络节点和 m 条有向边，边 u v w 表示信号从 u 到 v 需要 w 毫秒，所有权值均为正。源点 s 在时刻 0 发出信号，节点收到后会并行转发。求全部节点都收到信号的最早时刻；若存在不可达节点，输出 -1。

“并行传播”不是把所有边权相加：节点 v 的首次收到时间是 $d(s,v)$，全网完成时间是所有最短距离的最大值。

算法分析

边权非负，使用堆优化 Dijkstra。dist[v] 保存源点到 v 的当前最短估计；松弛成功后把新状态压入小根堆。堆中可能同时存在同一顶点的旧记录，因此弹出 (d,u) 时若 d != dist[u] 就跳过。

算法结束后扫描 dist：存在无穷值则输出 -1，否则输出最大距离。时间为 $O((n+m)\log n)$，空间为 $O(n+m)$。

伪代码

dist = 全 INF, dist[s] = 0
把 (0, s) 放入小根堆
while 堆非空:
    (d, u) = 弹出最小项
    if d != dist[u]: continue
    for (v, w) in graph[u]:
        if d + w < dist[v]:
            dist[v] = d + w
            压入 (dist[v], v)
if 存在 dist[v] == INF: 输出 -1
else 输出 max(dist)

network-delay.pseudo

最终代码

可编译 C++17 实现

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

struct Edge {
    int to;
    long long weight;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0, m = 0, source = 0;
    if (!(std::cin >> n >> m >> source)) return 0;
    std::vector<std::vector<Edge>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u = 0, v = 0;
        long long w = 0;
        std::cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }

    const long long INF = std::numeric_limits<long long>::max() / 4;
    std::vector<long long> dist(n, INF);
    using Entry = std::pair<long long, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> ready;
    dist[source] = 0;
    ready.push({0, source});

    while (!ready.empty()) {
        auto [d, u] = ready.top();
        ready.pop();
        if (d != dist[u]) continue;
        for (const Edge& edge : graph[u]) {
            if (d + edge.weight >= dist[edge.to]) continue;
            dist[edge.to] = d + edge.weight;
            ready.push({dist[edge.to], edge.to});
        }
    }

    long long answer = 0;
    for (long long d : dist) {
        if (d == INF) {
            std::cout << -1 << '\n';
            return 0;
        }
        answer = std::max(answer, d);
    }
    std::cout << answer << '\n';
}

network-delay-example.cpp

拓展、思考与变式

• 若需要输出最晚收到信号的节点，可在扫描最大距离时同时维护编号；
• 若所有边权都为 1，可改用 BFS，把复杂度降为 $O(n+m)$；
• 若允许负权边，应改用 Bellman-Ford，不能继续使用 Dijkstra；
• 对应练习：T18 · 07E18 · 网络延迟时间；可先完成 T17 · 07E17 · 朴素 Dijkstra 与路径还原。

范例二：Floyd 回答多组最短路径查询

题目解读

给定顶点数较少的有向带权图以及多组查询 (s,t)。图允许负权边但不含负环；可能有自环、平行边和不可达点对。每次查询需要输出最短距离以及完整顶点路径，不可达时输出 -1。

多组查询意味着不能每次都从头搜索；n\le300 时可以用 Floyd 预计算所有点对距离。平行边初始化时取最小权，路径还原使用后继矩阵 nxt。

算法分析

初始化 d[i][i]=0，边 u→v 令 d[u][v] 取最小权、nxt[u][v]=v。Floyd 按中转点 k 逐轮松弛；若经 k 使 d[i][j] 变小，就把第一跳改为 nxt[i][k]。

查询时从 s 开始不断令 u=nxt[u][t]，直到到达 t。预处理时间 $O(n^3)$、空间 $O(n^2)$，每次还原路径的时间与输出路径长度成正比。

伪代码

d[i][j] = INF, d[i][i] = 0, nxt[i][j] = -1
for 每条边 (u, v, w):
    if w < d[u][v]:
        d[u][v] = w
        nxt[u][v] = v
for k = 0 .. n-1:
    for i = 0 .. n-1:
        for j = 0 .. n-1:
            if i 能到 k 且 k 能到 j 且 d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]
                nxt[i][j] = nxt[i][k]
对每个查询 (s, t):
    若不可达输出 -1
    否则沿 nxt[*][t] 输出路径

floyd-queries.pseudo

最终代码

可编译 C++17 实现

#include <iostream>
#include <limits>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0, m = 0, query_count = 0;
    if (!(std::cin >> n >> m >> query_count)) return 0;
    const long long INF = std::numeric_limits<long long>::max() / 4;
    std::vector<std::vector<long long>> dist(
        n, std::vector<long long>(n, INF));
    std::vector<std::vector<int>> next(
        n, std::vector<int>(n, -1));
    for (int i = 0; i < n; ++i) dist[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int u = 0, v = 0;
        long long w = 0;
        std::cin >> u >> v >> w;
        if (w < dist[u][v]) {
            dist[u][v] = w;
            next[u][v] = v;
        }
    }

    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) continue;
                long long candidate = dist[i][k] + dist[k][j];
                if (candidate < dist[i][j]) {
                    dist[i][j] = candidate;
                    next[i][j] = next[i][k];
                }
            }
        }
    }

    while (query_count-- > 0) {
        int source = 0, target = 0;
        std::cin >> source >> target;
        if (source == target) {
            std::cout << "0: " << source << '\n';
            continue;
        }
        if (next[source][target] == -1) {
            std::cout << -1 << '\n';
            continue;
        }

        std::cout << dist[source][target] << ':';
        int current = source;
        while (current != target) {
            std::cout << ' ' << current;
            current = next[current][target];
        }
        std::cout << ' ' << target << '\n';
    }
}

floyd-queries-example.cpp

拓展、思考与变式

• 若只需要距离，不需要路径，可以删除 next 矩阵；
• 若查询很少、图稀疏且边权非负，对每个实际出现的源点运行一次 Dijkstra 可能更省；
• 若允许负环，应在 Floyd 后检查 dist[k][k] < 0，并进一步判断哪些查询点对受负环影响；
• 对应练习：T20 · 07E20 · Floyd 全源最短路径。

小结

• 松弛是全文的主线：dist[v] = min(dist[v], dist[u] + w) 是 BFS、Dijkstra、Bellman-Ford 以及 Floyd 状态转移中的共同更新形式。算法不仅调度顺序不同，维护的状态、可用前提和终止条件也不同。
• BFS 的正确性来自无权图的分层结构（归纳证明：出队序即距离非降序）。
• Dijkstra 的正确性来自非负权下的"前缀 $\le$ 全长"（反证法：第一个被错确定的顶点导致整条不等式链闭合为等号）；它贪心的是顶点总距离，不是单条边。
• Floyd 的正确性来自动态规划：按中转点扩张可选集，递推式由"是否经过 $v_k$"的分类与子路径最优性保证；$k$ 在最外层、二维滚动安全、负环可由对角线检测。
• 选型先看图：权值有无与符号、单源还是全源、稠密还是稀疏——先回答这三个问题，算法基本就选定了。

练习与自测

（答案已折叠）

1. 改权再算 Dijkstra

把例图的 $A\to F$ 权从 $10$ 改成 $6$，完整手算 Dijkstra 全过程。$\mathrm{dist}[F]$ 与最短路径如何变化？绕行路径是否曾经优于直达边？

点击展开答案

第 1 轮起，$F$ 的候选距离就从原例的 $10$ 变为 $6$；随后与 $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$。绕行路径从未优于直达边：第 4 轮得到的 $A\to B\to D\to F$ 权值为 $10$，第 5 轮得到的 $A\to B\to D\to E\to F$ 权值为 $7$，都大于 $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$ 处选择权值较小的边 $S\to 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. 证明 Floyd 二维原地更新的条件

证明：不存在负环时，Floyd 第 $k$ 轮迭代中，矩阵第 $k$ 行与第 $k$ 列保持不变；再说明存在相关负环时，这一结论为何可能失效。

点击展开答案

第 $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$ 出发并回到 $i$ 的负权闭路。

参考资料

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

代码题练习

按本节下方的 Lab 入口练习。下列入口使用稳定 Lab 编号。

• T16 · 07E16 · Dijkstra 逐轮推演
• T17 · 07E17 · 朴素 Dijkstra 与路径还原
• T18 · 07E18 · 网络延迟时间
• T19 · 07E19 · Bellman-Ford 与负环
• T20 · 07E20 · Floyd 全源最短路径
• T21 · 07E21 · 紧急救援
• T22 · 07E22 · 虫洞（Wormholes）