第 24 章单源最短路径 (Single-Source Shortest Paths)

核心结论

问题形式化：给定带权有向图 \(G=(V,E)\) 与权函数 \(w:E \to \mathbb{R}\)，单源最短路径问题求从源点 \(s\) 到所有顶点 \(v \in V\) 的最短路径权重 \(\delta(s,v)\)；同时构造最短路径树 \(G_{\pi}\)。
最优子结构与松弛：最短路径的子路径仍是最短路径（引理 24.1）；本章所有算法都基于「松弛」(relaxation) 这一统一操作——逐步收紧上界 \(v.d\)。
Bellman-Ford 算法：在一般情形（含负权边）下工作，时间复杂度 \(O(VE)\)；第 \(|V|-1\) 轮后若仍可松弛，则存在源可达的负权环。
Dijkstra 算法：要求所有边权 \(\geq 0\)，用最小优先队列实现，时间复杂度 \(O((V+E)\lg V)\)（二叉堆）或 \(O(V\lg V + E)\)（斐波那契堆）。
DAG 最短路径：在有向无环图上按拓扑序松弛每条边恰好一次，时间 \(\Theta(V+E)\)；同时也是求关键路径 (PERT) 的工具。
差分约束系统：形如 \(x_j - x_i \leq b_k\) 的不等式组可通过构造辅助图与单源最短路径求解；Bellman-Ford 的负环检测同时给出可行性判定。

本章主旨

本章是图论算法的核心章节之一，承接第 22 章的图搜索与第 23 章的最小生成树，向第 25 章全源最短路径和第 26 章最大流铺垫。单源最短路径的四种典型算法（Bellman-Ford / DAG-SP / Dijkstra / 差分约束）共享「初始化 + 松弛 + 提取」三段式框架，差异仅在于松弛顺序与适用范围。负权边的处理是本章的技术难点——Bellman-Ford 与 DAG-SP 容忍负权但不容忍负环；Dijkstra 因贪心结构而要求非负权。

一、核心概念

本章围绕 6 个核心概念展开：从问题形式化出发，先给出松弛与最短路径树的通用机制，再依次讨论 Bellman-Ford、DAG 最短路径、Dijkstra 与差分约束四种算法，最后总结性质证明。

概念	定义 + 重要性	实现提示
最短路径形式化 (Shortest paths)	路径权 \(w(p)=\sum w(v_{i-1},v_i)\)；最短路径权重 \(\delta(s,v)\) 是所有 \(s \rightsquigarrow v\) 路径权重的下确界；负环可达时 \(-\infty\)，不可达时 \(+\infty\)。	§24.0；路径必须简单（无环），故最短路径长度 ≤ latexmath:[
V	-1]。	松弛 (Relaxation)
对边 \((u,v)\) 尝试通过 \(u\) 改进 \(v\) 的估计：若 \(v.d > u.d + w(u,v)\)，则更新 \(v.d\) 与前驱 \(v.\pi = u\)。	§24.0；是本章所有算法的唯一修改操作；初始为 \(+\infty\)，源点 \(s.d = 0\)。	Bellman-Ford 算法
对所有边做 latexmath:[	V	-1] 轮松弛；若有边在第 latexmath:[
V	] 轮仍可松弛，则存在源可达的负权环。	§24.1；时间 \(O(VE)\)；同时给出负环检测。
DAG 最短路径	在有向无环图上按拓扑序松弛出边；每条边松弛恰好一次，时间 \(\Theta(V+E)\)。	§24.2；DAG 无环故无负环；可用于 PERT 关键路径。
Dijkstra 算法	贪心框架：用最小优先队列维护「未确定」的顶点集合 \(Q = V \setminus S\)；每轮从 \(Q\) 取 \(d\) 最小的顶点 \(u\)，松弛其出边；要求边权非负。	§24.3；时间 \(O((V+E)\lg V)\)（二叉堆）或 \(O(V\lg V+E)\)（斐波那契堆）。
差分约束系统 (Difference constraints)	形如 \(x_j - x_i \leq b_k\) 的不等式组；构造辅助图 \(G = (V,E)\)，每个不等式对应一条边 \((v_i,v_j)\) 权 \(b_k\)，求单源最短路径给出可行解。	§24.4；负环 ⟺ 系统无解。

