图系列第 9 篇：Dijkstra 深入——堆优化与实现细节

嘿，朋友，欢迎回到图系列。这是第 9 篇，我们要把图论里出镜率最高、面试和竞赛里最常见、也是无数”最短路径”故事主角的算法——Dijkstra（迪杰斯特拉）——彻底吃透。你可能已经在别的地方见过它的”标准三步”：初始化、找最小、松弛。但今天这篇文章不满足于”会背步骤”，我们要回答三个更扎心的问题：为什么它是对的？为什么堆优化能提速？以及为什么真实代码里到处都是坑？

如果你是从头一路读过来的，这一篇会非常舒服，因为前面攒下的装备全部派上用场：第 3 篇的邻接表告诉我们图怎么存，第 4 篇的 BFS 给了我们”逐层扩散”的直觉，第 7 篇的拓扑排序让我们见识了”循环 + 贪心选择”的威力，而第 8 篇用 BFS 拿下了无权图的最短路径。今天等于给第 8 篇的结论加上”边有权重”这个现实条件，把”步数”升级成”总代价”。

下面这张路线图是今天的长途计划：先回顾 Dijkstra 的基本流程；然后用归纳法把”已确定集合里的距离不会再变”讲出直觉，顺便找出非负权条件到底卡在哪一步；接着写一版朴素实现，看看 O(V²) 什么时候够用；然后进入重头戏——用优先队列做堆优化，包括重复入队、懒惰删除和复杂度推导；再学会用 prev 数组还原完整路径；接着列出一张”边界与 bug”清单，把新手（和老手）最容易翻车的地方一网打尽；最后介绍几个变体，并理清 Dijkstra 与 BFS、A* 的关系。文末还有实现要点速查表和七道自测题，答案全部附在最后。

好，系好安全带，我们从回顾开始。

1 回顾：从 BFS 到带权最短路径

1.1 第 8 篇我们走到了哪里

在上一篇里，我们解决的是无权图上的最短路径问题：每条边的代价都看成 1，从起点到某个顶点的最短路径，就是”最少经过几条边”。我们用的工具是 BFS：把起点放进队列，一层一层往外扩散，第一次访问到某个顶点时的层数，就是它到起点的最短距离。当时的关键洞察是：BFS 之所以能保证第一次访问就是最短，是因为队列天然按距离从小到大处理顶点——距离 0 的先出队，然后距离 1 的，然后距离 2 的，严格递增，绝不插队。

我们还学会了用 dist 数组记录距离，用 visited 数组防止重复入队，并在文章后半段用”前驱数组”把一条最短路径完整还原出来。如果你对”为什么 BFS 第一次访问就是最短”还有疑问，建议先回头把第 8 篇再翻一遍，因为今天 Dijkstra 的正确性论证，和它是同一个血脉：谁先被确定，谁的距离就最小，因此不会再被其他路径打败。

但现实世界很少这么整齐。从家到公司的路线，每条路长短不一；网络数据包经过的每条链路，延迟各不相同；地图导航里的每段路程，耗时有高有低。把”每条边都是 1”这个假设拿掉，图就变成了带权图：每条边有一个非负的权重（weight），路径的总代价是边上所有权重之和，最短路径问题的目标变成”找一条总权重最小的路径”。

graph LR
    S["起点 家"] -->|"0.8 km"| A["路口 A"]
    S -->|"1.2 km"| B["路口 B"]
    A -->|"0.5 km"| T["公司"]
    B -->|"2.5 km"| T
    A -->|"0.4 km"| B

上图里，从家到公司有两条路：走 A 的总代价是 0.8 + 0.5 = 1.3，走 B 的总代价是 1.2 + 2.5 = 3.7。看起来走 A 更短，但注意 A 和 B 之间还有一条 0.4 的小路：家 → A（0.8）→ B（0.4）→ 公司（2.5）的总代价是 3.7，并不更优；而如果公司到家的方向有别的走法，我们还得重新算。直觉告诉我们，这种问题不能再用”第一次访问就结束”的 BFS 了：因为经过边的条数少，不代表总权重小。也许一条”绕远但每条路都轻”的路线，反而比”直路但堵车”更快。

1.2 松弛：所有最短路径算法的发动机

在深入 Dijkstra 之前，必须先认识一个贯穿整篇文章的操作——松弛（relaxation）。假设我们已经知道一条到顶点 u 的路径，代价是 dist[u]；现在从 u 出发有一条边通往 v，权重是 w。如果 dist[u] + w < dist[v]，说明”先到 u，再走这条边”比目前已知的到 v 的任何路径都更短，我们就更新：

dist[v] = dist[u] + w

这个更新动作就叫”松弛”。名字很形象：把 dist[v] 从原来”绷得紧紧的、偏大的估计值”放松到一个更小的值。注意这里有个极其重要的细节：我们更新的是”当前已知的最短距离估计”，而不是”最终答案”。dist[v] 可能被多次松弛，每次遇到更短的路径就再次缩小，直到算法结束才稳定成真正的答案。

几乎所有最短路径算法——BFS、Dijkstra、Bellman-Ford、SPFA、Floyd——都可以用”反复松弛”来统一理解。它们的区别只在于：以什么顺序、松弛多少次，才能保证最终结果正确。BFS 因为权重全为 1，出队顺序恰好就是从小到大，每个顶点只需要被松弛一次；Dijkstra 在非负权图上，用”每次挑最小的未确定顶点”来保证每个顶点被确定后就不用再松弛；Bellman-Ford 则干脆松弛 V−1 轮，任何顺序都不怕，代价是慢。

1.3 Dijkstra 的基本流程

1956 年，荷兰计算机科学家 Edsger Dijkstra 在阿姆斯特丹的咖啡馆里想出了这个算法。传说他当时带着未婚妻去逛街，坐下来休息的半小时里把算法画在了纸上。半个多世纪过去，这个算法依然是路由协议、地图导航、游戏寻路等无数系统的心脏。

假设图 G 有 V 个顶点、E 条边，所有边权非负，起点为 s。Dijkstra 的流程可以写成四步：

1. 初始化：dist[s] = 0，其余顶点的 dist 设为”无穷大”；所有顶点都处于”未确定”状态。
2. 选择：在未确定顶点中，选出 dist 值最小的那个，记为 u，把它标记为”已确定”（settled）。
3. 松弛：遍历 u 的所有出边 (u, v, w)，尝试松弛：如果 dist[u] + w < dist[v]，就更新 dist[v]。
4. 重复：回到第 2 步，直到所有顶点都被确定（或者所有可达顶点都被确定）。

flowchart TD
    A["初始化：dist[s]=0，其余为 INF"] --> B{"还有未确定顶点？"}
    B -- "否" --> F["结束，dist 即为最终最短距离"]
    B -- "是" --> C["从未确定顶点中选出 dist 最小的 u"]
    C --> D["把 u 标记为已确定"]
    D --> E["松弛 u 的所有出边 (u, v, w)"]
    E --> B

这个流程和 BFS 的”一层一层”看起来完全不同，但精神是一致的：BFS 用队列保证处理顺序按距离递增；Dijkstra 用”每次挑 dist 最小”保证处理顺序也按最终距离递增。区别在于，BFS 的队列天然有序，而带权图里”最小”需要主动寻找。

1.4 本篇要深挖什么

如果只看上面四步，Dijkstra 似乎三分钟就能讲完。但真正写代码、跑数据、调 bug 时，你会发现每一个细节都在等你：为什么”挑最小”这一步如此关键？用数组扫描和用优先队列有什么区别？重复入队是怎么回事，懒惰删除又是什么？路径怎么还原？遇到自环、重边、不可达顶点该怎么办？INF 取多少才不会溢出？这些问题，正是本篇文章存在的意义。我们不仅要知道”算法怎么写”，还要知道”为什么这么写、坏在哪里、怎么修”。

2 正确性直觉：已确定集合里的距离为什么不再变

2.1 先抛出一个反直觉的疑问

请看下面这个例子：起点是 A，图里有 B、C、D 三个顶点。假设第一轮选择时，dist[B] = 1、dist[C] = 5、dist[D] = 3，于是算法把 B 标记为已确定。这时你的脑海里应该响起一个声音：凭什么 B 的 1 就是最终答案？万一有一条”绕远路”：A → C（5）→ B（-100）呢？ 啊，这个疑问问得太好了——如果允许负权边，这个质疑就是致命的，Dijkstra 会直接给出错误答案。而如果所有边权非负，这个质疑就会被下面这个论证彻底击碎。

关键在于：B 的当前距离是”所有未确定顶点里最小的”，而任何一条从 A 出发、最终到达 B 的路径，都必须从”已确定的区域”跨到”未确定的区域”一次。每跨一次，都要经过一条非负的边，路径的总代价只会增加，不会减少。既然 B 已经是未确定区域里”已知代价最小”的顶点，任何”先走到某个更远的未确定顶点，再绕回 B”的路径，代价都不可能小于 B 当前的 1。

2.2 用”确定区”的比喻来看

想象整个图被一条分界线分成两块：左边是”已确定集合 S”，里面每个顶点的 dist 都已经是最终答案；右边是”未确定集合 T”，里面每个顶点的 dist 还只是”当前已知的最好估计”。算法的每一步，都在做同一件事：找到 T 里 dist 最小的顶点 u，把它搬进 S，并顺带把 u 的出边延伸到 T 里的邻居，看看能不能让它们的估计值更小。

graph LR
    subgraph S["已确定集合 S（dist 已是最终值）"]
        s["起点 A"]
        b["B (dist=1)"]
        c["C (dist=5)"]
    end
    subgraph T["未确定集合 T（dist 只是估计值）"]
        d["D (dist=3)"]
        e["E (dist=8)"]
        f["F (dist=12)"]
    end
    c -->|"2"| e
    d -->|"4"| f
    s -.->|"分界线"| d

