Dijkstra 最短路径 — 一杯咖啡时间想出来的贪心算法

是什么

Dijkstra 算法是一种**给每个城市算出”从起点开车到这里最少要几公里”**的办法。日常类比：你站在北京要去全国 30 个城市，每条路上写着公里数，你想知道到每个城市的最短距离。Dijkstra 告诉你怎么一边走一边记，保证最后每张卡片上写的都是真正的最短。

它的核心是一个贪心策略：每一步都从”还没敲定的城市里挑当前估计最近的那个”，把它的距离敲死，再用它去刷新邻居的估计。这件事 Dijkstra 在 1956 年的咖啡馆里 20 分钟想出来，没带纸笔。

import heapq
def dijkstra(graph, s):
    d = {v: float('inf') for v in graph}; d[s] = 0
    heap = [(0, s)]
    while heap:
        du, u = heapq.heappop(heap)
        if du > d[u]: continue        # 懒惰删除过期项
        for v, w in graph[u]:
            if d[u] + w < d[v]:
                d[v] = d[u] + w
                heapq.heappush(heap, (d[v], v))
    return d

整个算法只用了一个堆和一个数组，14 行 Python 就能跑通——但贪心成立的前提是所有边权都非负。

为什么重要

不理解 Dijkstra 这套思路，下面这些事都没法解释：

为什么 Google Maps / 高德导航在 0.5 秒里能从全国路网算出最短路线
为什么互联网每台路由器都在内部跑一份它（OSPF / IS-IS 协议的骨架）
为什么”贪心算法”在很多教材里第一个例子就是它——它是贪心能给出全局最优的少数典型
为什么”边权非负”这个看似无伤大雅的限制，是整个算法成立的命脉
为什么 1959 年三页纸的备忘到今天依然出现在每一本算法教材的第一章

核心要点

Dijkstra 的算法可以拆成 三个动作：

维护两个集合：已敲定（距离不会再变）和未敲定（估计距离会被刷新）。类比：考完试已经判完分的卷子 vs 还在改的卷子。
每轮挑当前估计最小的未敲定点：这一点的估计距离一定就是真实最短距离——因为剩下未敲定的点估计都更远，再绕过去只会更长（边权非负）。类比：超市排队，最先轮到你的就是真最先。这是整个算法正确性的关键引理。
松弛邻居：用刚敲定的点去看它的每条出边，如果”经它绕过去”比邻居现在的估计更短，就更新。类比：你拿到内部价后告诉朋友，朋友把购物车价格刷新。松弛重复 |E| 次后，所有顶点的估计都收敛到真实最短距离。

三个动作合起来叫贪心松弛 + 优先队列。复杂度由 pop 决定：用数组 O(V²)，用二叉堆 O((V+E) log V)，用斐波那契堆 O(E + V log V)。

实践案例

案例 1：Python 14 行跑通 6 顶点小图

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 3), ('D', 2), ('E', 3)],
    'C': [('B', 1), ('D', 4), ('E', 5)],
    'D': [('E', 1)], 'E': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 3, 'C': 2, 'D': 5, 'E': 6}

逐部分解释：从 A 出发先到 C（2），从 C 用 1 敲到 B（2+1=3 比 4 短），从 B 到 D（3+2=5），最后 D 到 E（5+1=6）。贪心每步都选最小未敲定——这一选择被反证法保证就是真实最短。

案例 2：Internet 路由 OSPF

每台路由器把”我和谁直接相连、链路代价是多少”广播给全网。每台路由器收齐之后独立跑一遍 Dijkstra，得到一张”我到任意子网的下一跳”表，叫转发表。

源 R1 跑 Dijkstra 后得到：
  到 R2 → 下一跳 R2，距离 5
  到 R3 → 下一跳 R2，距离 12
  到 R4 → 下一跳 R5，距离 8

互联网骨干网每隔几十秒就刷新一次。这就是为什么”链路状态协议”快——每个节点拿到全图就能 O((V+E) log V) 算完。

案例 3：导航软件叠 A* 启发式

GPS 导航不能纯 Dijkstra——全国路网上千万节点会爆炸。A* 是 Dijkstra 的”加了直觉”版本：每步还看”目标点的直线距离”，把搜索方向掰向终点。本质：

普通 Dijkstra：pop 时按 d[v]
A*：           pop 时按 d[v] + h(v)
              h(v) = 到目标的直线距离（启发函数）

h(v) 必须不高估真实剩余距离（admissible）才保证最优。Hart-Nilsson-Raphael 在 1968 年给出证明。

踩过的坑