概念

定义 + 重要性

实现提示

最短路径形式化 (Shortest paths)

路径权 \(w(p)=\sum w(v_{i-1},v_i)\)；最短路径权重 \(\delta(s,v)\) 是所有 \(s \rightsquigarrow v\) 路径权重的下确界；负环可达时 \(-\infty\)，不可达时 \(+\infty\)。

§24.0；路径必须简单（无环），故最短路径长度 ≤ latexmath:[

-1]。

松弛 (Relaxation)

对边 \((u,v)\) 尝试通过 \(u\) 改进 \(v\) 的估计：若 \(v.d > u.d + w(u,v)\)，则更新 \(v.d\) 与前驱 \(v.\pi = u\)。

§24.0；是本章所有算法的唯一修改操作；初始为 \(+\infty\)，源点 \(s.d = 0\)。

Bellman-Ford 算法

对所有边做 latexmath:[

-1] 轮松弛；若有边在第 latexmath:[

] 轮仍可松弛，则存在源可达的负权环。

§24.1；时间 \(O(VE)\)；同时给出负环检测。

DAG 最短路径

在有向无环图上按拓扑序松弛出边；每条边松弛恰好一次，时间 \(\Theta(V+E)\)。

§24.2；DAG 无环故无负环；可用于 PERT 关键路径。

Dijkstra 算法

贪心框架：用最小优先队列维护「未确定」的顶点集合 \(Q = V \setminus S\)；每轮从 \(Q\) 取 \(d\) 最小的顶点 \(u\)，松弛其出边；要求边权非负。

§24.3；时间 \(O((V+E)\lg V)\)（二叉堆）或 \(O(V\lg V+E)\)（斐波那契堆）。

差分约束系统 (Difference constraints)

形如 \(x_j - x_i \leq b_k\) 的不等式组；构造辅助图 \(G = (V,E)\)，每个不等式对应一条边 \((v_i,v_j)\) 权 \(b_k\)，求单源最短路径给出可行解。

§24.4；负环 ⟺ 系统无解。

二、详细笔记

24.1 单源最短路径问题形式化

What：给定带权有向图 \(G=(V,E)\)、权函数 \(w:E \to \mathbb{R}\) 与源点 \(s \in V\)，求每个顶点 \(v \in V\) 的最短路径权重 \(\delta(s,v)\) 与一条最短路径。

Why：GPS 导航、网络路由、调度规划等大量现实问题都可抽象为单源最短路径；与第 25 章全源、第 26 章最大流形成图优化算法的三角。

How：

\[\delta(s,v) = \begin{cases} \min\{w(p) : s \overset{p}{\rightsquigarrow} v\} & \text{若 } s \rightsquigarrow v \text{ 存在}\\ +\infty & \text{若 } s \not\rightsquigarrow v\\ -\infty & \text{若存在负环} s \rightsquigarrow v \end{cases}\]

路径权：\(w(\langle v_0,v_1,\ldots,v_k\rangle) = \sum_{i=1}^{k} w(v_{i-1},v_i)\)。
最短路径必为简单路径（无环），长度 ≤ \(|V|-1\)（引理 24.1）。
边的权值可代表距离、时间、成本、损耗等线性可加量。

When：问题可建模为带权有向图，且关心「从某点出发到其余各点的最优路线」时。

Example：Phoenix 到 Indianapolis 的公路网，权值=英里数；导航系统调用 Dijkstra / Bellman-Ford 计算最优路线。

24.2 松弛操作与最短路径树

What：松弛 (relaxation) 是所有单源最短路径算法的基本操作：对边 \((u,v)\)，若经 \(u\) 能改进 \(v\) 的当前估计，则更新 \(v.d\) 与前驱 \(v.\pi\)。