分界线上的所有边，都是从 S 指向 T 的边。请注意一个事实：从 A 出发到达 T 中任何顶点的任何路径，最后一步必然是从 S 跨过分界线到 T 的那条边（除非路径完全绕开 S，但起点 A 本身就在 S 里，所以任何路径一开始就在 S 里，第一次离开 S 必然跨过分界线）。所以，如果我们想知道”T 里哪个顶点可能拥有全局最短的路径”，只需要比较：dist[x] + w，其中 x 在 S 里、边 (x, y) 跨过分界线到 y。而 Dijkstra 的”选 T 中 dist 最小”为什么等价于这个比较？因为 dist[y] 已经是”经过分界线上某条边到达 y”的最小代价——每次松弛都在维护这个值。

当算法选中 u 时，dist[u] 是 T 中所有估计值里最小的。现在假设存在一条真正更短的路径 P 到达 u，那么 P 第一次离开 S 时经过的边是 (x, y)，y 在 T 中。P 的完整代价 = 到 x 的代价 + w(x, y) + 后续代价。到 x 的代价就是最终的 dist[x]（x 在 S 里，已经确定），而后续代价里每条边都非负，所以 P 的总代价 ≥ dist[x] + w(x, y) ≥ dist[y]（因为松弛保证 dist[y] 不超过任何跨分界线进入 y 的代价）≥ dist[u]（因为 u 是 T 里最小的）。瞧，任何替代路径都不比 dist[u] 小，所以 dist[u] 就是最终答案，可以放心把 u 搬进 S。

2.3 把直觉写成严格的归纳

如果上面的文字你已经看懂，恭喜，Dijkstra 的正确性你已经掌握了八成。剩下两成，是把它整理成可以写进证明题的归纳结构，方便你在面试时三句话讲完：

归纳假设：在第 k 轮开始时，已确定集合 S 中的每个顶点 x 都满足 dist[x] 等于从 s 到 x 的真实最短距离。

基础情形：k = 0 时，S = {s}，dist[s] = 0，显然成立。

归纳步骤：假设 S 中的顶点都正确。算法从 T 中选出 dist 最小的 u。设 P 是从 s 到 u 的任意一条真实最短路径（如果 u 不可达，dist[u] 为 INF，选择逻辑另当别论，我们稍后讨论）。P 从 s 出发，s 在 S 中，而 u 在 T 中，所以 P 上必然存在一条边 (x, y)，使得 x 在 S 中、y 在 T 中，且 y 之后的部分还在 T 中。由于 y 在 T 中，且 u 是 T 中 dist 最小的，dist[y] ≥ dist[u]。由于所有边权非负，P 的代价 ≥ 从 s 到 x 的代价 + w(x, y) ≥ dist[x] + w(x, y) ≥ dist[y]（最后的 ≥ 是因为我们曾经松弛过 x 的出边 (x, y)）≥ dist[u]。但 dist[u] 本身就是一条从 s 到 u 的路径（当前估计值对应一条真实存在的路径）的代价，所以 P 的代价 ≥ dist[u]，而 P 又是最短路径，于是 P 的代价 = dist[u]。u 的估计值就是真实值，把它加入 S 后，归纳假设依然成立。

注意最后一步推理里的两个”≥“分别使用了什么条件：dist[x] + w(x, y) ≥ dist[y] 用到了松弛操作的正确性（任何跨分界线的边都至少被检查过一次）；P 的代价 ≥ dist[x] + w(x, y) 用到了边权非负——如果后续边有负权，后续部分可能”倒贴钱”，让整条路径比前缀更便宜。这就是非负权条件发挥作用的确切位置。

2.4 如果允许负权边：一张图说明灾难

让我们实际看一看负权边是怎么把 Dijkstra 骗倒的。下图里 A 是起点，B 的 dist 初始为 4，C 的 dist 初始为 3，第一轮算法会选中 C（因为 3 < 4），把 C 标记为已确定：

graph LR
    A["起点 A"] -->|"4"| B["B"]
    A -->|"3"| C["C"]
    C -->|"-5"| B
    style C fill:#ffaaaa

然而真正的最短路径是 A → C → B，总代价是 3 + (−5) = −2，比直接 A → B 的 4 小得多。可惜 C 被确定之后，算法才通过 C 松弛 B，把 dist[B] 更新成 −2——但 B 甚至可能已经被确定过了！一旦一个顶点被标记为已确定，Dijkstra 的经典实现就再也不会回头修改它，于是错误答案被永久固化。

问题的根源正是 2.3 里的证明：当存在负权边时，“P 的代价 ≥ 前缀代价”不再成立。一条路径可以先走一段很长的路，再靠一条负权边把总代价”倒贴”回最小值。这就像你绕地球一圈去买打折机票，结果总花费反而比直飞还便宜——正常的贪心顺序完全无法预判这种操作。因此，Dijkstra 只适用于所有边权非负的图。如果图中确实存在负权边，请改用 Bellman-Ford（第 10 篇的主角）或者 SPFA。

2.5 三个容易误解的点

第一，“已确定”不等于”已经访问过”。BFS 里 visited 的作用是防止重复入队，而 Dijkstra 里的 settled 是一个更强的声明：这个顶点的最终距离已经算出，以后再也不会被更新。第二，dist[v] 在 v 未确定前可能被松弛很多次，每次都在变小，这是正常的，不是 bug。第三，已确定顶点的 dist 绝不会被后续松弛改变——因为任何经过未确定顶点的替代路径都不可能更短（这正是上面证明的内容）。有些实现里没有显式的 visited/settled 数组，而是用”当顶点被弹出时检查它是否已被确定”来代替，这在堆优化版里很常见，我们会在第 4 节详细展开。

2.6 为什么可以称之为”贪心”

Dijkstra 经常被归类为贪心算法，因为它每轮都”目光短浅”地选择当前看起来最优的顶点。但有趣的是，这种贪心在非负权图上恰恰是安全的：当前 dist 最小的未确定顶点，必然就是全局最小——不存在”先选一个大的，再绕回来反而更小”的可能性。这有点像排队结账：如果每个人付的钱数已经标好，而且金额永远不会减少，那么每次挑金额最小的队伍去排，总能得到最优解。第 7 篇的 Prim 算法（最小生成树）也使用了类似的思想：每次都选一个”跨越已确定区域的最小边”，区别在于 Prim 贪的是”加入树的最小边”，Dijkstra 贪的是”到达顶点的最小距离”。

当然，“贪心正确”是有前提的，前提就是非负权。一旦前提不成立，贪心立刻翻车。这也是为什么我们在写代码之前，一定要先检查题目是否满足”所有边权 ≥ 0”，不满足就换算法——这是面试和竞赛中最高频的”审题错误”之一。

2.7 三角不等式与最短路径树

算法结束后，dist 数组不是一组随便的数，它满足一个漂亮的几何性质：对任意一条边 (u, v, w)，都有 dist[v] ≤ dist[u] + w。为什么？因为如果 dist[u] + w < dist[v]，那么”起点到 u 的最短路径 + 这条边”就是一条比 dist[v] 更短的路径，与 dist[v] 是最终最短距离矛盾。这个不等式叫三角不等式，和几何里”两边之和大于第三边”异曲同工：直接从 u 到 v 不会比绕道 u 再走边更远——因为那条边本身就是一条”路”。

这个性质有三个用途。第一，它可以当正确性自检：算法跑完，遍历所有边验证不等式，只要有一条不成立，你的实现一定有 bug（6.6 节提到过）。第二，它揭示了”最短路径的局部最优性”：一条最短路径的任意前缀，也必须是前缀两端之间的最短路径——不然把前缀替换成更短的走法，整条路径就变短了。这个”前缀最优”性质是所有贪心路径算法的基石，也是 Dijkstra 能把大问题拆成小问题逐个确定的深层原因。第三，把每条边的方向想成”只从 dist 小的顶点指向 dist 大的顶点”（权重为 0 时可以相等），所有最短路径合起来形成一棵以起点为根的树——最短路径树。第 5 节的 prev 数组，就是这棵树在代码里的化身。

还有一个小众但面试爱问的点：权重为 0 的边会不会破坏 Dijkstra？ 不会。归纳证明里只需要”边权非负”，0 恰好满足。0 权边带来的唯一变化是可能出现 dist[u] === dist[v] 的情况，prev 链上相邻顶点的距离可以相等，但每个顶点依然只有一个 prev，且沿着 prev 走不会形成环（因为形成环意味着 dist 不增地绕一圈回到自己，等价于存在一条 0 权环；若环上所有边权都是 0，环内顶点的最短距离相同，选哪个 prev 都不影响距离，但实现里 prev[v] = u 只在严格小于时更新，所以 prev 依然指向第一次发现最短路径的顶点，不会产生循环引用）。一句话：0 权边无害，负权边致命，这个分界线请刻在脑子里。

3 朴素实现：数组找最小 O(V²)

3.1 最直接的写法

理解了正确性之后，写一版”教科书实现”就非常简单了：维护 dist 数组和 visited 布尔数组，每一轮都用一趟线性扫描，从所有未访问顶点中找出 dist 最小的那个，然后松弛它的出边。因为一共要确定 V 个顶点，每轮扫描数组要 O(V)，总时间复杂度就是 O(V²)；如果再加上松弛所有出边，邻接表下总共是 O(V² + E)，而 E 最多 V²，所以通常直接写 O(V²)。

这里的关键成本不是松弛，而是”找最小”。每一轮都要重新在数组里从头到尾找一遍，上一轮的信息完全不能复用：上轮最小的是 A，这轮也许还是 A 的某个邻居，也许跳到十万八千里外，谁知道呢？数组不会告诉我们，只能老老实实再看一遍。

3.2 朴素版 JavaScript 实现

下面用邻接矩阵实现一版最朴素的 Dijkstra，方便和后面的堆优化版做对比。为了突出算法本身，这里假设顶点编号是 0 到 n−1，graph[u][v] 表示 u 到 v 的边权，没有边就是 Infinity：

