2.1 Dijkstra算法：贪心求单源最短路径
2.1 Dijkstra 算法：贪心求单源最短路径
本节摘要：Dijkstra 算法求解"边权非负"的图上从单一源点到其余各点的最短路径，核心是贪心策略——每轮取出当前距离最小的未确定顶点，认定其距离已经最优，再用它去松弛邻居。朴素实现时间复杂度为点数平方，用优先队列（二叉堆）优化后降为边数乘以 log 点数。它是地图导航、网络路由的算法基石，但不接受负权边。
先说结论
阅读完本节，你应当能够：
- 解释松弛操作的语义，写出一条松弛语句；
- 手工模拟 Dijkstra 在小图上的完整执行过程；
- 说明贪心正确性为什么依赖"边权非负"这一前提；
- 写出朴素版与堆优化版两份实现，并分析各自复杂度；
- 说出记录路径前驱、处理重边与不连通顶点的工程细节。
一、问题与直觉：BFS 哪里不够用了
1.3 节的结论是：无权图上 BFS 就是最短路径算法。现在给每条路标上里程——3 公里的双车道乡道和 300 公里的高速，BFS 眼里都是"一步"。它按"边数最少"分层，而我们要的是"总代价最小"。一旦边有了权重，"先被波纹触及的点"不再保证更便宜：绕两条廉价小路可能比直走一条昂贵干道划算。
Dijkstra 的思路是把 BFS 的"逐层扩展"改成"按累计代价扩展"：维护每个点到源点的当前最短估计距离，每轮从尚未确定的点里挑估计距离最小的那个，断定它的距离已经定型，然后借它更新邻居。挑"当前最小"正是优先队列的拿手好戏——这就是 BFS 的队列换成堆的由来。
原始文集把 Dijkstra 称为"贪婪的探索者"，这个比喻抓住了要害：它每一步都吃掉离自己最近的果实，并且从不反悔。不反悔的底气来自非负权——下面细说。
二、核心原理：松弛与贪心不变量
松弛（relaxation） 是一切最短路算法的原子动作：考察边从 u 到 v、权重 w，若从源点经 u 到 v 比当前记录的到 v 的距离更短，就更新：
if dist[u] + w < dist[v]: dist[v] = dist[u] + w prev[v] = u # 记录前驱，便于回溯路径
直觉是"发现一条更便宜的路，就把账本改掉"。所有最短路算法的区别只在以什么顺序挑边来松弛。
贪心为什么对（非负权前提）：设某轮被选中的点是 u，其当前估计距离为 d。反证——假如 u 的真实最短距离小于 d，那么最短路必然先经过另一个未确定点 x 再到 u；但 d 是所有未确定点中最小的估计，而边权非负保证了从 x 继续走只会更远或不变，矛盾。所以 u 的距离就此定型。
负权为何击穿它：一旦存在负边，"从 x 继续走只会更远"不再成立——一条负边完全可能让后确定的点反过来缩短先确定的点。Dijkstra "定型后不再修改"的承诺破产。这正是 2.2 节 Bellman-Ford 存在的理由。
执行过程（原始文集的例图：边 A 到 B 权 2、A 到 C 权 4、B 到 D 权 7、B 到 E 权 1、C 到 E 权 3、D 到 F 权 2、E 到 F 权 5）：
初始：dist = {A:0, B:∞, C:∞, D:∞, E:∞, F:∞} 第1轮 取A：松弛 B→2，C→4 第2轮 取B：松弛 D→2+7=9，E→2+1=3 第3轮 取E：松弛 F→3+5=8（C 经 E 无改进） 第4轮 取C：无改进（E 已定型且 4+3 不小于 3） 第5轮 取D：松弛 F→9+2=11，不小于 8，保持 8 第6轮 取F：结束 结果：A=0, B=2, C=4, D=9, E=3, F=8
注意第 4 轮 C 的命运：虽然 C 比 E 后定型，但它经 E 已经没有更好的路——贪心的"跳过"与"覆盖"两种结局都在这个例子里出现了。
三、实现与工程细节
堆优化版（生产环境的标准形态）：
import heapq def dijkstra(graph, start): dist = {node: float('inf') for node in graph} dist[start] = 0 pq = [(0, start)] # 元组为 距离 与 顶点 while pq: d, u = heapq.heappop(pq) if d > dist[u]: # 过期的堆条目，跳过 continue for v, w in graph[u]: nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(pq, (nd, v)) return dist
几个实现层面的关键点：
- 懒删除：小根堆不支持降键值，做法是往堆里塞新条目、弹出时若发现距离已过期就跳过。堆里同一顶点可能有多份记录，但每份至多对应一次有效松弛，复杂度仍是边数乘以 log 边数。
- 路径还原：配一个 prev 数组，松弛成功时记录前驱；到达终点后沿 prev 一路回溯再反转，即得完整路径。
- 不连通顶点：终值仍是无穷大，业务层要把它翻译成"不可达"，而不是参与数值比较。
- 重边与自环：邻接表允许重复边，松弛天然取最优，自环则永远不构成改进，都无需特判。
朴素版与堆优化版对比（原始文集的实验设置）
| 版本 | 数据结构 | 时间复杂度 | 适用形态 |
|---|---|---|---|
| 朴素 Dijkstra | 数组线性扫最小 | 点数平方 | 稠密图（边数接近平方级时堆反而无优势） |
| 二叉堆版 | 优先队列 | 边数乘以 log 点数 | 稀疏图，绝大多数真实路网 |
| 斐波那契堆版 | 支持降键的堆 | 边数加 点数乘以 log 点数 | 理论更优、常数大，工程少用 |
原始文集对斐波那契堆的评价值得抄录：它能把复杂度进一步压到"边数加顶点数 log 顶点数"，但实现复杂、常数因子大，实际跑起来往往不如二叉堆——理论优雅与工程实用在这里明显分家。优先队列本身的实现细节，第 5 章会专门展开。
⚠️ 常见坑：拿 Dijkstra 跑带负权的图。它不报错、不抛异常，只会安静地给出错误答案——这是最难排查的一类 bug。上线前先确认权重语义：费用、折扣、收益都可能产生负值。
💡 关键直觉：Dijkstra 的世界是一个"只会变贵不会变便宜"的世界（边权非负），所以"当前最近的未确定点"必然已经最优。把负权想象成"倒贴钱的路段"，一旦存在，走得越远反而越省，贪心的地基就塌了。
四、深入一层：不变量与手算纪律
Dijkstra 的循环不变量值得单独抄进笔记：任何时刻，已定型点的距离都是最终最短距离，未定型点的距离是"仅经已定型点中转"的最短距离。整个算法就是不断把"未定型中最小的那个"升级为定型，并借此扩大"可中转集合"。用这个视角重看手算表格，每一轮数字的含义都变得确定——不是"猜测"，而是"限定路径集合下的精确最优"。排错时同样用它：抽一轮中间状态，手工验证"未定型点的距离是否恰好等于只经过定型点的最短路"，不符则松弛代码有漏。
手算纪律也值得固化成三步：每轮先圈出"未定型中距离最小者"；划掉它进入定型的动作；只更新它的直接邻居。初学者最常见的错是"顺手更新了非邻居"或"跳过了已经更小的值"——前者多算（结果往往仍对但过程错），后者直接出错。
常见疑问解答
为什么我的 Dijkstra 在有零权边的图上也对了？该继续用吗？
零权边不破坏正确性——证明只需要"边权非负"，零完全合法。真正的红线是负数。所以"图里全是零和正数"可以放心用；一旦权重可能为负（哪怕是理论上），就要换 2.2 节的算法或在入口做校验。
堆里存"顶点"还是存"边"？两种写法有区别吗？
本节的实现存的是"（距离， 顶点）"条目，Prim 一节存的是"（权重， 内点， 外点）"边条目——本质都是存"键值加定位信息"。Dijkstra 里距离本身就是键，顶点定位即可；若还需要输出路径，配合 prev 数组即可，不必把整条路径塞进堆（那会让堆操作代价与路径长度挂钩）。
到达某个特定终点就要结果，能提前停吗？
能。弹出目标顶点时即可返回——它此刻已定型，距离即最终答案。这个小优化在"点对点导航"场景能把平均耗时砍掉一半左右，代价只是循环里加一个判断。
相同距离的顶点谁先定型有讲究吗？
结果层面无讲究（距离相同则答案相同）；性能层面，处理顺序影响堆中过期条目的数量，但仍是同数量级。真正要讲究的是堆条目的比较规则——键相同时必须再比较第二字段（顶点编号），否则某些语言的堆实现会在比较上抛错或行为不定。
动手实验：验证与压测一个正确实现
拿到一份 Dijkstra 实现，先做正确性三连：小图手算对答案；构造带零权边的图（结果应正确）；构造含负权边的图（结果应与 Bellman-Ford 不一致——这正是"负权必翻车"的活证据）。然后做规模压测：生成十万顶点、五十万边的随机稀疏图，分别跑朴素版与堆版。多数语言里两者的差距会在一到两个数量级之间；再把图调稠密（边数拉到两千万），观察差距收窄甚至反转——亲手复现 5.2 节预告的"稠密反转"，比读十遍结论更牢。
工程封装清单
把 Dijkstra 封装成可复用模块时，建议保留这些接口细节：入口校验权重非负（发现负值立即报错而非静默算错）；返回"距离加前驱"两份数组（前驱可还原路径）；支持"到指定终点提前终止"的开关；不可达顶点用语言的原生空值表达而非无穷大数字；距离类型选足够的整数宽度防溢出。这五条清单来自真实的线上教训，每一条都能省一次深夜报警。
Dijkstra 能处理"边权随时间变化"的图吗？
标准版不能——它假设权重在整个计算期间不变。动态权重的两条工程出路：定期重算（权重更新频率低时最简单）；或用时效化的变体（把时间维度并入状态，顶点扩展为"某时刻在某点"，本质是把图改造成时空图再跑静态算法）。导航系统的实时路况就落在"定期重算加增量修正"的框架里。
最后补一条工程观察：距离相同时的处理顺序虽然不影响正确性，却影响"等长路径中输出哪一条"；对用户可见的路线建议，常在比较规则里加入"少转弯""主干道优先"等次级偏好，让相同距离下的输出更符合人的直觉。
重点提炼
- 问题定位：Dijkstra 解决非负权图的单源最短路径，是 BFS 的加权升级（队列换优先队列）。
- 两大动作：取当前最小估计距离的点定型；用它松弛所有出边。
- 正确性前提：边权非负；出现负边时贪心结论可被推翻，需改用 2.2 节的算法。
- 复杂度：朴素版点数平方，堆优化版边数乘以 log 点数；稠密图反而朴素版不亏。
- 懒删除：堆中过期条目靠弹出时校验跳过，不需要真正的降键操作。
- 路径还原：松弛时记录前驱，终点回溯即得路径。
- 工程守则：不连通点保持无穷大；权重语义里可能有负值时，换 Bellman-Ford。
负权边出现时该怎么办？下一节的 Bellman-Ford 用"老老实实多轮迭代"换来了对负权的容忍，还能顺手告诉我们图里有没有负环。