Why：松弛是「无副作用的尝试性更新」——若新路径更短则接受，否则保持原值；这一操作既能维护正确性（一旦 \(v.d = \delta(s,v)\) 则不再变化），又能逐步逼近最优解。

How：

\[\text{RELAX}(u, v, w): \ \textbf{if } v.d > u.d + w(u,v): \quad v.d = u.d + w(u,v),\quad v.\pi = u\]

松弛的初始化（INITIALIZE-SINGLE-SOURCE）：

\(s.d = 0\)，\(v.d = +\infty\)（\(v \neq s\)）；
\(v.\pi = \text{NIL}\)，对所有 \(v\)。

性质（在 §24.5 中证明）：

三角不等式：\(\delta(s,v) \leq \delta(s,u) + w(u,v)\)。
上界性质：\(v.d \geq \delta(s,v)\) 始终成立。
收敛性质：若 \(u.d = \delta(s,u)\) 且松弛 \((u,v)\)，则此后 \(v.d = \delta(s,v)\)。
路径松弛性质：按最短路径顺序松弛 \((v_0,v_1), (v_1,v_2), \ldots\)，终点 \(v_k\) 即获 \(\delta(s,v_k)\)。

前驱子图 (predecessor subgraph) \(G_{\pi} = (V_{\pi}, E_{\pi})\)：由所有非 NIL 前驱顶点构成的树；算法终止时 \(G_{\pi}\) 即最短路径树。

When：每条边被松弛多少次？DAG-SP / Dijkstra 每条边松弛恰好一次；Bellman-Ford 每条边最多松弛 \(|V|-1\) 次。

Example：顶点 \(v.d=10\)、\(u.d=3\)、\(w(u,v)=2\)，则松弛后 \(v.d=5\)、\(v.\pi=u\)。

24.3 Bellman-Ford 算法

What：在一般情形（含负权边但不容忍源可达负环）下求单源最短路径，时间复杂度 \(O(VE)\)，并能检测负权环。

Why：实际应用中有时边权为负（如金融套利、化学反应能量差），Dijkstra 不适用；Bellman-Ford 是这种情况下唯一简单的多项式算法。

How：

伪代码（CLRS 第 651 页图 24.4）：

INITIALIZE-SINGLE-SOURCE(G, s)
for \(i = 1\) to \(|V|-1\): // 共 \(|V|-1\) 轮
1. for each edge \((u,v) \in E\): RELAX(u, v, w)
for each edge \((u,v) \in E\):
1. if \(v.d > u.d + w(u,v)\): return FALSE // 存在负环
return TRUE

正确性（定理 24.4）：

无负环时 \(|V|-1\) 轮后 \(v.d = \delta(s,v)\)。
推导：任何简单路径至多 \(|V|-1\) 条边；第 \(i\) 轮松弛恰好处理第 \(i\) 条边，由路径松弛性质得证。
负环检测：若有负环，第 \(|V|\) 轮必有边可继续松弛。

When：图含负权边但无负环；或在已知/未知是否存在负环时需自动判定（DAG-SP / Dijkstra 不具备此能力）。

Example：CLRS 图 24.4 的 5 顶点图：4 轮后 \(t.d=2, x.d=4, y.d=7, z.d=-2\)，返回 TRUE。

24.4 DAG 上的单源最短路径

What：在有向无环图 (DAG) 上求单源最短路径，时间复杂度 \(\Theta(V+E)\)，每条边松弛恰好一次。

Why：DAG 既无正环也无负环，最短路径必有良定义；拓扑序保证每次松弛时起点 \(u.d\) 已收敛；也是求 PERT 关键路径的工具。

How：

DAG-SHORTEST-PATHS(G, w, s)：

topologically sort vertices of G
INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex u taken in topologically sorted order:
1. for each vertex \(v \in G.\text{Adj}[u\)]: RELAX(u, v, w)

正确性（定理 24.5）：最短路径 \(p = \langle v_0, v_1, \ldots, v_k\rangle\) 中边按拓扑序松弛，故路径松弛性质在第 \(k\) 步生效。

PERT 应用：边权=任务时长，求最长路径（即关键路径，决定项目最短完工时间）：

