CS Wiki

第22章 单源最短路径-章节汇总

10分钟阅读

相关笔记

概览

全章围绕单源最短路径（Single-Source Shortest Paths, SSSP）问题展开。首先建立最短路径的基本性质（三角不等式、上界性质、收敛性质、路径松弛性质、前驱子图性质），为所有算法提供统一的理论基础（22.5）；然后给出三种经典算法——Bellman-Ford算法（处理一般图，支持负权边，22.1）、DAG最短路径算法（利用拓扑序，22.2）、Dijkstra算法（非负权图上的最优选择，22.3）；最后展示差分约束系统与最短路径问题的等价关系（22.4）。全章的核心主线是 松弛操作——所有算法都基于反复应用松弛操作来逐步逼近最短路径。

知识结构总览

flowchart TD
    A["第22章 单源最短路径"] --> B["理论基础 (22.5)"]
    A --> C["Bellman-Ford (22.1)"]
    A --> D["DAG最短路径 (22.2)"]
    A --> E["Dijkstra (22.3)"]
    A --> F["差分约束 (22.4)"]

    B --> B1["三角不等式"]
    B --> B2["上界性质"]
    B --> B3["收敛性质"]
    B --> B4["路径松弛性质"]
    B --> B5["前驱子图性质"]

    C --> C1["松弛操作"]
    C --> C2["|V|-1轮遍历所有边"]
    C --> C3["负权环检测"]
    C --> C4["O(VE)"]

    D --> D1["拓扑排序"]
    D --> D2["按拓扑序单轮松弛"]
    D --> D3["O(V+E)"]

    E --> E1["优先队列"]
    E --> E2["贪心选择"]
    E --> E3["仅非负权"]
    E --> E4["O(E lg V)"]

    F --> F1["约束图构造"]
    F --> F2["超级源点"]
    F --> F3["Bellman-Ford求解"]

    B --> C
    B --> D
    B --> E
    C --> F

核心概念回顾

松弛操作——全章的核心

RELAX(u, v, w):
    if d[v] > d[u] + w(u, v)
        d[v] = d[u] + w(u, v)
        π[v] = u

所有SSSP算法的本质都是以不同顺序反复执行松弛操作，直到无法再松弛为止。

四种算法对比

比较维度Bellman-FordDAG最短路径DijkstraBFS
适用图一般有向图有向无环图非负权图无权图
负权边✅ 支持✅ 支持❌ 不支持❌ 不支持
负权环可检测不存在不适用不适用
核心策略多轮全局松弛拓扑序+单轮松弛贪心+优先队列逐层扩展
数据结构无特殊要求无特殊要求优先队列队列
时间复杂度
最优实现——斐波那契堆 —
理论基础路径松弛性质路径松弛+拓扑序收敛+贪心BFS最短路径性质

五大基本性质（22.5）

三角不等式（Lemma 22.1）

，对所有 成立。

上界性质（Lemma 22.2）

，对所有 成立（前提：从 可达的顶点不存在负权环）。

收敛性质（Lemma 22.3）

若 是最短路径，且某时刻 ，则此后永远有 。

路径松弛性质（Lemma 22.4）

若 是从 到 的最短路径，按边序松弛，则 。

前驱子图性质（Lemma 22.5）

一旦 ，前驱子图 是以 为根的最短路径树。

跨章关联

与第20章（基本图算法）的关系

第20章概念第22章应用
BFSBFS是无权图上Dijkstra的特例
图的表示邻接表是所有SSSP算法的标准输入
DFS/拓扑排序DAG最短路径算法直接使用拓扑排序
DFS完成时间与Bellman-Ford的松弛顺序有关

与第21章（最小生成树）的关系

MST概念SSSP对应
Prim算法Dijkstra算法（结构几乎相同）
贪心选择性质Dijkstra的贪心选择由收敛性质保证
割性质Dijkstra中 集合定义割

与第6章（堆排序）的关系

与第19章（不相交集合）的关系

  • Bellman-Ford不使用并查集（与Kruskal不同）
  • 但Bellman-Ford的负权环检测与并查集的环检测有概念关联

综合复习题

常见误区

误区1：Bellman-Ford可以找到含负权环的图的最短路径

正确理解：Bellman-Ford可以检测负权环的存在，但不能为从源点可达负权环的顶点找到有定义的最短路径（因为可以无限绕负权环使路径长度趋近于 ）。

误区2：Dijkstra算法总是比Bellman-Ford快

正确理解：Dijkstra在非负权图上确实更快（ vs ），但Dijkstra无法处理负权边。在含负权边的场景下，Bellman-Ford是唯一的选择（除非使用SPFA等优化变体）。

误区3：BFS可以替代Dijkstra

正确理解：BFS只在所有边权相等（通常为1）时等价于Dijkstra。如果边权不同，BFS不能正确求解最短路径问题。

学习要点总结

学习目标掌握程度对应笔记
松弛操作的定义与作用熟练22.1 Bellman-Ford算法
Bellman-Ford伪代码、正确性、复杂度熟练22.1 Bellman-Ford算法
负权环检测原理掌握22.1 Bellman-Ford算法
DAG最短路径的拓扑序方法熟练22.2 有向无环图中的单源最短路径
Dijkstra伪代码、正确性、复杂度熟练22.3 Dijkstra算法
Dijkstra不适用负权边的原因掌握22.3 Dijkstra算法
差分约束系统与约束图的构造掌握22.4 差分约束与最短路径
五大基本性质的陈述与证明思路掌握22.5 最短路径性质的证明
四种算法的选型依据熟练全章

参见Wiki

概念页尚未创建

关系图谱

反向链接