function dijkstraNaive(graph: number[][], s: number): number[] {
  const n = graph.length;
  const dist = new Array<number>(n).fill(Infinity);
  const visited = new Array<boolean>(n).fill(false);
  dist[s] = 0;

  for (let round = 0; round < n; round++) {
    // 第 1 步：扫描找最小
    let u = -1;
    let best = Infinity;
    for (let v = 0; v < n; v++) {
      if (!visited[v] && dist[v] < best) {
        best = dist[v];
        u = v;
      }
    }
    if (u === -1) break; // 剩余顶点全部不可达

    visited[u] = true; // 第 2 步：确定 u

    // 第 3 步：松弛所有出边
    for (let v = 0; v < n; v++) {
      const w = graph[u][v];
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }
  return dist;
}

逐行看几个容易忽略的细节。第一，visited 在这里不是”防止重复访问”那么简单，而是”永久确定”的标志：visited[u] = true 之后，u 永远不会再被选为最小，也不会再被松弛，这正是正确性证明里”已确定集合 S”的代码化身。第二，内层扫描里 dist[v] < best 用严格小于，所以当多个顶点并列最小时，选编号小的那个；并列时选谁都行，不影响正确性。第三，if (u === -1) break 处理了不可达顶点：当所有剩余顶点的 dist 都是 Infinity 时，再怎么找也不会找到更好的路径，直接结束，节省时间。第四，松弛时如果 w 是 Infinity，dist[u] + Infinity 还是 Infinity，不会误更新；如果 dist[u] 本身就是 Infinity（理论上选不到，因为不可达顶点不会先被选中），也依然安全——Infinity + w 仍是 Infinity。

3.3 什么时候 O(V²) 够用

O(V²) 听起来吓人，但在很多场景下它反而是最优选择。判断标准是图的稠密程度：如果边数 E 接近 V²（稠密图），那么堆优化版的 O((V+E) log V) ≈ O(V² log V)，比 O(V²) 还多了一个 log 因子；而数组扫描版既没有堆的常数开销，也不需要维护复杂的结构，代码还更短，出错概率更低。换句话说，图越稠密，朴素版越香。

具体量级感受一下：V = 1000 时，V² = 10⁶，无论用哪种写法都眨眼完成；V = 5000 时，V² = 2.5 × 10⁷，现代计算机也能在零点几秒内跑完，如果边数接近满的（E ≈ 2.5 × 10⁷），堆优化反而更慢；V = 10⁵ 时，V² = 10¹⁰，朴素版需要几十秒甚至几分钟，此时必须上堆优化——除非你的图真的稠密到 E 也是 10⁹ 量级，那连读图都读不进来，通常不在考虑范围。

所以经验法则可以记成两句话：顶点很少（几千以内）或者边非常密时，用朴素版；顶点多且边稀疏时，用堆优化版。刷题时看数据范围：如果 V ≤ 10⁴ 且 E ≤ V²，O(V²) 通常能过；如果 V 到 10⁵、E 只有 2×10⁵，朴素版必死，堆优化是唯一出路。

3.4 朴素版的隐藏代价

还有两个”隐藏代价”值得一提。第一，邻接矩阵本身要 O(V²) 空间，V = 10⁵ 时仅矩阵就 10¹⁰ 个格子，按 8 字节算要 80GB，直接内存爆炸；所以”稠密图用矩阵”的前提是 V 足够小。第二，扫描找最小只利用了”dist 最小的未确定顶点”这个信息，却把”谁次小、谁第三小”全部丢掉了，下一轮又要重新扫描——这就是信息浪费的本质。优先队列优化的动机，就是把这堆”次小、第三小”的信息存起来，避免反复扫描。

4 堆优化：优先队列与懒惰删除

4.1 为什么要堆

让我们面对一个具体的现实：一张稀疏图，V = 10⁵ 个顶点，E = 2 × 10⁵ 条边。用朴素版，扫描要 10⁵ × 10⁵ = 10¹⁰ 次比较，哪怕每次比较只要 1 纳秒，也要 10 秒；而松弛只需要 E = 2 × 10⁵ 次，微不足道。很明显，瓶颈就在”找最小”。

我们需要一种数据结构，支持三个操作：插入一个 (dist, vertex) 对；取出当前 dist 最小的对；以及当某个顶点的 dist 变小时，更新它。二叉最小堆（binary min-heap）恰好满足全部需求：插入 O(log V)，取最小 O(log V)，更新 O(log V)。第 16 篇树系列文章我们专门讲过堆的结构，这里只复习一句：堆是一棵”父节点永远不大于子节点”的完全二叉树，所以堆顶永远是最小值。

4.2 优先队列里存什么

堆优化版的核心思路是把”未确定顶点集合”换成”优先队列”，队列里每个元素是一个二元组 (dist, vertex)，按 dist 从小到大排序。每次从堆顶取出的顶点，就是当前未确定顶点里 dist 最小的那个——正是朴素版扫描半天要找的东西。

第一次接触堆优化时，很多人会问：堆里存的是”未确定顶点”，那松弛时发现 dist[v] 变小了，怎么”更新”堆里的旧元素？答案出乎意料地简单：不更新，直接再插入一个新元素。旧元素留在堆里不管，等它将来被弹出时，发现自己的 dist 已经过时，就跳过它。这个”留着不管、过期作废”的策略，江湖人称懒惰删除（lazy deletion）。

4.3 重复入队是怎么发生的

下面用一张小图走一遍，看看堆里为什么会出现同一个顶点的多个条目。起点 A，三条出边：A→B 权重 2，A→C 权重 5，B→C 权重 1：

graph LR
    A["A (起点)"] -->|"2"| B["B"]
    A -->|"5"| C["C"]
    B -->|"1"| C

算法开始时，堆里只有 (0, A)。弹出 A，松弛两条出边：dist[B] 从 INF 变成 2，入堆 (2, B)；dist[C] 从 INF 变成 5，入堆 (5, C)。此时堆里有 (2, B) 和 (5, C)。下一轮弹出 (2, B)，松弛 B→C：2 + 1 = 3 < 5，于是 dist[C] 更新成 3，又一个 (3, C) 被塞进堆里。此刻堆里同时存在 (5, C) 和 (3, C) 两个条目！

当 (3, C) 被弹出时，它是最新的，正常处理；而当 (5, C) 后来被弹出时，5 > dist[C] = 3，说明这是过时条目，直接丢弃。这个”弹出的值大于当前 dist”的判断，就是懒惰删除的全部实现：

const [d, u] = heap.pop();
if (d !== dist[u]) continue; // 过时条目，跳过

这里用 !== 还是 > 都可以（更稳妥的是 >,因为浮点或 NaN 场景），语义是：我弹出时声称 d 是 u 的最短距离，但如果 u 的 dist 已经不是 d 了，说明后来有更短路径，这个条目作废。注意这个判断同时充当了”已确定”检查：因为每个顶点被确定后 dist 就不再改变，而它最后一次入堆时的 d 必然等于 dist[u]，所以”弹出的 d 等于 dist[u]“等价于”这个条目有效且 u 第一次以最终距离被处理”。为什么它不会在 u 被确定之后又出现一个有效的 (dist[u], u)？因为确定 u 之后，只有更短的路径才会触发新的入堆，而更短的路径不可能存在（正确性证明保证），所以 u 不会再次以有效条目出现。

4.4 堆内容变化的完整走查

为了把”堆里到底发生了什么”看清楚，我们给上面那张图配一份逐步记录。每一步后面括号里是堆的内容，按 dist 从小到大排列：

flowchart TD
    P0["初始：堆 = [(0, A)]"] --> P1["弹出 (0, A)，松弛 B、C：堆 = [(2, B), (5, C)]"]
    P1 --> P2["弹出 (2, B)，松弛 C：dist[C] 5 → 3，入堆 (3, C)：堆 = [(3, C), (5, C)]"]
    P2 --> P3["弹出 (3, C)，有效，松弛完成：堆 = [(5, C)]"]
    P3 --> P4["弹出 (5, C)，5 > dist[C] = 3，过时条目，跳过：堆 = []"]
    P4 --> P5["结束：dist = {A: 0, B: 2, C: 3}"]

注意第 4 步：堆里弹出的 (5, C) 并不是”C 又变近了”，而是”旧数据还赖在堆里没走”。如果不做这个跳过判断，C 会被重复处理一次；在更复杂的图上，一个顶点可能被弹出几十次，每次处理它的出边，复杂度就会失控，甚至可能因为重复松弛而无限循环（虽然 dist 单调下降，最终会停，但时间上不可接受）。

4.5 懒惰删除的另一个视角

其实懒惰删除的思想到处都有：浏览器的缓存过期了不立刻删，等有人来访问时再检查；操作系统里的”脏页”先标记、不着急写回磁盘；我们日常用的”已读未读”标记，本质也是”先留着，下次见到再处理”。在算法里，它的价值是用空间换时间：为了不实现复杂的”堆内任意位置更新”（decrease-key），我们宁可让堆里多存几个过期元素，换取插入操作的简单和正确。付出的代价是堆的体积可能超过 V，达到 O(E) 级别——这完全在可接受范围内，因为后面会证明总插入次数是 O(E)。

有些实现会去写真正的 decrease-key（堆内定位顶点、向上调整），把堆大小严格限制在 V。这在理论上有意义，但实现极易出错：需要额外维护一个 pos[v] 数组记录 v 在堆数组里的下标，堆交换元素时要同步更新，稍微漏一处就出现悬空下标。竞赛和工程实践里，“重复入队 + 懒惰删除”是绝对的主流，代码短、正确性容易验证，性能也足够好。所以本文只讲这一种。

4.6 为什么复杂度是 O((V+E) log V)

很多人背下”O((V+E) log V)“这个式子，却说不清 log 到底乘在哪。让我们一步步推，顺便把”为什么是 V+E 而不是别的”讲明白。

先看插入。每个顶点的 dist 一旦被成功松弛（从 INF 变成有限值，或者从大值变成更小值），就会往堆里推入一个新条目。问题来了：一个顶点最多能被成功松弛几次？答案藏在 Dijkstra 的性质里：每次成功松弛都会把某个顶点的 dist 严格变小，而每个顶点的 dist 最终只会被确定一次，且确定后不再改变。更精确的界是：每条边最多触发一次成功松弛。为什么？假设边 (u, v, w) 在 u 被弹出时让 dist[v] 变小了；u 只会以有效条目被弹出一次（4.3 节论证过），所以这条边只会被”正式松弛”一次。至于从别的顶点绕过来再次松弛 v，那属于别的边，各自独立。因此总插入次数 ≤ 初始的 V 次（每个顶点第一次被从 INF 松弛成有限值，最多一次）+ 所有边成功松弛的次数 ≤ V + E，即 O(V + E)。

再看删除。堆里每有一个条目，最终都会被弹出一次——有效的处理，过期的跳过。所以 pop 的总次数也 ≤ 总插入次数 = O(V + E)。每次 push 或 pop，二叉堆都要沿着树高调整，树高是 O(log(堆大小)) = O(log V)（堆大小最坏 O(V+E)，但 log(V+E) 和 log V 同阶，因为 E 也不会超过 V² 太多以至于改变数量级；严格地说这是 O(log(V+E))，通常简写为 O(log V)）。三项合并：插入 O((V+E) log V)，删除 O((V+E) log V)，松弛本身 O(E)，总复杂度 O((V+E) log V)。

还有一个更常用的化简：在连通图（或者从起点能到达所有顶点）里 E ≥ V−1，所以 O((V+E) log V) = O(E log V)。这就是竞赛笔记里”堆优化 Dijkstra 是 O(E log V)“的来源。另外提醒一句，这里说的是二叉堆的复杂度；如果使用 Fibonacci 堆，插入和 decrease-key 是摊还 O(1)，取最小是 O(log V)，理论复杂度可以降到 O(E + V log V)。但 Fibonacci 堆常数巨大、实现复杂，工程上几乎不用，了解即可。

4.7 完整的 TypeScript 实现

下面是一份可以直接跑起来的完整实现：一个最小堆类加一个 dijkstra 主函数。为了不依赖任何第三方库，堆是我们自己写的；它的代码不长，但每个方法都值得看一遍，因为堆是实现 Dijkstra 时最容易写错的部分。

// 最小堆：元素是 [dist, vertex]
class MinHeap {
  data: Array<[number, number]> = [];

  push(item: [number, number]): void {
    this.data.push(item);
    this.siftUp(this.data.length - 1);
  }

  pop(): [number, number] | undefined {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length > 0) {
      this.data[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p][0] <= this.data[i][0]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }

  private siftDown(i: number): void {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const l = i * 2 + 1;
      const r = i * 2 + 2;
      if (l < n && this.data[l][0] < this.data[smallest][0]) smallest = l;
      if (r < n && this.data[r][0] < this.data[smallest][0]) smallest = r;
      if (smallest === i) break;
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

function dijkstra(
  graph: Array<Array<[number, number]>>, // 邻接表：graph[u] = [[v, w], ...]
  s: number
): { dist: number[]; prev: number[] } {
  const n = graph.length;
  const dist = new Array<number>(n).fill(Infinity);
  const prev = new Array<number>(n).fill(-1); // 前驱，路径还原用
  dist[s] = 0;

  const heap = new MinHeap();
  heap.push([0, s]);

  while (heap.data.length > 0) {
    const item = heap.pop()!;
    const d = item[0];
    const u = item[1];

    if (d > dist[u]) continue; // 懒惰删除：过时条目

    for (const [v, w] of graph[u]) {
      const nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        prev[v] = u;
        heap.push([nd, v]);
      }
    }
  }

  return { dist, prev };
}

这份代码虽然短，却有五个细节值得逐条拆解，面试时能说清这五条，Dijkstra 实现基本就过关了。

第一，heap.pop() 返回的是”当前堆里 dist 最小的条目”，但堆只保证堆顶最小，堆里的兄弟之间没有顺序，所以弹出顺序不是”严格递增”的全局序列——这不重要，重要的是每次弹出的都是当前最小。第二，if (d > dist[u]) continue 是懒惰删除的唯一检查：弹出的 dist 比数组里的当前值大，说明这个条目过时。用 > 而不是 !==，是为了在极端情况下（比如浮点 NaN 或者多个 INF）更稳健；!== 在整数场景完全等价。第三，这里没有 visited 数组，也不需要：一个顶点一旦被弹出，它的 dist 就是最终值，之后不会有更小的 nd 能更新它（正确性证明），所以它不会以有效条目再次弹出；如果有过时条目弹出，也被第一行跳过。第四，prev[v] = u 放在成功松弛里，记录”v 的最新最短路径是从 u 来的”，这就是下一节路径还原的原料。第五，循环条件是堆非空，而不是”第 V 轮”：堆空了说明所有可达顶点都已确定，不可达顶点的 dist 保持 Infinity，算法自然结束，连 break 都不用写。

4.8 堆里存边还是存顶点

再聊一个实现层面的小问题：为什么堆元素是 (dist, vertex) 而不是只存顶点编号？因为堆排序的依据必须是 dist，如果只存顶点编号，堆就无法知道该顶点当前排在哪里。当然也可以只存顶点，靠外部数组在比较器里取 dist，但那样堆内部交换元素时 dist 可能已经变化，比较结果会和入堆时不一致，堆的性质会被破坏——这是”索引堆”要解决的难题。所以最稳妥的做法就是把 dist 和 vertex 绑在一起存，让每条目携带自己入堆时的快照；过期条目自然被懒惰删除拦截。这个”快照”思想在别的算法里也很有用：任何”排队等处理、价格可能变化”的场景，都可以考虑存快照加惰性校验。

4.9 完整手算走查：六个顶点跑一遍

理论讲得再多，也不如亲手跑一遍。下面这张图有 6 个顶点、8 条边，起点是 A。我们一边跑一边记录堆的内容，完整复现 Dijkstra 的每一步：

graph LR
    A["A"] -->|"4"| B["B"]
    A -->|"2"| C["C"]
    B -->|"1"| C
    B -->|"5"| D["D"]
    C -->|"8"| D
    C -->|"10"| E["E"]
    D -->|"6"| F["F"]
    E -->|"2"| F

初始化：dist = {A: 0, B: INF, C: INF, D: INF, E: INF, F: INF}，堆 = [(0, A)]。

第 1 步：弹出 (0, A)。A 已确定。松弛 A→B（4）和 A→C（2）：dist[B] = 4，dist[C] = 2，入堆。此时堆 = [(2, C), (4, B)]。

第 2 步：弹出 (2, C)。C 已确定。松弛 C→D（8，2+8=10）和 C→E（10，2+10=12）：dist[D] = 10，dist[E] = 12。堆 = [(4, B), (10, D), (12, E)]。

第 3 步：弹出 (4, B)。B 已确定。松弛 B→C（4+1=5，不小于 2，跳过）和 B→D（4+5=9，小于 10）：dist[D] = 9，prev[D] = B，入堆 (9, D)。堆 = [(9, D), (10, D), (12, E)]。注意，堆里现在同时有 D 的旧条目 (10, D) 和新条目 (9, D)。

第 4 步：弹出 (9, D)。D 已确定。松弛 D→F（9+6=15）：dist[F] = 15，入堆。堆 = [(10, D), (12, E), (15, F)]。

第 5 步：弹出 (10, D)。检查发现 10 > dist[D] = 9，这是第 3 步留下的过时条目，直接跳过，不处理任何出边。堆 = [(12, E), (15, F)]。

第 6 步：弹出 (12, E)。E 已确定。松弛 E→F（12+2=14，小于 15）：dist[F] = 14，prev[F] = E，入堆 (14, F)。堆 = [(14, F), (15, F)]。

第 7 步：弹出 (14, F)。F 已确定，无出边。堆 = [(15, F)]。

第 8 步：弹出 (15, F)，15 > dist[F] = 14，过时条目，跳过。堆空，算法结束。

最终结果：dist = {A: 0, B: 4, C: 2, D: 9, E: 12, F: 14}，prev = {B: A, C: A, D: B, E: C, F: E}。从 A 到 F 的最短路径是 A → C → E → F，总代价 2 + 10 + 2 = 14。

把每一轮堆的变化汇总成一张表：

这张表值得多看两眼，因为它浓缩了本章几乎所有知识点：每一轮弹出的都是”当前未确定里 dist 最小”的顶点（正确性依赖）；D 和 F 都被松弛过两次，第二次都来自更短的路径（松弛的反复性）；堆里出现过 (10, D) 和 (15, F) 两个过时条目，都被懒惰删除拦下（堆优化的实现细节）；最终 prev 链还原出的路径绕过了直接走 D 的 15，改走 E 的 14（Dijkstra 的全局最优）。如果你在纸上把这张表独立推一遍，不偷看答案，你会对算法产生一种”肌肉记忆”——这比读十遍文章都管用。

4.10 堆的每个方法到底在做什么

堆优化的代码里，最容易出 bug 的不是 Dijkstra 主函数，而是那个最小堆本身。很多人直接抄一个堆模板，出了错也不知道是堆的问题还是算法的问题。所以这里把 4.7 节里 MinHeap 的每个方法单独拆开，讲清楚它为什么这么写。

为什么堆用数组存？ 二叉堆是一棵完全二叉树：除了最后一层，每一层都填满，最后一层从左到右连续。完全二叉树有一个妙处：可以按”层序”平铺进数组，根节点在下标 0，然后不用任何指针，光靠下标就能算出父子关系——节点 i 的左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1) >> 1。这既省内存（不需要存 left/right 指针），又让整棵树在内存里连续分布，缓存友好。下图是堆 [(3, C), (5, C), (8, D), (12, E)] 的数组与树形对应关系：

graph TD
    N0["下标 0： (3, C)"] --> N1["下标 1： (5, C)"]
    N0 --> N2["下标 2： (8, D)"]
    N1 --> N3["下标 3： (12, E)"]

push 为什么只向上调整？ 新元素先放到数组末尾（也就是树的最右下角），此时除了”新元素可能比它的父节点小”之外，堆的其他部分依然满足”父 ≤ 子”。所以只需要让新元素沿着父链往上爬：只要它比父节点小，就和父节点交换，一直爬到正确位置。这个操作叫 siftUp（上滤）。循环条件里用 this.data[p][0] <= this.data[i][0] 就停，保证相等的元素不用换——换不换都行，不影响正确性，但不换可以少几次交换。

pop 为什么先取堆顶再下滤？ 最小值必然在堆顶（下标 0）。直接删掉堆顶会把树劈成两半，没法继续维护。标准做法是：把数组最后一个元素挪到堆顶，然后让这个”冒名顶替者”沿着孩子链往下走，每次和两个孩子里较小的那个比较，只要它比孩子大就交换，直到两个位置都合适。这个操作叫 siftDown（下滤）。注意必须和较小的孩子交换：如果和大孩子交换，那个较小的孩子会留在上面，违反”父 ≤ 子”的性质，堆就坏了。

为什么比较只看 [0]（dist）？ 堆元素是 [dist, vertex] 二元组，排序依据只有 dist。当两个元素 dist 相等时，谁在堆里靠前都无所谓，因为 Dijkstra 只关心”最小值是谁”，并列时选哪个顶点不影响最终结果。所以比较器只需要 a[0] < b[0]；如果你希望并列时优先编号小的顶点，可以把比较扩展成”dist 相同再比 vertex”，这是可选优化，不是必需。

堆代码的三个高频 bug。 一是 pop 之后忘记 siftDown：堆顶放了个大值就完事，下一次 pop 拿到的是错误的最小值。二是孩子下标算错：左孩子 2*i+1、右孩子 2*i+2 是从 0 开始编号的公式，如果从 1 开始编号的模板没改过来，数组访问会越界或者漏掉节点。三是在 siftUp/siftDown 里交换元素时，如果直接写 this.data[p] = this.data[i] 而不同时交换完整条目，会把 [dist, vertex] 对拆散，导致”dist 是 A 的、vertex 是 B 的”这种幽灵条目——比数值错误难查十倍。用解构赋值 [a, b] = [b, a] 一步交换两个元素，是最不容易出错的写法。

复杂度再确认一遍。 完全二叉树的高度是 O(log n)，siftUp 和 siftDown 都最多沿一条链走到根或叶子，所以 push 和 pop 都是 O(log n)。Dijkstra 总共做 O(V+E) 次 push/pop，于是总时间 O((V+E) log V)。堆的初始化（把 V 个起点条目逐个 push）也是 O(V log V)，合并进大 O 里没有额外开销。至此，4.7 的代码每一个字符都有了明确的意义，你可以放心地把它背进肌肉记忆。

4.11 各语言优先队列的注意点

自己手写堆能让你真正理解原理，但工程和竞赛里更多是直接用语言内置的优先队列。这里把主流语言最容易踩的坑各点一句。JavaScript 传统上没有内置优先队列，只能手写堆或者引入第三方库；好消息是 2025 年后 TC39 的 PriorityQueue 提案已经进入标准化的进程，未来可以直接用，但现阶段手写堆仍然是最稳妥的选择。Python 的 heapq 是小顶堆，默认按元组第一个元素排序，直接把 (dist, v) 往里塞就行，几乎零成本；唯一的坑是别往堆里塞 None 或者混合类型，比较时会报错。C++ 的 std::priority_queue 默认是大顶堆，直接存 dist 会取出最大值，必须用 greater<pair<long long, int>> 指定小顶堆，或者把距离取负再入堆——这是 C++ 选手最经典的翻车点。Java 的 PriorityQueue 默认小顶堆，但比较器写错（比如把 a.dist - b.dist 的符号搞反）会导致弹出顺序完全混乱；用 Long.compare(a, b) 而不是减法，还能避免溢出。Go 则需要实现 container/heap 接口，包括 Less 方法，第一次写时记得 heap.Init，忘了初始化堆会让”堆序”名存实亡。一句话总结：无论什么语言，先确认你的优先队列是小顶堆、比较器按 dist 升序，再开始写 Dijkstra；确认这一件事，能省下无数个深夜调试。

5 路径还原：从 dist 到完整路线

5.1 光有 dist 不够

到目前为止，Dijkstra 告诉我们的是”每个顶点离起点有多远”，但很多时候我们要的是一整条路线：从家出发，先到哪个路口，再到哪个路口，最后到公司。dist 数组回答”多远”，路线回答”怎么走”。

幸运的是，还原路径几乎不花额外成本：只要在松弛成功时，顺手记录”v 的最短距离是从 u 得到的”，即 prev[v] = u，算法结束时，我们就得到了一棵”最短路径树”。这棵树以起点为根，每个顶点的父指针指向它最短路径上的前一个顶点。为什么一定是一棵树而不是乱七八糟的图？因为每个顶点最多只有一个 prev，而且 prev[v] 指向的顶点到起点的距离一定严格小于 v（权重非负且松弛成功时 dist[u] < dist[v]，除非权重为 0 时可能相等，此时仍无环），所以顺着 prev 往回走，必然回到起点，不会陷入环。

5.2 一个完整的还原例子

沿用 4.3 的小图：A 到 B 权重 2，A 到 C 权重 5，B 到 C 权重 1。算法结束后，dist = {A: 0, B: 2, C: 3}，prev = {B: A, C: B}。把 prev 画出来，就是一棵以 A 为根的树：

graph TD
    A["A (dist=0, prev=-1)"] -->|"2"| B["B (dist=2, prev=A)"]
    B -->|"1"| C["C (dist=3, prev=B)"]
    style A fill:#aaddaa
    style B fill:#aaddaa
    style C fill:#aaddaa

注意 C 的 prev 是 B 而不是 A：虽然 A 到 C 直接有一条权重 5 的边，但 A → B → C 总权重只有 3，更短。这正是 Dijkstra 的魅力——它自己发现了那条”绕一下反而更快”的路，并且用 prev 把这条路的每一步都记了下来。

如果我们要从 A 走到 C，从 C 开始顺着 prev 往回走：C 的 prev 是 B，B 的 prev 是 A，A 的 prev 是 -1（起点），于是把序列反转，得到 A → B → C。这就是路径还原的全部原理。

5.3 递归打印与迭代还原

下面是两种还原写法。递归版最直观，但路径很长时可能爆栈；迭代版用数组先收集再反转，是工程上更稳的选择。

// 递归版：打印从 s 到 v 的完整路径
function printPath(prev: number[], s: number, v: number): void {
  if (v === s) {
    console.log(s);
    return;
  }
  if (prev[v] === -1) {
    console.log(`顶点 ${v} 不可达`);
    return;
  }
  printPath(prev, s, prev[v]);
  console.log(` -> ${v}`);
}

// 迭代版：返回顶点数组，从起点到终点
function reconstructPath(
  prev: number[],
  s: number,
  t: number
): number[] {
  if (prev[t] === -1 && t !== s) return []; // 不可达
  const path: number[] = [];
  for (let cur = t; cur !== -1; cur = prev[cur]) {
    path.push(cur);
    if (cur === s) break; // 走到起点就停
  }
  path.reverse();
  return path;
}

递归版里有两个终止条件：一是回到了起点，二是遇到了 prev[v] === -1 且 v 不是起点——这表示 v 不可达，提前报错。迭代版的循环条件写成 cur !== -1，配合 cur === s 提前 break，双保险：既不会在正常路径上越走越远，也不会在异常数据（比如 prev 数组被破坏）里无限循环。注意 path.reverse() 之前数组是”终点到起点”的顺序，反转后才是”起点到终点”。

5.4 三条容易踩的还原细节

第一，起点自己的 prev 必须初始化为 -1（或者约定为自身）。如果初始化为 0 而起点恰好编号 0，迭代还原时 cur !== -1 永远成立，会无限循环。第二，如果存在多条同样最短的路径，prev 只记其中一条：松弛条件用严格小于 nd < dist[v]，所以第一次发现最短路径时记下 prev，之后等长路径不会再覆盖它。如果你希望”字典序最小”或”边数最少”的路径，需要额外处理并列情况（比如 nd === dist[v] 时按字典序比较 prev），这是一个经典的进阶扩展。第三，dist 的最终值和 prev 的指向必须一致：实现里两者在同一处 if 里更新，不要拆开写，否则可能出现”dist 更新了但 prev 没更新”或者反过来，造成还原结果和距离对不上——这种 bug 极难定位，因为单看数值都对，拼在一起就是错的。

5.5 还原的复杂度

还原本身的时间是 O(路径长度)，空间上 prev 数组 O(V)。和 O((V+E) log V) 的主算法相比，这几乎可以忽略不计。有趣的是，Dijkstra 一次运行得到的是一整棵最短路径树：从起点到任意顶点的最短路径都已经藏在 prev 里，不需要为每个目标重新跑一遍算法。这也是”单源最短路径”这个名字的含义——一次计算，服务所有终点。如果你需要的是”任意两点之间”的最短路径，那就要考虑多源 Floyd-Warshall 或者多次运行 Dijkstra 了，那是后话。

6 边界与 bug：把最容易翻车的地方全列出来

6.1 INF 到底该取多少

几乎所有最短路径算法都要面对同一个问题：起点到某个顶点的距离”还不知道”，用什么表示？最直觉的选择是”无穷大”。在 JavaScript / TypeScript 里，直接写 Infinity 是最省心的：Infinity + w 还是 Infinity，Infinity > Infinity 是 false，5 < Infinity 是 true，所有比较都符合直觉，几乎不可能出错。

但很多从 C++/Java 转过来的同学习惯写”很大的数”，比如 1e9 甚至 1 << 30。这在小型数据上没问题，一旦权重的规模逼近这个值，就会出大事：假设 INF = 10⁹，而某条边的权重也是 10⁹，松弛时 10⁹ + 10⁹ = 2×10⁹ > INF，一个”本来可以到达”的顶点会永远保持 INF；反过来，如果用了 Number.MAX_SAFE_INTEGER（约 9.007×10¹⁵）当 INF，MAX_SAFE_INTEGER + 1 会超出双精度浮点能精确表示的范围，出现”大数加小数结果不变”的静默错误。所以两条铁律：能写 Infinity 就写 Infinity；必须在有限整数里选 INF 时，要选”比任何可能路径总长都大得多、但加一次权重不会溢出”的值，比如 C++ 里 LLONG_MAX / 4，并确认最大答案不会超过它。

顺带一提，图论题里”权重 10⁹、顶点 10⁵”的组合很常见，最坏路径长度是 10¹⁴，32 位整数（上限约 2.1×10⁹）根本装不下。所以只要数据范围大，记得用 64 位整数或 BigInt，这也是”审题时先看数据范围”的又一例证。

6.2 重边与自环

重边指两个顶点之间存在多条平行边。比如从 1 到 2 既有权重 5 的边，又有权重 2 的边。Dijkstra 并不怕重边：松弛时 2 < 5，算法自然只会保留更小的那个，多余的边只是多一次无用的比较。但如果你的图用邻接矩阵存，就必须在建图时对重复边取最小值：graph[u][v] = min(graph[u][v], w)，否则后写入的边会覆盖先写入的，可能丢掉更短的路径。邻接表则无需处理，全部存进去即可，交给松弛判断。

自环指 u 到 u 自己的边。权重非负时，自环永远不可能改善 dist[u]（dist[u] + w ≥ dist[u]），所以它是纯噪音，不影响正确性，只会浪费一点时间。唯一要注意的是权重为 0 的自环：dist[u] + 0 < dist[u] 不成立，不会造成无限松弛，可以放心。负权自环就另当别论了——那意味着”绕一圈还能倒贴钱”，最短路径根本不存在，不过负权本身就不在 Dijkstra 的适用范围里。

6.3 起点不可达与图的非连通

图不连通时，从起点出发只能到达它所在的连通分量。Dijkstra 处理这种情况的方式很优雅：不可达的顶点从来没有被入堆过，它们的 dist 永远停在 INF，算法在堆空时自然结束。代码层面有三个注意点。第一，朴素版扫描时如果 u === -1（剩下的全是 INF），必须 break，否则循环会空转到结束——虽然结果不错，但浪费了时间，还可能让某些实现误把 -1 当成合法顶点去访问数组，直接越界崩溃。第二，路径还原时，目标顶点的 prev 还是初始值 -1，打印前要检查（5.3 节的代码已经处理）。第三，如果题目要求”对每个顶点都运行一次 Dijkstra”（比如多组询问），记得每次运行前把 dist 和 prev 重新初始化，这是最经典的”样例过了、提交全错”的元凶之一。

6.4 队列里的旧值：三种错误写法

懒惰删除的检查看似简单，但围绕它衍生出三种高频错误。第一种是完全忘了检查：弹出 (5, C) 时直接当有效条目处理，C 被重复松弛，小图没事，大图上每个顶点可能被处理多次，复杂度从 O(E log V) 退化到可能 O(E²) 甚至更糟，超时几乎必然。第二种是用 visited 数组替代检查：在弹出时 if (visited[u]) continue; visited[u] = true;，看起来更”严谨”，但注意弹出顺序里，visited 标记的是”已被最终处理”，这本身没错；真正的坑是有些人把 visited 的赋值放在入堆时，即第一次遇到 v 就标记，于是 v 的后续更短路径被拦在门外，答案错误。第三种是检查写反：if (d < dist[u]) continue，把有效的当成过时、过时的当成有效，算法结果完全随机。正确的检查只有一种语义：弹出的 d 不小于当前 dist[u] 时才处理，严格大于时跳过（d > dist[u] 跳过，d === dist[u] 处理）。

6.5 常见错误清单

下面把上面所有坑汇总成一张表，以后 debug 时可以直接对照：

这张表值得贴在显示器边上。说句实在话，上面每一行都是真实发生在生产代码和竞赛提交里的错误，尤其是”负权边”和”过时条目”这两行，几乎每个写 Dijkstra 的人都至少踩过一次。

6.6 如何验证你的实现

写完实现后，怎么知道它是对的？最可靠的办法是对拍（brute-force 对照）：随机生成一堆小图（顶点 ≤ 8，权重 0 到 10），用 Floyd-Warshall 或 BFS 暴力算出正确答案，再和你的 Dijkstra 输出逐点比较；一旦不一致，把图缩小到能手工分析的程度，用调试器逐步走查。对拍能覆盖大量组合，包括重边、自环、不可达、并列最短路径这些刁钻情况。另一个快速自检是”不变式检查”：算法结束后，对每条边 (u, v, w) 都验证 dist[v] ≤ dist[u] + w（三角不等式），以及 dist[s] === 0、所有可达顶点 dist 有限、不可达顶点 prev 为 -1。这些性质只要有一条不成立，实现就一定有 bug。

7 变体：双向、多源与网格地图

7.1 双向 Dijkstra：两头同时挖隧道

一句话原理：同时从起点和终点各跑一个 Dijkstra，两团”已确定区域”相向扩张，第一次碰头时，把两边的距离加起来，就得到了最短路径。直观上，只从起点挖一条隧道到终点，可能要挖到很大半径才知道方向对不对；两头同时挖，各自只挖到中间就能碰头，工作量大约减半。

graph LR
    S["起点"] --> A["前向区域"]
    A --> M["碰头点"]
    T["终点"] --> B["后向区域"]
    B --> M
    style M fill:#ffffaa

实现上的两个坑：一是后向 Dijkstra 要在反向图上跑（把每条边 (u, v) 反转成 (v, u)），因为从终点出发”走向”起点，等于在原图上从起点走向终点；二是终止条件不能写成”两边都确定同一个顶点就停”——正确且常用的做法是每次扩展完一边后，用当前两边的最小距离和更新答案，直到某一边的最小 dist 不小于当前答案。细节很容易讲偏，所以这里只给一句话结论：双向版本不改变复杂度量级，但常数大约减半，适合地图导航这种”一次只查一对点”的场景。

7.2 多源 Dijkstra：超级源点一根线全串起来

题目常常长这样：“城市里有 k 个消防站，求每个路口到最近消防站的距离。“如果对每个消防站分别跑一次 Dijkstra，复杂度乘 k，代价太高。更聪明的做法是引入一个虚拟的超级源点（super source），从它向每个消防站连一条权重为 0 的边，然后对这个新图只跑一次 Dijkstra：

graph LR
    SS["超级源点"] -->|"0"| F1["消防站 1"]
    SS -->|"0"| F2["消防站 2"]
    SS -->|"0"| F3["消防站 3"]
    F1 -->|"3"| R1["路口 A"]
    F2 -->|"2"| R1
    F3 -->|"5"| R2["路口 B"]

为什么这样可行？因为超级源点到任何顶点的最短路径，必然是”0 到某个消防站 + 从该消防站出发的最短路径”，而 Dijkstra 在多个 dist 同时为 0 的初始状态下，会按”所有源点一起扩张”的方式运行——第一次弹出消防站 1、消防站 2、消防站 3，然后它们各自往外松弛。实现上甚至不需要真的建超级源点，只要初始化时把所有源点的 dist 设为 0 并全部入堆，其他代码一行都不用改。这个”把多个起点合并成一个超级源点”的技巧，在图论里反复出现：多源 BFS、多源 Dijkstra、最小生成树的虚拟节点，都是同一招。

7.3 网格地图上的 Dijkstra：与寻路实验室联动

迷宫、地图、像素游戏里的寻路，本质都是在一个网格图上跑最短路径：每个格子是一个顶点，上下左右（四邻域）或加上斜对角（八邻域）是边，边的权重可以是”穿过这个格子的代价”。如果所有格子代价相同，BFS 就够了；但如果草地 1、沼泽 5、山地 10，或者不同道路有不同限速，Dijkstra 就闪亮登场了。

下面是一张 4×3 的网格示意，数字代表格子代价（进入该格的代价）：

graph LR
    A["起点 (0)"] -->|"1"| B["草地 (1)"]
    B -->|"5"| C["沼泽 (5)"]
    C -->|"1"| D["终点 (1)"]
    A -->|"5"| E["沼泽 (5)"]
    E -->|"1"| F["草地 (1)"]
    F -->|"1"| D
    style A fill:#aaddaa
    style D fill:#ffaaaa

虽然绕了一点，但”草地 → 沼泽 → 草地”总代价 7，而”草地 → 草地”如果存在会更便宜；Dijkstra 会在所有候选里挑出真正代价最小的那条。网格图的规模通常很大（1000×1000 就是 10⁶ 个顶点），但它是典型的稀疏图：每个格子最多连 4 或 8 个邻居，E ≈ 4V 或 8V，堆优化版的 O(E log V) 完全吃得消。写代码时注意两点：用二维坐标给顶点编号（id = r * cols + c），以及越界和障碍检查放在生成邻居时，别让算法跑到地图外面去。

老规矩，理论说完必须动手。下面这个寻路实验室支持你亲手在地图上画障碍、调权重，然后分别用 BFS、Dijkstra 和 A* 跑一跑，亲眼看看”已确定区域”是怎么一圈一圈往外扩张的。建议先复现 4.3 那张小图，再拖一个带沼泽的网格，观察 Dijkstra 是不是宁可绕远也不走贵路：

在实验室里观察时，你会看到一幅很特别的画面：已确定的格子并不是按”离起点几步”扩散，而是按”累计代价”扩散——代价低的草地先被染上颜色，沼泽虽然离起点更近，却可能迟迟不变色。这正是 Dijkstra 与 BFS 最直观的分野：BFS 的扩散圈是严格的同心圆，Dijkstra 的扩散圈则像被地形拉扯过的不规则等高线。如果再把某个格子的代价调成 0，你还能看到两个相邻格子几乎同时被确定的奇景——这再次提醒我们，0 权边只是让”确定顺序”出现并列，并不会破坏正确性。建议至少玩满三分钟：先画一堵墙，再铺一片沼泽，最后把终点放在对角，看看 Dijkstra 会不会为了避开沼泽绕一个看似很远的弧线。

7.4 其他值得一提的亲戚

如果边权只有 0 和 1 两种，可以用双端队列（0-1 BFS）把复杂度压到 O(V+E)：权重 0 的边头插，权重 1 的边尾插，比堆优化快一个 log。如果边权是 0 到 C 之间的小整数，可以用Dial 算法：准备 C+1 个桶，dist 每次最多增加 C，把顶点放进对应距离的桶里，用”当前桶指针 + 取模”实现近似 O(V+E+C) 的扫描。这两个都是”根据权重范围特化 Dijkstra”的经典例子，面试加分项，本文不展开。记住结论：数据范围决定数据结构，权重分布越特殊，能用的优化越廉价。

7.5 网格 Dijkstra 的完整实现

光说不练假把式，下面给一份可以直接套用的网格版 Dijkstra。地图是 H × W 的二维数组，cost[r][c] 表示进入格子 (r, c) 的代价，blocked[r][c] 为 true 表示障碍（不可进入）。我们让算法每次从当前格子向上下左右四个方向扩展，起点 (sr, sc)，终点 (tr, tc)。

function gridDijkstra(
  cost: number[][],
  blocked: boolean[][],
  sr: number,
  sc: number,
  tr: number,
  tc: number
): number {
  const H = cost.length;
  const W = cost[0].length;
  const INF = Infinity;
  const dist = Array.from({ length: H }, () => new Array<number>(W).fill(INF));
  dist[sr][sc] = 0;

  const heap = new MinHeap();
  heap.push([0, sr * W + sc]); // 二维坐标压成一维编号

  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  while (heap.data.length > 0) {
    const [d, id] = heap.pop()!;
    if (d > dist[Math.floor(id / W)][id % W]) continue; // 过时条目

    const r = Math.floor(id / W);
    const c = id % W;
    if (r === tr && c === tc) return d; // 终点已确定，提前返回

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      // 越界、障碍、自环都不生成
      if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
      if (blocked[nr][nc]) continue;
      const nd = d + cost[nr][nc];
      if (nd < dist[nr][nc]) {
        dist[nr][nc] = nd;
        heap.push([nd, nr * W + nc]);
      }
    }
  }
  return -1; // 终点不可达
}