方法 A：边权取负 + DAG-SHORTEST-PATHS。
方法 B：把「min」改「max」、\(+\infty\) 改 \(-\infty\)。

When：输入是有向无环图；或要在线性时间内求最长路径（用边权取负的变体）；PERT / 项目调度问题。

Example：CLRS 图 24.5 的 6 顶点 DAG，源点 \(s\)，6 个拓扑序步骤后所有 \(v.d\) 即最短路径权重。

24.5 Dijkstra 算法

What：在边权非负的带权有向图上求单源最短路径，用最小优先队列实现贪心扩展；时间复杂度 \(O((V+E)\lg V)\)（二叉堆）或 \(O(V\lg V+E)\)（斐波那契堆）。

Why：边权非负时贪心正确——每次从「未定」集合中取最小 \(d\) 的顶点，该顶点即获最终最短路径；这是单源最短路径最快的一般算法。

How：

DIJKSTRA(G, w, s)：

INITIALIZE-SINGLE-SOURCE(G, s)
\(S = \emptyset\)
\(Q = G.V\) // 最小优先队列，键为 \(v.d\)
while \(Q \neq \emptyset\):
1. \(u = \text{EXTRACT-MIN}(Q)\)
2. \(S = S \cup \{u\}\)
3. for each \(v \in G.\text{Adj}[u\)]: RELAX(u, v, w)

正确性（CLRS 定理 24.6）：边权非负时，每当 \(u\) 从 \(Q\) 取出，\(u.d = \delta(s,u)\)。直观：到 \(u\) 的最短路径只会经 \(S\) 中的顶点，否则会被更小的候选取代。

复杂度：

二叉堆 + 邻接表：\(O((V+E)\lg V)\)。
斐波那契堆：\(O(V\lg V + E)\)（适合稀疏图）。
数组实现：\(O(V^2)\)（适合稠密图）。

When：边权 ≥ 0；关心单源最短路径且图规模较大（GPS 路由默认算法）；不要求负环检测。

Example：CLRS 图 24.6 的 5 顶点非负权图，每轮从 \(Q\) 取出最小 \(d\) 顶点加入 \(S\)；4 轮后所有顶点进 \(S\)，路径树成型。

24.6 差分约束与最短路径

What：差分约束系统是形如 \(x_j - x_i \leq b_k\) 的不等式组（\(k = 1, \ldots, m\)）；通过构造辅助图并求单源最短路径可判定可行性与求可行解。

Why：大量调度与规划问题可自然写为差分约束（如「事件 A 比 B 至少早 3 天」）；Bellman-Ford 同时给出可行性判定（负环 = 无解）。

How：

构造辅助图 \(G = (V,E)\)：

顶点：每个变量 \(x_i\) 对应一个顶点 \(v_i\)，再加源点 \(v_0\)。
边：每个不等式 \(x_j - x_i \leq b_k\) 对应边 \((v_i, v_j)\) 权 \(b_k\)。
源点：加边 \((v_0, v_i)\) 权 \(0\)，对所有 \(i\)。

性质：

若 Bellman-Ford 在此图上无负环，则设 \(x_i = \delta(v_0, v_i)\) 即得可行解。
若存在负环，则系统无可行解。

典型应用：

雇员排班：每个员工每天排或不排，相邻日差约束。
系统差分约束：电路时序、生产计划。

When：问题是线性不等式组且每条只涉及两个变量的差；想用图算法而非单纯形法。

Example：不等式组

\[x_1 - x_2 \leq 3,\quad x_2 - x_3 \leq -2,\quad x_1 - x_3 \leq 2\]

构造 3 顶点图加源点；Bellman-Ford 求 \(\delta(v_0, \cdot)\) 即得可行解 \(x_1=3, x_2=0, x_3=2\)。

三、关键图表

核心公式对照表

公式编号

内容

式 24.1

路径权定义 \(w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)\)

引理 24.1

最短路径的子路径仍是最短路径（最优子结构）

引理 24.10

三角不等式 \(\delta(s,v) \leq \delta(s,u) + w(u,v)\)

