跳到主要内容

最短路

本节目标

用距离上界、松弛与已确定集合区分稠密图 Dijkstra、堆优化 Dijkstra 和 Floyd 全源最短路。

最短路要求路径边权之和最小。先问清楚“从哪里到哪里”：单源、单终点或全源；再确认边权条件和图的稠密程度。三种模板共享松弛的含义，但已确定集合、存图和枚举中转点的方式不同。

识别信号​

  • 求固定起点到所有点或某个终点的最小距离，且边权非负：考虑 Dijkstra。
  • 顶点较少、需要任意两点之间多次查询：考虑 Floyd。
  • 图较稠密时，邻接矩阵与线性选点的 O(n²) Dijkstra 足够直接。
  • 图较稀疏时，邻接表配最小堆能避免反复扫描不存在的边。

问题模型与核心不变量​

维护 dist[v]，表示当前已知从起点到 v 的最小代价上界。经过边 u -> v 时用

dist[v] = min(dist[v], dist[u] + weight[u][v])

尝试缩小上界，这一步叫松弛。

Dijkstra 的已确定集合 S 满足：S 中顶点的 dist 已是真实最短距离；其余顶点仍是可被未来松弛改善的上界。每轮选 S 外 dist 最小的 u。若存在一条更短路径到 u，取这条路径上第一个不在 S 的顶点 x，其前驱已在 S，故此前已经松弛过 x。非负边权使路径前缀不长于整条路径，于是 dist[x] < dist[u]，与 u 的最小性矛盾。因此 u 可以安全确定。

Floyd 改为维护 dist[from][to]：在第 mid 轮之后，它只允许使用编号不超过 mid 的中转点。若 from -> mid 与 mid -> to 都可达，就比较是否经由 mid 更短；三重循环的 mid / from / to 顺序正是在维护这个不变量。

通用模板​

单源非负权：
dist[source] = 0，其余为无穷大
不断取当前最小候选，确定它，再松弛它的出边

全源：
dist[i][i] = 0，边取最小重边
for mid / from / to：两段可达时尝试 dist[from][mid] + dist[mid][to]

邻接矩阵版 Dijkstra 每轮线性选点并扫描一整行，适合稠密图；建图时同一对端点的重边必须保留较小权值。最小堆版把 (distance, vertex) 入堆，弹出项若不等于当前 dist[vertex] 就跳过，避免过期候选影响答案。

模板变体​

  • 邻接矩阵 Dijkstra：O(n²)，适合顶点数较小或图稠密的单源题。
  • 邻接表 + 最小堆 Dijkstra：O((n + m) log n)，适合稀疏图和需要到所有点的延迟类题。
  • Floyd：O(n³) 时间、O(n²) 空间，适合较小图的全源查询。

母题序列​

按必学顺序练习：

  1. Dijkstra 求最短路 I（必学）：在线性选点的邻接矩阵中理解已确定集合。
  2. 网络延迟时间（必学）：在邻接表与最小堆中处理过期候选。
  3. Floyd 求最短路（必学）：用中转点阶段不变量求全源最短路。

常见误区​

  • 在含负边的图上套 Dijkstra，破坏“选中后可确定”的前提。
  • 把局部最小边误当作起点到顶点的最小 dist。
  • 重边直接覆盖，丢失先读到的更轻边。
  • 未检查可达性就让无穷大参与相加。
  • 堆优化时不跳过过期距离，造成重复且错误的扩展。
  • Floyd 把循环顺序写成先枚举端点，破坏“允许中转点集合”的阶段含义。

迁移方向​

新题先按“单源还是全源、边权是否非负、图是稠密还是稀疏”选模板。若边数多且顶点不大，矩阵版的结构最清晰；若边稀疏，则把选点与枚举出边替换为堆和邻接表，dist、松弛和非负权前提不变。遇到允许负边或受限边数时，需要切换到相应的其他最短路模型。