这份实现有几个刻意为之的设计。坐标压成一维编号 id = r * W + c，是为了让堆元素保持 [dist, vertex] 的简单形态；反解坐标时 r = floor(id / W)、c = id % W，注意先除后取余的顺序。终点提前返回是安全的：当终点以有效条目弹出时，它的 dist 已经确定，不可能再被更短的路径更新，直接返回就是答案——这是 Dijkstra”确定即最终”性质带来的免费优化。越界和障碍检查统一放在邻居生成处，保证任何一步都不会访问非法格子，也避免给障碍格子初始化无穷大的边权。如果地图允许斜着走，把 dirs 换成八方向，并给斜边配上 √2 或自定义的对角代价即可；四条直边代价相同时，这就是经典的 A* 前置版本。

网格 Dijkstra 在真实世界里遍地都是：即时战略游戏里单位绕开树林和沼泽找路，扫地机器人规划穿过不同材质地面的清扫路线，配送系统在路网图上计算配送顺序——它们背后的核心，往往都是这一份代码的某个变体。顺带一提，互联网路由协议 OSPF 和 IS-IS 计算最短路径时用的也是 Dijkstra（路由领域叫 SPF，Shortest Path First），不过顶点是路由器、边是链路延迟，规模从网格换成上百万节点的自治域。下次你的手机地图给出”比预计晚 5 分钟”的路线时，可以默默想一下：这里面很可能就有一个 Dijkstra 在工作。

