最短路径：Dijkstra、Bellman-Ford 与 Floyd

04-图与网络核心预计 25 分钟最短路DijkstraBellman-FordFloyd

学习状态：

一句话定义

最短路径问题在带权图中求权值和最小的路径：Dijkstra 用贪心 + 优先队列解非负权单源问题（O(E log V)）；Bellman-Ford 逐轮松弛容忍负权并检测负环（O(VE)）；Floyd-Warshall 用动态规划求全源最短路（O(V³)）。

为什么重要

「从 A 到 B 的最小代价」是地图导航、网络路由、任务依赖、汇率换算的共同抽象。三个算法分别示范了贪心、迭代松弛、动态规划三种设计范式在同一线索（松弛）上的变奏——学透它们等于同时复习 kp-025/kp-026 的思想；「为什么 Dijkstra 不能有负权」更是检验是否真懂贪心正确性的试金石。

前置知识

kp-016（图的表示与遍历）；kp-014（堆）。

核心概念

松弛（Relaxation）：若 dist[u] + w(u,v) < dist[v] 则更新——所有最短路算法共享的原子操作。
Dijkstra：维护已确定集 S，每次从优先队列取 dist 最小的未定顶点 u（其 dist 必为最终值），松弛其邻居；要求所有边权非负。
堆优化复杂度：O((V+E) log V)；朴素数组版 O(V²)——稠密图反而朴素更快。
Bellman-Ford：对所有边松弛 V−1 轮；再跑第 V 轮若仍可松弛则存在负环。
Floyd-Warshall：dp[k][i][j] = 允许中转点集 {1..k} 的最短路，三维滚动到二维；顺带求传递闭包。
不可达：用 +∞ 表示，注意加法溢出要用「先判可达再加」。

原理与机制

三个算法共享同一原子操作「松弛」：发现经中转点更近就更新距离。Dijkstra 的机制是「按距离从小到大一锤定音」：非负权保证先取出的点不可能再被绕近（反证骨架见公式节），用优先队列维护候选即可；Bellman-Ford 放弃贪心、按轮次反复松弛 V−1 轮，让「至多 k 条边」的最短路逐轮收敛；Floyd 用 DP 把「允许中转点集」逐个扩大，阶段语义藏在最外层的 k 上。

直观类比

Dijkstra 像水位上涨：水从源点漫开，每次淹没「当前海拔最低」的格子——海拔（距离）只会被更早淹掉（非负权保证）；一旦有「负权下坡」，水可能绕回来把已淹没格子的海拔改得更低，贪心即失效，这就是它拒绝负权的本质。Bellman-Ford 则是「重复全员核对 V−1 遍地图」，笨但可靠，还能发现「绕一圈越走越近」的负环。

公式或模型

Dijkstra 贪心不变量：u 入选时 dist[u] = δ(s,u)。证明骨架：反设存在更短路径 P，P 上第一个不在 S 的顶点 y 满足 dist[y] ≤ dist[u]（前缀非负权性质），与「u 是当前最小」矛盾。
Bellman-Ford 正确性：最短路至多 V−1 条边，按任意顺序松弛 V−1 轮后所有 dist 收敛到 δ。
Floyd 转移：dp[k][i][j] = min(dp[k−1][i][j], dp[k−1][i][k] + dp[k−1][k][j])；空间可滚动为 dp[i][j]，k 必须放最外层。
三算法对比表：

算法	场景	复杂度	负权	负环检测
Dijkstra+堆	单源、非负权	O((V+E) log V)	✗	✗
Bellman-Ford	单源、可负权	O(VE)	✓	✓
Floyd	全源、小图	O(V³)	✓（无负环）	可判

图示

Dijkstra 过程（源 A）:   A ─1→ B ─1→ C
  取 A: dist=[0,∞,∞]⇒[0,1,∞]        A ─4→ C
  取 B(1): 松弛 C: min(4, 1+1)=2
  取 C(2): 结束。贪心序：A(0) → B(1) → C(2)

负权反例（Dijkstra 失效）:  A ─1→ B ; A ─4→ C ; C ─3→ B
  A 取出后 B 先按 1 定死，但真实最短是 A→C→B = 4+3=7？ 注意若边为
  C ─(−3)→ B，则 B 真实为 1，而 Dijkstra 已按 1 定死——绕行可能更优，
  贪心「一锤定音」的前提被破坏。

实例或案例

地图导航：分层图 + Dijkstra/A*；OSPF 路由协议内嵌 Dijkstra 思想。
汇率套利：取 −log(汇率) 转成非负权最短路，出现负环即存在套利圈——Bellman-Ford 的经典应用。
游戏寻路、电路布线的简化模型：网格图 Dijkstra。

常见误区

图中有负权边仍用 Dijkstra：结果可能错且无报错，必须先扫一遍边权。
稠密图硬上堆版：E≈V² 时 (V+E)logV ≈ V²logV，反而输给朴素 O(V²)。
Bellman-Ford 只跑 V−1 轮就报答案：第 V 轮的「仍可松弛」检查才是负环判定，漏掉即失去检测能力。
Floyd 忘记 k 放最外层或用一维滚写错方向：dp[k][i][j] 的语义依赖「不含 k」的上一轮。

自测题

手推下图 Dijkstra：V={S,A,B}，边 S→A=1，S→B=5，A→B=2。

答案要点：取 S(0) 松弛 A=1,B=5；取 A(1) 松弛 B=3；取 B(3)。dist: A=1, B=3。

构造一个 Dijkstra 给出错误答案的负权图。

答案要点：S→A=1，S→B=2，B→A=−2：Dijkstra 先定 A=1，实际 A 可经 B 达 0。

为什么 Bellman-Ford 松弛 V−1 轮就够？

答案要点：无负环时最短路至多 V−1 条边；第 k 轮结束后所有「至多 k 条边」的最短路已正确，归纳覆盖全部。

与其他知识点的关系

kp-014 堆是 Dijkstra 的加速器；kp-025 的贪心论证直接复用本节的反证骨架；kp-026 的 DP 与 Floyd 同构（状态=中转点集合）；kp-018 的 MST 与最短路共享「局部贪心」气质但目标不同。

延伸阅读

Dijkstra 1959 原文；《算法导论》第 22 章（22.2–22.4、24.1–24.4 依版本目录为准）。

前置知识点

图的表示与 BFS/DFS 遍历核心