第5章 急行军竞赛：最短路径战役

第 5 章 · 急行军竞赛：最短路径战役

章节摘要：地图上的每条道路如今都有了里程——通行要付出代价，远征队的问题从"能不能到"升级为"怎么到最省"。本章是全册的第一场大型战役：Dijkstra 用贪心策略在非负权地形上闪电推进；Bellman-Ford 牺牲速度换取稳健，独门解负权边并顺手侦测负环；Floyd-Warshall 换一个视角，在邻接矩阵上三重循环算出所有顶点对之间的最短路。三支部队各擅胜场，也各有禁区。学完本章，你面对任何"求最短"的问题，应当能先问对三个问题：权有没有负的？要一个源还是全部源？稀疏还是稠密？

本章知识点清单

下列考核点覆盖本章全部内容：

1. 手写 Dijkstra 的朴素版与堆优化版，说明非负权在正确性证明中的两处关键出场。
2. 解释"松弛"操作的涵义，并推导 Dijkstra 的时间复杂度在两种实现下的差异。
3. 手写 Bellman-Ford，证明"边数至多为 k 的最短路"随迭代轮数单调逼近的论证。
4. 判定负环并输出环上顶点；说明负环存在时"最短路"为何失去意义。
5. 手写 Floyd-Warshall，解释中转顶点放在最外层循环的原因。
6. 给出三种算法的选型对比表：单源对全源、非负对可负、稀疏对稠密。

核心概念速览

金句：最短路算法的分歧不在"怎么走"，而在"敢不敢相信眼前这条最近的边"——贪心的胆量由权非负担保。

子章节导航

第 1 节"Dijkstra 算法：非负地形上的贪心行军"从行军竞赛的场景切入，完整推演贪心策略为何在非负权下无懈可击，给出朴素与堆优化两种实现，并交代它作为导航系统心脏的工程变体。

第 2 节"Bellman-Ford 与负权地形：反复松弛的稳健打法"处理贪心的禁区：负权边。反复松弛的稳健打法以更多轮次为代价换正确性，还附赠负环侦测——汇率套利检测正用它。

第 3 节"Floyd-Warshall：全源最短路的方阵演算"把镜头拉远：不求单源，一次算清所有顶点对。矩阵视角与第 2 章的邻接矩阵呼应，三重循环的次序里藏着动态规划的骨架。

三支部队怎么分工

一句话论点：问对问题再选兵器——权的符号定生死，源的数量定格局，图的疏密定实现。

  求最短路之前，先过三道关卡
  ┌─ 关卡一：有负权边？ ─── 有 → Bellman-Ford（再查负环）
  │                        无 → Dijkstra 或 Floyd
  ├─ 关卡二：单源还是全源？ ─ 单源 → Dijkstra（堆优化）
  │                        全源 → Floyd（或逐点跑单源）
  └─ 关卡三：疏还是密？ ──── 稀疏 → 邻接表+堆
                           稠密 → 朴素 Dijkstra / Floyd
​

前置知识与后续延伸

前置：第 2 章的邻接矩阵与邻接表（两种存储在这里直接决定实现路线）、第 3 章广度优先的"层次即距离"（Dijkstra 是它的加权推广）、优先队列的基本用法。

后续延伸：最短路是无数系统的地基——第 10 章的路由与导航一节将检验它的工程形态；稀疏图上的全源问题可以逐顶点跑单源替代 Floyd；Floyd 的三重循环是第 6 章动态规划式思维的预热。此外，"松弛"这一操作将贯穿全册，网络流一节还会再见到它的变体。