Dijkstra 算法 | ReConcept Lab

问题从哪里来

当每条边都只算一步时，BFS 很好用。但道路、网络连接或选择常常有不同代价。现在问题不再是”几条边”，而是”从 A 出发的最小总代价是多少”。

地图现在带权：一条边可能比两条边更贵。Dijkstra 开始前的带权图。

追踪start

堆A:0

当前-

边-

规则权重是明确标签；视觉长度不是代价。

从 A 出发的最终距离
节点	dist	parent
A	0	-
B	3	C
C	1	A
D	4	B
E	7	D
F	8	E

第一个朴素想法

仍然尝试 BFS。它会从 A 直接发现 B，并保留一条边的路径 A -> B，即使 A -> C -> B 的总代价更低。

BFS 会先保留 A-B，但 A-C-B 代价更低。BFS 在带权图中的失败点。

追踪relax-A-B

堆B:4

当前A

边A-B

规则按边数第一次发现不等于总代价最低。

它为什么会痛

在无权图中，第一次发现就足够。在带权图中，按边数第一次发现可能冻结错误的父节点或代价。

A-B 代价为 4；A-C-B 代价为 3。到 B 的路线代价对比。

追踪relax-C-B

堆B:3, B:4*

当前C

边C-B

规则比较总代价，而不是边数。

核心发明

Dijkstra 保留 BFS 的前沿思想，但前沿按暂定总代价排序。普通队列弹出最早进入的条目；优先队列（priority queue）弹出标签最小的条目。

优先队列取代先进先出顺序。C 更新 B 后的暂定距离表和堆。

追踪relax-C-B

堆B:3, B:4*

当前C

边C-B

规则优先级来自最小暂定距离。

松弛脚手架

松弛（relaxation）会问：经过当前节点能不能改善某个邻居？对于 C -> B，旧的 dist[B] 是 4，而 dist[C] + 2 = 3，所以 B 被改善，父节点改为 C。

C -> B 把 B 从 4 改善到 3，并把父节点改为 C。从 C 到 B 的松弛。

追踪relax-C-B

堆B:3, B:4*

当前C

边C-B

规则当候选值小于当前暂定距离时更新。

互动可视化

Dijkstra 追踪

把 A 初始化为距离 0；其他节点都是 Infinity。

当前-

当前边-

弹出-

已确定-

优先队列:A:0

为便于阅读而排序展示；真实堆只保证下一次取出最小项。

节点	距离	父节点
A	0	-
B	Infinity	-
C	Infinity	-
D	Infinity	-
E	Infinity	-
F	Infinity	-

形式化版本

对于每条边 (u, v)，Dijkstra 要求 w(u, v) >= 0。算法维护暂定距离 dist[v]、父节点 parent[v]、已确定节点集合，以及候选条目的优先队列。

形式化状态命名当前节点、当前边、候选值、堆和表格。扫描 D-E 时的 Dijkstra 形式化状态。

追踪scan-D-E

堆D:6*, E:9

当前D

边D-E

规则candidate = dist[current] + weight(current, neighbor)。

算法会计算所有可达节点的距离。后面检查 F 只是为了演示如何恢复一条路径，并不是说 Dijkstra 只能处理单个目标。

实现草图

function dijkstra(start: NodeId, graph: WeightedGraph) {
  const dist = new Map<NodeId, number>([[start, 0]]);
  const parent = new Map<NodeId, NodeId>();
  const settled = new Set<NodeId>();
  const heap = new MinHeap([{ node: start, distance: 0 }]);

  while (!heap.isEmpty()) {
    const entry = heap.popMin();
    if (entry.distance !== dist.get(entry.node) || settled.has(entry.node)) continue;

    settled.add(entry.node);
    for (const edge of graph[entry.node]) {
      const candidate = entry.distance + edge.weight;
      if (settled.has(edge.to)) continue;
      if (candidate < (dist.get(edge.to) ?? Infinity)) {
        dist.set(edge.to, candidate);
        parent.set(edge.to, entry.node);
        heap.push({ node: edge.to, distance: candidate });
      }
    }
  }

  return { dist, parent };
}