边权出现负数就崩——贪心证明里用到 w ≥ 0，一旦有负边必须改用 Bellman-Ford。最隐蔽的是”看起来都正”但建模时无意取了差值导致负权。
用普通队列代替优先队列——退化成 BFS，加权图给不出正确答案，看起来”差不多”但悄悄错；小图测不出来，大图崩盘。
忘了懒惰删除——同一顶点可能多次入堆，pop 出来要先判 du > d[u] 跳过过期项，否则反复松弛拖慢一倍。
混淆”已访问”和”已入堆”——只有从堆里 pop 并通过过期检查才算敲定，光入过堆不算。这个坑常出现在边数远大于点数的稠密图。

适用 vs 不适用场景

适用：

边权非负的单源最短路径（路网导航、路由协议、依赖最短链路）
顶点和边规模可以装进内存（百万级以下）
同一起点要查很多终点（一次 Dijkstra 全算完）

不适用：

有负边或负环 → 用 Bellman-Ford / SPFA / Johnson
求所有点对之间最短路径 → 用 Floyd-Warshall O(V³)
全国路网毫秒级响应 → 用 contraction hierarchies / A* 加启发式
求最长路径 → 把权值取负还是不行，是 NP-hard

历史小故事（可跳过）

1956 年：Dijkstra 26 岁，在阿姆斯特丹 Mathematisch Centrum 为新机器 ARMAC 准备公开演示样例，需要一个看起来”聪明”的算法。
某个早晨：他和未婚妻在咖啡馆喝咖啡，故意没带纸笔，约 20 分钟在脑子里推完最短路径算法。他后来说”没带纸笔反而帮我抛掉细节”。
1959 年：发表于 Numerische Mathematik 第 1 卷 269–271 页，仅 3 页给出两个算法（最小生成树 + 单源最短路径）。
几乎同时：Bellman 与 Ford 给出含负边的版本，复杂度 O(VE) 但适用场景更宽。
1968 年：Hart-Nilsson-Raphael 提出 A*，将启发式叠到 Dijkstra 之上。
1984 年：Fredman & Tarjan 用斐波那契堆把上界压到 O(E + V log V)，理论最优但工程上很少用。
2000 年代：contraction hierarchies 把欧洲路网的查询压到毫秒级，依然是 Dijkstra 的衍生。

学到什么

贪心 + 单调性 = 全局最优——不是所有问题都行，但满足”边权非负”这种单调性的问题可以；这是贪心算法的护城河
算法设计的力量来自约束——Dijkstra 故意没带纸笔；最强的洞察来自抛弃细节
数据结构选对，复杂度差一个数量级——朴素 O(V²) 到二叉堆 O((V+E) log V)，只是 pop 操作换了实现
理论 → 工程：1959 年的 3 页备忘，60 年后还在你手机的导航里跑；好算法的寿命远超任何编程语言

关联

dijkstra-goto —— 同一作者 1968 年的”Go To Considered Harmful”，工程美学一脉相承
knuth-taocp —— TAOCP 卷 1 与卷 3 给 Dijkstra 算法做了 Knuth 风格的复杂度精分析
kildall-dataflow —— 数据流分析的 worklist 算法本质就是 Dijkstra 的远亲
ssa —— SSA 转换里支配树的算法用到最短路径思想
turing-1936 —— 可计算性的奠基；Dijkstra 给出”多项式时间内可计算”的早期范例
cook-levin —— NP-完全性诞生；最长路径却是 NP-hard，恰好是最短路径的反面
karp-21 —— 21 个 NP-完全问题的清单，解释为什么”长”难”短”易
mccarthy-lisp —— 同年代的奠基论文，与 Dijkstra 这篇并称 1959/1960 计算机科学双子星

反向链接

cook-levin —— Cook-Levin 定理 — NP-完全性的诞生
dijkstra-goto —— Dijkstra 1968 — Go To Statement Considered Harmful
freertos —— FreeRTOS-Kernel — KB 级 RAM 跑得动的可抢占多任务内核
fsrs-spaced-repetition —— FSRS — 让 Anki 知道每张卡什么时候快被你忘掉
kajiya-1986-rendering-equation —— Kajiya 渲染方程 — 把所有渲染算法统一成一个积分方程
karp-21 —— Karp 21 — 21 个 NP-完全问题
kildall-dataflow —— Kildall 数据流框架 — 用一套格论统一所有全局编译优化
knuth-taocp —— Knuth TAOCP — 计算机程序设计艺术
mccarthy-lisp —— McCarthy LISP 1960
ssa —— SSA — 静态单赋值形式
the-os-1968 —— THE 1968 — Dijkstra 用分层 + 信号量造出第一个可证明的 OS
turing-1936 —— Turing 1936 可计算性