最短路径与 Dijkstra 算法

1956 年，荷兰计算机科学家艾兹赫尔·迪克斯特拉（Edsger W. Dijkstra）在阿姆斯特丹数学中心工作，那时没有鼠标、没有编辑器——程序员用铅笔在纸上写，然后把穿孔卡片送进去运行。

他在这年想出了一个算法，能找出加权图中任意两点之间的最短路径。这个算法今天仍然运行在全球每一台路由器上，也在你每次用导航 App 的时候悄悄工作。

迪克斯特拉后来回忆：他花了大约 20 分钟在一家阿姆斯特丹咖啡馆里构想出这个算法——那天他没有带铅笔纸。

破除误解：最短路径不等于"最少边数"#

BFS 可以找到无权图中最少边数的路径。但现实问题通常有权重：

• 路径：不同道路有不同长度
• 网络：不同链路有不同延迟
• 航班：不同路线有不同价格

此时"最短路径"指权重之和最小的路径，而不仅仅是经过节点最少。BFS 无法处理这种情况——权重为 2 的直达路，可能比权重各为 1 的两跳路还要贵。

Dijkstra 算法解决的正是加权图中的单源最短路径问题（Single-Source Shortest Paths）：从给定起点出发，求到图中所有其他节点的最短路径。

前提条件：所有边的权重必须非负。负权边会破坏 Dijkstra 的核心假设（见后文争议部分）。

算法思路：贪心地扩展最近节点#

Dijkstra 的核心是一个贪心策略：

每次从"当前已知距起点最近的未处理节点"出发，更新其邻居的距离。

维护一个距离表 dist[v]，初始化为：起点 $s$ 距离为 0，其余为 $\infty$。

dist = {A: 0, B: inf, C: inf, D: inf, E: inf}
priority_queue = [(0, A)]  # (距离, 节点)
```

每次取出距离最小的节点 $u$，对其每条出边 $(u, v, w)$：

$$\text{如果 } dist[u] + w < dist[v], \text{ 则更新 } dist[v] = dist[u] + w$$

这叫做松弛（Relaxation）操作——"通过 $u$ 到达 $v$ 是否比目前已知的更短？"

实现#

import heapq

def dijkstra(graph, start): # graph[u] = [(weight, v), ...] dist = {node: float('inf') for node in graph} dist[start] = 0 prev = {node: None for node in graph} # 记录路径 pq = [(0, start)] # 优先级队列（最小堆）

while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue # 过时的条目，跳过 for weight, v in graph[u]: new_dist = dist[u] + weight if new_dist < dist[v]: dist[v] = new_dist prev[v] = u heapq.heappush(pq, (new_dist, v))

return dist, prev ```

走一遍：六个节点，看着表格动#

取一张无向加权图，六个节点，七条边：

从 A 出发。每一行是"弹出一个节点，松弛它的所有出边"之后的快照，加粗表示这一步被改进的值，✓ 表示该节点已定案：

第 3 步是整张表的重点。A→D 有一条直达边，权重 5；但走 A→C→F→D 是 $1 + 2 + 1 = 4$，更短。所以 dist[D] 从 5 被改进成 4——绕三条边比走一条边更近。这就是加权图与无权图的根本差别，也是 BFS 在这里必然出错的地方：BFS 会认定 A→D 是最优（只用一跳）。

第 5 步也值得看。弹出 B 时 dist[B] = 6，它去松弛 E：$6 + 2 = 8$，而 dist[E] 已经是 7，所以不更新。松弛失败和松弛成功一样正常——大部分松弛操作什么都不改变。

最终结果：A=0，C=1，F=3，D=4，B=6，E=7。注意弹出的距离序列（0, 1, 3, 4, 6, 7）单调递增——这不是巧合，而是"为什么贪心是正确的"一节要说明的核心性质：非负边权保证了后弹出的节点不可能比先弹出的更近，因此一旦弹出就再无翻案可能。

复杂度#

时间复杂度取决于实现：

实践中，二叉堆实现是最常用的。对稠密图（$E \approx V^2$），朴素版可能更快（常数小）；对稀疏图（$E \ll V^2$），堆版更优。