8 与 BFS 和 A* 的关系：三个算法一条血脉

8.1 BFS 是单位权重的 Dijkstra

如果你把第 4 篇的 BFS 和第 9 篇的 Dijkstra 放在一起看，会发现它们惊人地相似：都是初始化 dist、都是”取出当前最近的顶点、松弛邻居”、都是第一次确定就是最终答案。唯一的差别是取顶点的顺序：BFS 用队列，先进先出；Dijkstra 用优先队列，谁小谁先出。当所有边权都等于 1 时，Dijkstra 的堆里永远只有两种距离值：当前层 d 和下一层 d+1，而且所有 d 都排在 d+1 前面——堆退化成了严格的层次队列，这和 BFS 的队列行为完全一致。

所以可以理直气壮地说：BFS 是边权全为 1 时 Dijkstra 的特例，而 Dijkstra 是 BFS 在带权图上的推广。反过来看，BFS 的 O(V+E) 比 Dijkstra 的 O((V+E) log V) 快一个 log，因为单位权重下”找最小”不需要堆：队列本身就是有序的。这也解释了为什么刷题时看到”每条边代价相同”就一定要用 BFS，用 Dijkstra 属于杀鸡用牛刀，不会错但会慢。

flowchart LR
    BFS["BFS<br/>队列：先进先出<br/>适用：边权全为 1<br/>复杂度 O(V+E)"]
    DJ["Dijkstra<br/>优先队列：按 dist<br/>适用：边权非负<br/>复杂度 O((V+E) log V)"]
    BFS -- "边权全部 = 1 的特例" --> DJ
    DJ -- "加上启发式 h(v)" --> AST["A*<br/>按 f = g + h 排序<br/>目标明确时更快"]