允许重复的堆条目。过期条目保护会跳过那些距离已经不等于当前最佳 dist[node] 的旧条目。

过期条目保护让重复堆条目更简单。过期跳过的代码到追踪映射。

追踪skip-stale-B-4

堆D:4, D:6*, E:9

当前B

边-

规则弹出的条目过期时跳过。

正确性直觉

在确定 B 之前，堆中最小项是 (B, 3)，其他暂定条目至少是 4。任何经过未确定节点到达 B 的隐藏替代路径，都必须先以 >= 4 的代价到达前沿，再加上一条非负边。它不可能小于 3。

确定 B 之前，堆最小项是 (B,3)；其他暂定项至少为 4。确定 B 前的正确性前沿。

追踪pop-B-3

堆B:4*, D:6, E:9

当前B

边-

规则任何隐藏替代路径都先从代价 >= 4 的前沿开始，再加非负边。

复杂度

使用二叉堆并允许重复条目时，每次成功松弛都会压入一个堆条目。每个堆操作需要 O(log V)，所以常见界是 O((V + E) log V)。

9 条无向边变成 18 次有向邻居扫描；重复入堆产生过期跳过。该例子的 Dijkstra 复杂度计数。

追踪done

堆-

当前-

边-

规则边扫描加堆操作得到 O((V + E) log V)。

这个例子中 9 条无向边产生 18 次邻居扫描、10 次入堆和 4 次过期跳过。

常见混淆

这里为了阅读把优先队列按顺序展示，但真实堆只保证下一次取出的最小项。旧条目可以留在堆里，并在之后变成过期条目。

旧的 (B,4) 过期了，因为 dist[B] 已经是 3。B 的过期优先队列条目。

追踪skip-stale-B-4

堆D:4, D:6*, E:9

当前B

边-

规则为便于阅读而排序展示；真实堆只保证下一个最小项。

堆条目为了阅读按序展示；真实堆只保证下一次取出最小项。

零权边是允许的。相同暂定距离可以用确定的显示顺序处理，但平局顺序不是 Dijkstra 正确性的来源。

不可达节点会保持距离 Infinity，且没有父节点。

孤立的 G 会保持 dist[G] = Infinity，且没有父节点。不可达孤立节点情况。

追踪done

堆-

当前-

边-

规则不可达节点保持 Infinity，且永远不进入堆。

如果加入孤立的 G，它会保持 dist[G] = Infinity、parent[G] = 无，并且永远不会进入堆。

负边会破坏”已确定就是最终”这个承诺。这个警示使用单独的有向图，不是主无向地图。

后来的负边与已确定状态的承诺矛盾。Dijkstra 的有向负边警示。

警示步骤negative-contradiction

候选值1

规则这是有向警示变体，不是主地图。

路径恢复

距离告诉总代价。父节点指针可以从目标反向追踪，再反转结果，从而恢复具体路径。

F 恢复出的路径是 A -> C -> B -> D -> E -> F。从 F 恢复路径。

追踪done

堆-

当前-

边-

规则沿父节点箭头向后追踪，然后反转结果。

从 A 出发的最终距离
节点	dist	parent
A	0	-
B	3	C
C	1	A
D	4	B
E	7	D
F	8	E

从 F 沿父节点反向追踪：F <- E <- D <- B <- C <- A；反转后得到 A -> C -> B -> D -> E -> F。

图谱连接

Dijkstra 推广了 BFS 的前沿和距离思想。BFS 使用先进先出，是因为每条边代价相同；Dijkstra 使用暂定总代价，是因为边可以有不同的非负权重。

预测练习

A 确定之后，堆中哪个条目应该下一个弹出？
为什么 C -> B 会更新 B，但之后过期的 (B, 4) 会被跳过？
根据父节点表恢复到 F 的路径。
在有向负边警示中，哪个”已确定状态”的承诺失效了？

图谱连接 : Dijkstra 算法