斐波那契堆是一个值得警惕的例子：它把 decrease-key 摊还到 $O(1)$，从而把总复杂度压到理论最优的 $O(E + V \log V)$——但几乎没有生产系统用它。原因不在算法，在硬件：斐波那契堆的节点是散落在堆上、靠指针互连的树林，每次操作都在做指针追逐，缓存缺失率极高；而二叉堆是一个连续数组，父子下标算术可得，几乎每次访问都命中缓存。渐进更优 + 常数灾难 = 实践更慢，这是算法工程里最经常重演的一课。真实系统若要优化这一步，通常改用 $d$ 叉堆（增大分支因子换取更浅的树、更少的下沉次数）或配对堆，而不是斐波那契堆。

另一条被低估的优化在上面那份代码里已经出现了：if d > dist[u]: continue。这叫惰性删除——不去堆里找旧条目改它，而是任由重复条目堆积，弹出时发现过期就跳过。它让堆里最多有 $E$ 个条目（而非 $V$ 个），换来的是完全不需要实现 decrease-key。绝大多数工程实现都选这条路。

为什么贪心是正确的#

Dijkstra 正确性的关键：若所有边权非负，那么一个节点一旦被弹出优先级队列（被标记为"已处理"），其最短距离就已经确定，不会再被改进。

证明的直觉：已处理节点 $u$ 的距离 $dist[u]$ 是当前最小的。通过其他未处理节点绕路到 $u$ 的任何路径，距离必然 $\geq dist[u]$（因为所有边权 $\geq 0$）。所以不存在更短的路。

这个论证在有负权边时失效——负权边可以让"绕远路"反而变短，破坏了"已处理节点不再更新"的假设。处理负权边需要 Bellman-Ford 算法（$O(VE)$，慢得多）。

现实应用#

互联网路由：OSPF（Open Shortest Path First）协议是互联网内部路由的主要协议之一，其核心就是 Dijkstra 算法。每个路由器维护一张网络拓扑图，用 Dijkstra 计算到所有目的地的最短路径，构建转发表。

游戏地图寻路：策略游戏、RPG 中的单位寻路通常使用 A*，可以理解为"有启发函数的 Dijkstra"。

现场：从"能跑"到"0.76 毫秒跑完西欧"#

导航是 Dijkstra 最大众的应用，也是它最不能直接用的地方。原因很直白：教科书 Dijkstra 是一个从起点向四面八方均匀膨胀的圆。要从慕尼黑算到罗马，它会先把整个巴伐利亚、大半个奥地利和瑞士全部扫一遍——目标在南边，它照样往北探索。这不是实现不好，是算法定义如此：不给它任何关于"目标在哪"的信息，它只能全方位扩张。

工业界的路是层层加码：

第一层：A\*——告诉它目标在哪。 优先队列的键从 dist[v] 换成 dist[v] + h(v)，$h$ 是对"从 $v$ 到终点还剩多远"的估计（比如直线距离）。只要 $h$ 从不高估真实剩余距离（可采纳性，admissibility），A\ 找到的仍是最优路；而搜索区域从圆压成了朝终点方向的椭圆。$h \equiv 0$ 时，A\ 一字不差地退化成 Dijkstra——两者是同一个算法的两个参数取值。

第二层：预处理换查询时间。 真实导航接受"离线算一次、在线查无数次"。Contraction Hierarchies（Geisberger、Sanders、Schultes 与 Delling，2008）的做法是：按"重要性"给节点排序，从最不重要的开始逐个收缩——删掉它，同时在它的邻居之间补上代表原路径的捷径边（shortcut）。反复做完，图就分出了层次，查询时只需从起点和终点各自"往上爬"，在高层相遇。

他们在西欧路网上的实测数字值得记下来：18,029,721 个节点、42,199,587 条有向边，预处理约 15 分钟，每个节点多花 68 字节，随机查询平均 0.76 毫秒。（该文还报告了一个反直觉的结果：加了捷径边之后的数据结构比原图更省空间——因为收缩过程让大量原始边变得可丢弃。）

这一层的意义超出导航：它说明"算法复杂度"和"系统响应时间"是两件事。CH 的查询没有比 Dijkstra 有更好的渐进上界，但它把一次全图 Dijkstra 要面对的四千多万条边的松弛，压缩到只需触碰几百个节点——靠的是把结构提前算好存下来。凡是查询远多于更新的场景（地图、路由表、只读索引），这条思路几乎总能用。