还有一层容易被忽略的联系：BFS 的 visited 和 Dijkstra 的”确定”语义不同。BFS 里第一次出队的顶点，距离一定是最小的，所以 visited 一打上就可以永不再见；Dijkstra 里出队顺序由堆决定，同一个顶点可能因为更短路径再次入堆，必须用”弹出时检查 dist”来确认”这次才是最终值”。从”一锤定音”到”多锤定音”，本质就是权重从”整齐的 1”变成”参差不齐的任意非负数”后，我们必须付出的额外管理成本。

8.2 什么时候用哪一个

决策顺序其实只有三步。第一步，看是否有负权边：有，Dijkstra 直接出局，等第 10 篇的 Bellman-Ford。第二步，没有负权时看边权是否全相等：是，用 BFS（或者 0-1 BFS 如果只有 0 和 1）；否，用 Dijkstra。第三步，如果目标只有一个顶点、且你有关于”到终点大概多远”的信息，可以考虑 A*。记住这个顺序，绝大多数最短路径题就不会选错算法。

8.3 A*：加了启发式的 Dijkstra

一句话版本：A 就是 Dijkstra 换了一个排序键*——Dijkstra 按 g(v) = dist[v]（起点到 v 的已知代价）排序，A* 按 f(v) = g(v) + h(v) 排序，其中 h(v) 是”从 v 到终点的估计代价”（启发式函数）。当 h 恒为 0 时，A* 就退化成 Dijkstra；当 h 满足”可采纳”（不超过真实代价）且”一致”时，A* 依然能保证最优，却往往比 Dijkstra 少扩展很多无关方向的顶点，因为它”知道”终点大致在哪个方向。