引理 24.11

上界性质 \(v.d \geq \delta(s,v)\) 恒成立

引理 24.14

收敛性质：松弛 \((u,v)\) 后 \(v.d = \delta(s,v)\)

引理 24.15

路径松弛性质：按最短路径顺序松弛，终点即获最短值

引理 24.17

前驱子图性质：终止时 \(G_{\pi}\) 是最短路径树

定理 24.4

Bellman-Ford 正确性 + 负环检测

定理 24.5

DAG-SHORTEST-PATHS 正确性

定理 24.6

Dijkstra 正确性（要求非负权）

四、思维导图

mindmap
  root((第 24 章 单源最短路径))
    形式化
      δ(s,v)定义
      最短路径树
      负环情形
    松弛框架
      初始化
      RELAX操作
      通用性质
    Bellman-Ford
      O(VE)时间
      负环检测
      一般情形
    DAG最短路径
      拓扑序
      Θ(V+E)
      PERT关键路径
    Dijkstra算法
      贪心扩展
      非负权
      优先队列
    差分约束
      不等式组
      辅助图构造
      可行性判定

五、重点与易错点

单源 vs 全源：单源 (本章) vs 全源 (第 25 章)；前者跑一次，后者通常需要更精细的算法（如 Floyd-Warshall）。
负环可达时 \(\delta(s,v) = -\infty\)：不要试图对负环求最短路径，因为可无限绕环降低权值；Bellman-Ford 用此性质作负环检测。
0 权环可从最短路径中删除而不改变权值；正 / 负环则不能。
Dijkstra 不允许负权边：反例——负权边可能让「非最小估计的顶点先确定」之后又被降低，破坏贪心结构。
Bellman-Ford 的 \(|V|-1\) 轮来源：任何最短路径至多 \(|V|-1\) 条边（简单路径），故 \(|V|-1\) 轮路径松弛性质保证全部收敛。
松弛是唯一修改 \(v.d / v.\pi\) 的操作：算法正确性证明往往依赖此唯一性——若中途有其他赋值，证明即失效。
差分约束系统中「源点加 0 权出边」的技巧：保证所有顶点可达，从而最短路径良定义；同时源点 \(d=0\) 不会人为引入额外约束。
DAG-SP 不仅求最短路径，还能求最长路径（边权取负或改 RELAX 方向）——这是 PERT 关键路径的核心。
前驱子图是树而非一般图：最短路径不唯一时多棵最短路径树均合法（CLRS 图 24.2 给出两棵）。
Dijkstra 优先队列选用：稀疏图用斐波那契堆 \(O(V\lg V + E)\)，稠密图用数组 \(O(V^2)\)；二叉堆是折中。
与第 22 章 BFS 的关系：BFS 是边权全为 1 的特例；BFS 的最短路径树性质可视为 Dijkstra 在单位权图上的退化。
与第 25 章全源最短路径的衔接：从每个顶点跑 Bellman-Ford 即得 \(O(V^2 E)\) 的全源解；第 25 章给出更快的 \(O(V^3)\) / \(O(V^2 \lg V + VE)\) 算法。
与第 26 章最大流的衔接：最大流的 Edmonds-Karp 算法依赖 BFS 求增广路径，与本章 Bellman-Ford 共享「图上递推」的思路。
松弛的方向性：RELAX(u,v) 与 RELAX(v,u) 不同——前者更新 v，后者更新 v；算法框架决定方向。
Bellman-Ford 的提前终止优化：若某一轮无更新可提前结束；最坏仍是 \(O(VE)\)。

第 24 章 单源最短路径 (Single-Source Shortest Paths)

核心结论

一、核心概念

二、详细笔记

24.1 单源最短路径问题形式化

24.2 松弛操作与最短路径树

24.3 Bellman-Ford 算法

24.4 DAG 上的单源最短路径

24.5 Dijkstra 算法

24.6 差分约束与最短路径

三、关键图表

四、思维导图

五、重点与易错点

第 24 章单源最短路径 (Single-Source Shortest Paths)