代价与争议#

负权边：一个刚刚被推倒的限制。 Dijkstra 不支持负权边，这在套汇问题、某些差分约束系统里是真实障碍。教科书给的出路是 Bellman-Ford（$O(VE)$）；对全点对则用 Johnson 算法，先用 Bellman-Ford 重新标注权重使其全部非负，再对每个源跑 Dijkstra。

但这条"负权 = 慢一个量级"的常识在 2022 年被打破了。Bernstein、Nanongkai 与 Wulff-Nilsen 在 FOCS 2022 给出一个随机化算法，在整数权重下以 $O(m \log^8 n \log W)$——近线性——时间求解含负权的单源最短路（$m$ 为边数，$W$ 为最大权重绝对值）。这是三十多年来第一次有组合算法突破 Gabow–Tarjan 的 $\tilde{O}(m\sqrt{n}\log W)$ 界。

值得注意的是这条结果目前的性质：它是理论突破，$\log^8 n$ 这个因子意味着在现实规模上常数极大，暂时没有取代 Bellman-Ford 的生产实现。但它改变了这个问题的地位——"负权注定更慢"从一条定律降级为一个待优化的工程问题。

与 BFS、A\*、Bellman-Ford 的统一视角：这四个算法其实是同一件事在不同约束下的样子——都在反复做松弛，区别只在"下一个松弛谁"。

把这张表记住，比单独记四个算法有用得多：选择策略决定了算法名字，也决定了它需要什么前提。

跨域连接#

• 图遍历：BFS、Dijkstra 与带启发的搜索其实是同一套松弛框架，区别只在"下一个处理谁"：先进先出、距离最小、还是距离加估计最小。选择策略同时决定了算法的名字与它需要的前提——启发函数一旦高估剩余距离，最优性立刻失效。
• 外汇：把汇率取对数再取负，一条兑换路径的总代价就成了边权之和，而一个负权环恰好对应一次无风险套汇。于是贪心失效不是技术细节，而是有套汇机会时最短路根本不存在——这也说明为何处理负权必须换一套按轮扫描的方法。
• 最优化：最短路是线性规划的特例，其对偶变量可以读成每个节点的"势"。重新标注权重使其全部非负，本质上就是构造一组可行的对偶势，之后才能重新用贪心。近似与重标注这类技巧的来源，往往在对偶而不在图论。
• 网络流：最小费用流的经典解法每轮都在残量网络上求一次最短路，而残量网络里的反向边天然带负权——负权不是人为构造的病态输入，它是从别的算法里自然长出来的。这也解释了对偶势技术为何最早在流问题中被需要。
• 网络协议：链路状态路由让每台路由器持有全网拓扑、各自独立跑一次最短路生成转发表。真正的难点不在算法而在一致性：只要两台路由器的拓扑视图不同步，就可能出现转发环路。这是分布式系统问题，不是图论问题。

参考文献#

• Dijkstra, E. W. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1, 269–271 (1959).（原始论文，仅 3 页）
• Cormen, T. et al. Introduction to Algorithms (CLRS). 3rd ed., 第 24 章. MIT Press, 2009.
• Geisberger, R., Sanders, P., Schultes, D. & Delling, D. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. WEA 2008, LNCS 5038, 319–333.（西欧路网 1802 万节点、0.76 ms 查询的来源）
• Goldberg, A. & Harrelson, C. Computing the Shortest Path: A\ Search Meets Graph Theory.* SODA 2005.
• Bernstein, A., Nanongkai, D. & Wulff-Nilsen, C. Negative-Weight Single-Source Shortest Paths in Near-Linear Time. FOCS 2022, 600–611. arXiv:2203.03456.
• Moy, J. OSPF Version 2. IETF RFC 2328, 1998.（Dijkstra 在互联网路由中的标准化形态）

延伸阅读#

• Bast, H. et al. Route Planning in Transportation Networks. In: Algorithm Engineering, LNCS 9220, 2016.（路径规划加速技术的系统性综述：CH、Hub Labeling、Transit Node Routing）
• Frana, P. L. An Interview with Edsger W. Dijkstra. Communications of the ACM 53(8), 41–47 (2010)；原始口述史访谈 2001 年由 Charles Babbage Institute 录制。（咖啡馆里那 20 分钟由他本人讲述）