用寻路来感受：Dijkstra 像是一个蒙着眼睛的人，只知道”我已经走了多远”，于是向四面八方平均地摸索；A* 像是戴了一副”终点在东北方向”的眼镜，虽然也会绕路，但大方向始终指着目标，所以整体更快。在游戏 AI、地图导航这类”知道终点坐标”的场景，A* 几乎是默认选择；而 Dijkstra 更适合”不知道终点、要算到所有顶点距离”的场景。本篇只做这一句话的铺垫，A* 的启发式设计、可采纳性证明、Octile 距离与欧氏距离的选择，我们留到专门的番外篇细讲。

8.4 一张图看三种算法的血脉

最后用一张示意图总结三者的扩张方式。同样的网格地图、同样的起点与终点，BFS 按”步数”扩散成圆形，Dijkstra 按”代价”扩散成不规则的圆形（贵的地形扩散得慢），A* 则带着方向感偏向终点：

graph TD
    S["起点"] -->|"BFS"| C1["等步数圆环"]
    S -->|"Dijkstra"| C2["等代价区域（地形越贵越慢）"]
    S -->|"A*"| C3["偏向终点的扇形"]
    C1 --> T["终点"]
    C2 --> T
    C3 --> T

三者共享同一个”松弛 + 按序扩展”的骨架，区别只是排序键：BFS 用入队顺序（等价于步数），Dijkstra 用已知代价，A* 用已知代价加估计代价。理解了这条血脉，你就同时理解了三类算法，也理解了为什么 Dijkstra 的正确性证明可以”移植”到 A* 上——只要启发式不撒谎（可采纳），证明里”替代路径不会更短”的论证就依然成立。

如果你对”启发式为什么能保证最优”已经产生好奇，可以现在就做一个思维实验：在一条直线上，起点在 0、终点在 100，所有格子代价相同。Dijkstra 会从 0 开始左右均匀扩散，直到碰到 100；而 A* 如果使用”到终点的直线距离”作为启发式，它会像装了磁铁一样直直地奔向终点，几乎不浪费任何一步。这个思维实验里藏着 A* 的全部秘密，也藏着”可采纳性”这三个字的分量。我们会在番外篇里把它拆开，到时候你会发现：原来证明 A* 最优的那一步，和今天证明 Dijkstra 的那一步，用的是同一种”反正替代路径不会更短”的语气。

9 实现要点速查表

9.1 一屏装下的核心模板

把全文浓缩成一份可以直接抄的模板，所有关键点都在注释里：

// 输入：graph[u] = [[v, w], ...]，起点 s，所有 w >= 0
function dijkstra(graph: number[][][], s: number): { dist: number[]; prev: number[] } {
  const n = graph.length;
  const dist = new Array<number>(n).fill(Infinity); // INF 用 Infinity，避免溢出
  const prev = new Array<number>(n).fill(-1);       // 起点 prev = -1，防死循环
  dist[s] = 0;

  const heap = new MinHeap();                       // 存 [dist, vertex]
  heap.push([0, s]);

  while (heap.data.length > 0) {
    const [d, u] = heap.pop()!;
    if (d > dist[u]) continue;                     // 懒惰删除：过时条目跳过
    for (const [v, w] of graph[u]) {
      const nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        prev[v] = u;                               // prev 和 dist 必须同步更新
        heap.push([nd, v]);                        // 重复入队没关系，旧条目会被跳过
      }
    }
  }
  return { dist, prev };
}

模板旁边配四句口诀：INF 要够大，弹出验旧值；松弛成功才入堆，prev 同步记。写题时照着这四句自查，能挡掉九成低级错误。

