学习指南：图论基础与最短路径算法（进阶）
适用人群：大学生、自学者、职场新人
目标：系统掌握图论基础与最短路径算法的核心原理、正确性、实现细节与应用。
先修要求：数据结构（数组、链表、堆）、算法复杂度、基本数学逻辑与证明方法、编程基础（任一主流语言）
学习目标
- 准确理解图的基本概念、建模方式与常用表示（邻接表/邻接矩阵）
- 根据图的特性（有向/无向、权重、负权、稀疏/稠密、规模）选择合适的最短路径算法
- 掌握 BFS（无权最短路径）、Dijkstra（非负权单源）、Bellman-Ford（含负权单源）、Floyd–Warshall（全点对）的原理、复杂度、正确性不变式与实现
- 能进行路径重建与负环检测，处理常见边界情况
- 将最短路径算法应用于真实场景（导航、路由、调度），并制定工程化选择策略
模块一：核心概念与定义
核心概念
- 图 Graph：由顶点集合 V 和边集合 E 构成。边可有方向（有向图）或无方向（无向图），可带权重 w(u, v)。
- 路径 Path：顶点序列 v0 → v1 → … → vk，其中相邻顶点之间存在边。简单路径不重复顶点。
- 距离/路径长度：路径上边权之和；无权图中可视作边数。
- 连通性：无向图的连通；有向图的强连通与弱连通。
- 负权与负环：边权为负；若存在总权重为负的环，则最短路径问题在该源到可达负环的情况不再有下界（趋于负无穷）。
- 图表示：
- 邻接表：适合稀疏图，空间 O(V + E)
- 邻接矩阵：适合稠密图或需要 O(1) 边存在性查询，空间 O(V^2)
关键原理
- 松弛（Relaxation）：若 dist[v] > dist[u] + w(u, v)，则更新 dist[v] 与前驱 pred[v] = u。
- 最优性原理（Optimal Substructure）：最短路径的任一前缀也是对应子问题的最短路径。
- 贪心安全性（Dijkstra）：在非负权图中，具有当前最小估计距离的顶点，其估计距离一旦取出（finalize）即为最短距离。
模块二：问题分类与算法选择
问题分类
- 单源最短路径（SSSP）：从单一源 s 到所有顶点的最短距离
- 单源单目标（S–T）：从 s 到特定 t 的最短路径
- 全点对最短路径（APSP）：任意两顶点之间的最短距离
条件驱动的算法选择
- 无权图（或所有边权相等）：BFS
- 有权且非负：Dijkstra（优先队列/堆）
- 含负权但无负环：Bellman-Ford（单源）；Floyd–Warshall 或 Johnson（全点对）
- 需要全点对：
- 顶点数较小（≤ 数百）：Floyd–Warshall
- 大图稀疏：Johnson（先用 Bellman-Ford 重新加权，再多次 Dijkstra）
- 仅需 s→t 且图很大：Dijkstra + 可选 A*（若有可行启发式）
模块三：算法详解
A. 无权最短路径：BFS
- 适用：无权图或权重均为 1
- 原理：按层扩展，先到达即最短步数
- 时间复杂度：O(V + E)
- 关键不变式：队列中顶点的层次非递减；首次出队即确定最短距离
示例图（无向，无权）
- 顶点：A, B, C, D, E
- 边：A–B, A–C, B–D, C–D, D–E
- 从 A 出发到 E 的最短路径：A → B → D → E 或 A → C → D → E（长度 3）
伪代码
BFS(G, s):
for v in V: dist[v] = ∞; pred[v] = NIL
dist[s] = 0
Q = queue()
Q.push(s)
while Q not empty:
u = Q.pop()
for each v in adj[u]:
if dist[v] == ∞:
dist[v] = dist[u] + 1
pred[v] = u
Q.push(v)
练习
- 在给定无权图中用 BFS 找出从指定源到所有顶点的最短距离与路径（重建路径见模块四）。
- 证明：BFS 第一次发现顶点 v 时得到的是从源到 v 的最短路径长度。
B. Dijkstra 算法（非负权单源）
- 适用：边权非负的有向/无向图
- 原理：贪心选择当前最小估计距离顶点进行“定型”，并对其邻居做松弛；优先队列维护候选
- 时间复杂度：
- 使用二叉堆：O(E log V)
- 使用斐波那契堆（理论）：O(E + V log V)
- 正确性要点：
- 贪心安全性：非负权确保“先到更短”，不会被后续边权修正反驳
- 不变式：已定型顶点的 dist 值为全局最短距离
伪代码
Dijkstra(G, s):
for v in V: dist[v] = ∞; pred[v] = NIL
dist[s] = 0
PQ = min-priority-queue()
PQ.insert(s, 0)
while PQ not empty:
(u, du) = PQ.extract-min()
if du > dist[u]: continue // 懒惰删除
for each (u, v, w) in edges from u:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
pred[v] = u
PQ.insert_or_decrease_key(v, dist[v])
示例（有向，非负权）
- 顶点：S, A, B, C, T
- 边与权：S→A(2), S→B(5), A→B(2), A→C(4), B→C(1), C→T(3)
- 运行轨迹（简略）：dist[S]=0；取 S → 松弛 A=2, B=5；取 A → 松弛 B=4, C=6；取 B → 松弛 C=5；取 C → 松弛 T=8；最终 dist[T]=8，路径 S→A→B→C→T
常见坑
- 负权边存在则不适用（哪怕单条负边）
- 大图中使用邻接矩阵会导致 O(V^2)；稀疏图应使用邻接表 + 堆
- 需进行路径重建时维护 pred
练习
- 对比使用数组线性扫描的 Dijkstra（O(V^2)）与堆优化版本在稀疏图上的性能差异。
- 证明：当所有 w ≥ 0 时，Dijkstra 的贪心选择是安全的。
C. Bellman–Ford（含负权，无负环的单源）
- 适用：允许负权；需检测负环
- 原理：对所有边进行 V−1 轮松弛，确保任意最短路径最多包含 V−1 条边；额外一轮检测负环
- 时间复杂度：O(VE)
- 正确性要点：动态规划式迭代，每轮扩展允许路径长度增加一条边；若第 V 轮仍能松弛，存在可达负环
伪代码
BellmanFord(G, s):
for v in V: dist[v] = ∞; pred[v] = NIL
dist[s] = 0
for i in 1..V-1:
for each edge (u, v, w) in E:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pred[v] = u
// 负环检测
for each edge (u, v, w) in E:
if dist[u] + w < dist[v]:
report "存在可达负环"
示例
- 顶点：S, A, B
- 边与权：S→A(1), A→B(-2), S→B(4)
- 结果：dist[A]=1，第一轮松弛后 dist[B]= -1（S→A→B），第二轮不再变化，无负环
注意
- SPFA 是 Bellman–Ford 的队列优化，但有可能退化到非常慢（最坏指数级）。在工程中谨慎使用并加以保护（拓扑序、随机化、边界检查）。
练习
- 构造一个带负权但无负环的小图，手算 Bellman–Ford 迭代过程。
- 给出负环检测的例子并解释为何最短路径不存在。
D. Floyd–Warshall（全点对最短路径）
- 适用：需要 AP-SP；适用于顶点数较小或图稠密；允许负权但无负环
- 原理：三重循环的动态规划；逐步允许中间顶点集合扩展
- 时间复杂度：O(V^3)，空间 O(V^2)
- 正确性要点：k 阶段引入顶点 k 作为中间点，dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
伪代码
FloydWarshall(G):
for i in V:
for j in V:
if i == j: dist[i][j] = 0
else if edge(i, j): dist[i][j] = w(i, j)
else dist[i][j] = ∞
next[i][j] = j if edge(i, j) else NIL
for k in V:
for i in V:
for j in V:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next[i][j] = next[i][k]
// 负环检测：若 dist[i][i] < 0，则 i 在负环可达域内
练习
- 对一个 4×4 小图运行 Floyd–Warshall，绘制中间矩阵变化。
- 扩展：使用 next 表重建任意 i→j 的路径。
E. 扩展：A* 搜索（单源单目标，启发式）
- 适用：有空间几何信息的路网等；需要 s→t；边权非负
- 原理：f(n) = g(n) + h(n)，其中 h(n) 是对目标距离的可采纳启发式（不超过真实最短）
- 正确性要点：启发式需满足可采纳（admissible）与一致性（consistent/三角不等式），保证最优性与加速
- 练习：在网格图上采用曼哈顿距离作为启发式，对比 Dijkstra 的扩展节点数量
模块四：路径重建与数据结构要点
路径重建
- 使用前驱数组 pred[v]；从目标 t 回溯到源 s，再反转得到路径
- BFS/Dijkstra/Bellman–Ford 均可维护 pred
图表示与数据结构
- 稀疏图（E ≈ O(V)）：邻接表 + 最小堆（Dijkstra）
- 稠密图（E ≈ O(V^2)）：邻接矩阵；Floyd–Warshall更适配
- 队列/堆选择：
- 二叉堆：工程常用，易实现
- 斐波那契堆：理论更优，但实现复杂；多数场景二叉堆足够
模块五：综合应用案例
- 城市导航：路网非负权（距离/时间），选择 Dijkstra；若需要频繁查询多对最短路径，可使用预处理（如多源 Dijkstra、分层图或收缩层次 CH）。
- 物流配送：存在时窗与转运（可能需要时间依赖权重）；可将时间展开为层图，边权非负仍可用 Dijkstra；全局分析用 Floyd–Warshall（规模小）或 Johnson。
- 网络路由：链路费用可能为负（策略积分或延迟补偿），需 Bellman–Ford 以支持负权并检测负环；BGP/Distance Vector 协议设计与负环相似问题。
- 项目调度（PERT）：用有向无环图（DAG）时，可用拓扑序上的一次松弛求最短/最长路径（无环特化）。
模块六：练习题（含要点提示）
- 概念与判断
- 给定有向加权图与边权集合，判断适用的最短路径算法并说明理由。
提示：检查负权、有无环、规模与稀疏性、是否需要全点对。
- 手算与轨迹
- 对下图（有向，非负权）手动运行 Dijkstra，给出 dist 表与 pred 表的变化，重建 s→t 路径。
提示：每次 extract-min 后对出边松弛，记录更新。
- 证明与不变式
- 证明 BFS 的层次等价最短步数。
- 证明 Dijkstra 的贪心安全性：若所有 w ≥ 0，则取出最小 dist 的顶点，其 dist 为真实最短。
提示：反证法与三角不等式。
- 负环案例
- 构造一个包含负环的图，运行 Bellman–Ford 展示第 V 轮仍可松弛并定位负环。
提示：传递松弛链条可无限降低 dist。
- 全点对路径重建
- 对 5 个顶点的小图运行 Floyd–Warshall，给出 dist 与 next 表，并重建 3→5 的路径。
提示：沿 next[i][j] 前进直到 j。
- 工程实现
- 使用邻接表 + 堆实现 Dijkstra，支持路径重建与不可达判定（输出“无路径”）。
- 将输入规模从 1e3→1e6 顶点进行压力测试，记录时间与内存，讨论瓶颈与优化点。
提示：I/O、缓存局部性、堆操作数量、图存储格式。
- 算法选择设计题
- 为“地铁换乘最少+路程最短”联合目标设计方案：先以无权边（换乘计数）最短作为主目标，再在同层次内用权重（路程）优化。
提示：分层或词典序优化：先 BFS（换乘），再对候选子图运行 Dijkstra（路程）。
模块七：记忆辅助工具
决策树（选算法）
- 无权/权重相同 → BFS
- 有权非负 → Dijkstra（单源）；Johnson/重复 Dijkstra（全点对）
- 有负权无负环 → Bellman–Ford（单源）；Floyd–Warshall/Johnson（全点对）
- 规模小且需全点对 → Floyd–Warshall
- 仅 s→t 且有启发式 → A*
核心检查清单（WENND）
- W: Weights 权重是否非负？
- E: Edges 表示稀疏/稠密？
- N: Negative cycle 可能存在？
- N: Need APSP 是否需要全点对？
- D: Data structure 数据结构是否匹配（邻接表/堆/矩阵）？
不变式快记
- BFS：首次发现即最短层数。
- Dijkstra：已定型顶点的 dist 不再变化且为真值（非负权）。
- Bellman–Ford：第 i 轮后，所有不超过 i 条边的最短路径均已到位；第 V 轮可检测负环。
- Floyd–Warshall：允许的中间点集合逐步扩大，dp 递推。
常见错误与排查
- 误用 Dijkstra 于负权图 → 改用 Bellman–Ford/Johnson。
- 忽略路径重建 → 记得维护 pred 或 next。
- 邻接矩阵用于稀疏大图 → 空间与时间双重低效。
- 未处理不可达顶点 → dist 保持 ∞，输出时特别判定。
- 忽略负环 → 必须检测并明确报告“最短路径不存在”。
小口诀
- “无权层层 BFS，非负贪心 Dij；负权逐轮 Bell，点对三层 Floyd。”
- “负权慎用贪心，负环必做检测。”
模块八：综合示例（从建模到求解）
问题：给定城市路网，边表示道路，权重为通行时间（非负），需要从仓库 S 到所有商店的最短送达时间；同时评估是否要全点对。
- 建模：有向加权图（考虑单行线）。
- 选择：单源多目标 → Dijkstra；若需要任意两店间时间 → 视规模用 Johnson 或 Floyd–Warshall。
- 实现要点：邻接表存储；二叉堆；维护 pred 重建具体路线；对不可达点输出“不可达”。
- 扩展：高峰期不同时间段权重变化 → 时间依赖图；可分时段运行或建立时间层图。
参考与延伸
- CLRS《算法导论》：最短路径（第 24 章）
- Sedgewick & Wayne《Algorithms》：图与最短路径
- 竞争编程资料：cp-algorithms, emaxx
- Johnson 算法（APSP 稀疏图）与 CH/ALT（路网加速）
- A* 启发式设计与一致性证明
总结与实践建议
- 以“图特性驱动算法选择”为原则：无权 → BFS；非负权 → Dijkstra；负权 → Bellman–Ford；全点对（小规模）→ Floyd–Warshall。
- 工程实现中优先选择邻接表 + 堆；为路径重建维护前驱；注意不可达与负环的显式处理。
- 多做手算与实现练习，验证不变式与边界情况；将算法应用于真实需求，逐步形成决策与优化习惯。