9.2 复杂度与数据范围速查

选型时先看数据范围：V 小用朴素版代码最稳；V 大、E 小用堆优化；边权只有 0/1 用双端队列；有负权直接换 Bellman-Ford。

9.3 面试高频追问与一句话答案

问：为什么 Dijkstra 不能处理负权边？ 答：正确性证明依赖”跨过分界线的后续边权重非负”，负权边可以让一条路径先走到远处再”倒贴”回来，破坏”当前 dist 最小的未确定顶点必然最优”的论断。

问：堆优化里为什么允许重复入队？ 答：因为标准的二叉堆不支持高效定位和修改任意元素；重复入队配合弹出时检查 d > dist[u] 跳过旧条目，实现简单且总插入次数 O(E)，不影响复杂度量级。

问：visited 数组在堆优化版里还需要吗？ 答：不需要。弹出时 d === dist[u] 的条目天然对应”首次以最终距离处理”，之后再无更短路径，因此不会有有效条目重复出现；显式 visited 反而容易写错时机。

问：所有边权都为 1 时为什么用 BFS？ 答：BFS 的队列天然按距离排序，找最小是 O(1)，总复杂度 O(V+E)，比堆优化少一个 log。

问：如何还原路径？ 答：松弛成功时记录 prev[v] = u，从终点沿 prev 回溯到起点再反转；起点 prev 置 -1，还原前先判断不可达。

问：起点到所有顶点都可达吗？ 答：不一定。不可达顶点的 dist 保持 INF、prev 保持 -1；朴素版要 break，还原要检查，堆优化版自然结束。

问：多个起点求最近距离怎么办？ 答：初始化时把所有起点 dist 置 0 全部入堆（等价于虚拟超级源点加 0 权边），一次 Dijkstra 完成。

9.4 自检清单

提交代码前，按这个清单过一遍：确认所有边权非负；确认 INF 不会溢出也不会误判；确认邻接矩阵重边取 min；确认弹出时做了过时条目检查；确认 prev 只在成功松弛时更新；确认多组数据时 dist、prev、堆都重新初始化；最后用 6.6 的对拍方法跑一组随机小图。全部通过，再提交，心里就踏实了。

9.5 学习方法与工程心法

先把故事补完。1956 年，年轻的 Edsger Dijkstra 在阿姆斯特丹一家咖啡馆里，为了”找出荷兰两个城市之间最短的铁路连接”冥思苦想，据说用了二十分钟设计出这个算法，甚至没有纸笔，直接在心里完成。1959 年他发表论文《A Note on Two Problems in Connexion with Graphs》，原文里并没有堆——那个年代人们用的是数组扫描；优先队列优化是后来计算机科学家们逐步改进的结果。这个历史细节值得记住：算法的第一版往往朴素，优化的方向往往来自对瓶颈的清醒认识。Dijkstra 发现瓶颈是”找最小”，于是后来的优化全部围绕这个操作展开，这和我们 3.4 节的结论一模一样。

学习这个算法，最有效的路径是三遍训练法。第一遍，找一张五六个顶点的图，不写代码，用纸笔完整手推一遍，把每一轮的 dist 变化和堆内容都写下来，就像 4.9 节那样；第二遍，合上所有参考，凭记忆把朴素版和堆优化版各默写一遍，写完后对照模板，把记错的每一处标记出来；第三遍，随机生成小图和正确答案对拍，直到连续十组数据全部一致。三遍走完，Dijkstra 就会从”看过”变成”会写”，从”会写”变成”写不错”。

工程上还有几条心法，来自真实系统的经验。第一，图特别大时，邻接表不要用”二维数组套数组”：每个顶点一个动态数组虽然好写，但上百万顶点会带来大量小对象和指针跳转，缓存命中率差；竞赛和底层库里常用”链式前向星”——用三个平行数组 head、to、w、next 把边串起来，内存紧凑、遍历快。第二，只问单点最短距离时，可以在终点被弹出时提前返回（7.5 的网格代码已经示范），这往往能把平均耗时砍掉一大截，尤其当终点离起点很近时。第三，多组询问共用同一张图时，考虑把结果缓存起来：如果询问的起点固定，一次 Dijkstra 的结果可以回答所有终点；如果起点也多变，可以按”离线处理 + 排序”的技巧分摊代价，这些都属于”图算法工程”的进阶话题。第四，浮点权重要谨慎：地图导航里可能出现 0.1 + 0.2 ≠ 0.3 的经典问题，比较松弛条件时给一个极小的 epsilon，或者干脆把所有权重乘以 10^k 转成整数，能省掉一大类”样例过了、线上随机挂”的诡异 bug。

最后，把整篇文章浓缩成四句话，当作你的算法座右铭：正确性靠非负权，效率靠堆和懒惰删除，完整性靠 prev 同步记录，鲁棒性靠边界条件全检查。这四句话对应着四个章节，也对应着四类面试追问。背下这四句，Dijkstra 就真的属于你了。

9.6 经典题目与套路

光会模板还不够，真题里 Dijkstra 从来不裸奔，它总是披着各种外衣出现。下面总结五个最高频的套路，遇到类似的题可以直接对号入座。

套路一：求”从起点到所有顶点的最远最短距离”。 典型题是”网络延迟时间”：给定 n 个网络节点、信号传播耗时和起点，问信号多久能到达所有节点。解法就是跑一遍 Dijkstra，然后取 dist 数组的最大值；如果存在某个 dist 还是 INF，说明有节点收不到信号，返回 -1。这类题的变体还包括”所有城市到最近加油站的距离”——把加油站当多源一起入堆即可，正是 7.2 节的超级源点。

套路二：求”概率最大的路径”。 给定每条边上的成功概率，问从起点到终点概率最高的走法。表面上看 Dijkstra 求的是”最小和”，这里是”最大乘积”，但用对数变换：最大化 p1 × p2 × ... 等价于最大化 log(p1) + log(p2) + ...，而每个概率都不超过 1，-log(p) 一定非负，于是”最大化乘积”就变成了”最小化 -log 之和”的标准 Dijkstra。如果你不想引入浮点和 log，也可以直接把堆的比较器改成”取乘积最大”，只要权重乘法单调、结果在 [0,1] 区间，Dijkstra 的贪心性质依然成立——不过面试时说出 log 变换的原理会更显功力。

套路三：限制中转次数的最短路。 题目如果写着”最多经过 k 站""最多转机 k 次”，Dijkstra 就不能直接用了，因为”限制步数”会破坏”确定即最终”的前提——一条距离更远但步数更少的路径，可能在步数限制下才是唯一合法的解。这类题的正解是 Bellman-Ford 的 k 轮松弛版本（或者带状态的分层图），正好是第 10 篇要讲的内容。看到 k 步限制，第一时间想起 Bellman-Ford，而不是硬套 Dijkstra，这是审题能力的体现。

套路四：要输出完整路线。 题目问”给出从 A 到 B 的具体路径”时，别慌，算法部分一行不用改，只要在松弛成功时维护 prev，最后用 5.3 节的 reconstructPath 还原即可。如果要求”字典序最小”或”经过的顶点数最少”的并列最优路径，需要把松弛条件从严格小于改成”小于或等于且新路径更符合附加要求”，再配合 prev 比较；这类扩展题的陷阱在于，附加条件不同，比较逻辑就要跟着变，不能写死。

套路五：图很大、只问一对点。 当 V 到百万级、只关心起点到终点时，优先考虑 7.5 节的”终点弹出即返回”优化，条件允许再用双向 Dijkstra（7.1 节）进一步减半搜索区域。如果图是静态的、查询非常频繁，甚至可以提前把图建成索引、用 A* 或 CH（Contraction Hierarchies）这类工业级算法——那就是地图导航公司的核心机密了，等你把这篇吃透再往前走。

刷题时如果遇到以上任意一种包装，先别急着写代码，花三十秒做三件事：确认边权非负；确认数据范围决定用朴素版还是堆优化版；确认题目要的是距离、路径还是别的附加条件。这三件事想清楚，Dijkstra 就只是你的搬运工，而不是你的绊脚石。

9.7 术语对照表

最后附一张术语表，中英文、一句话解释和正文位置一次配齐，方便你复习时快速定位：

这张表和 6.5 的 bug 清单一样，建议收藏起来。下次面试或刷题前扫一眼，相当于把整篇文章的索引过了一遍，比从头再读一遍高效得多。

10 自测题：七道题检验是否真的吃透

while (heap.size() > 0) {
  const [d, u] = heap.pop();
  if (seen[u]) continue;   // 第一次看到就标记
  seen[u] = true;
  for (const [v, w] of graph[u]) {
    if (!seen[v] && d + w < dist[v]) {
      dist[v] = d + w;
      heap.push([dist[v], v]);
    }
  }
}

11 下一篇预告：Bellman-Ford 与负环

到这儿，Dijkstra 已经被我们拆得明明白白：正确性直觉、朴素实现、堆优化、懒惰删除、路径还原、边界 bug、变体家族，以及和 BFS、A* 的血脉关系。但你心里一定还留着一个疙瘩：负权边怎么办？

下一篇《图系列第 10 篇：Bellman-Ford 与负环》就来解决这个问题。我们会看到 Bellman-Ford 用最笨也最稳的办法——把全图松弛 V−1 轮——换来对负权边的完全容忍；会学到”第 V 轮还能松弛就说明存在负环”这个漂亮的判据；会讨论负环为什么让”最短路径”这个概念本身失去意义；还会介绍 SPFA 这个”队列加速版”以及它的复杂度和争议。等你读完第 10 篇，再把今天这篇拿出来对照，你会惊喜地发现：Dijkstra 的每一条边界，都是 Bellman-Ford 的用武之地；两个算法放在一起，才是最短路径问题的完整拼图。

图系列走到第 9 篇，我们已经攒下了存储、遍历、拓扑排序、无权最短路径和带权非负最短路径五件套。下一站，补齐”负权”这块最后的短板，然后我们就可以去挑战那些最精彩的应用了：差分约束、网络流、以及真实地图上的大规模寻路。咱们第 10 篇见。