Dijkstra 算法 | Codeboy's Blog

形式陈述

给定有限有向或无向图、源点 $s$ ，并假设每条边权 $w(e)\ge0$ ，Dijkstra 算法维护暂定距离 $d[v]$ 与已结算集合 $S$ 。初始化 $d[s]=0$ 、其余为 $+\infty$ ；反复从未结算顶点中取 $d$ 最小者 $u$ 加入 $S$ ，再对每条出边执行松弛

d[v]\leftarrow\min\{d[v],d[u]+w(u,v)\}.

每个有限 $d[v]$ 都是一条已发现 $s\leadsto v$ 路的权重，所以 $d[v]\ge\delta(s,v)$ 。归纳假设 $S$ 中距离均已正确。取最小候选 $u$ ，在一条最短 $s\leadsto u$ 路上令 $y$ 为第一个不在 $S$ 的顶点， $x$ 为它的前驱。松弛 $x\to y$ 后已有 $d[y]=\delta(s,y)$ ；非负权又给出 $\delta(s,y)\le\delta(s,u)$ 。由最小键选择，

\delta(s,u)\le d[u]\le d[y]=\delta(s,y)\le\delta(s,u),

故 $d[u]=\delta(s,u)$ ，可以永久结算。这个割论证同时解释了非负权假设出现在哪里。

算法以按键取最小值的优先队列实现。设 $n=|V|$ 、 $m=|E|$ ，并假设邻接表、精确权重加法与比较在单位成本 RAM 中计费：

二叉堆加顶点句柄执行 $n$ 次 extract-min、至多 $m$ 次 decrease-key，最坏时间 $O((n+m)\log n)$ 、额外空间 $O(n)$ ；
不支持 decrease-key 时可插入新记录并惰性跳过旧记录，至多有 $O(m)$ 个堆项，时间 $O((n+m)\log(n+m))$ 、空间 $O(n+m)$ ；
Fibonacci 堆把理论界改为 $O(m+n\log n)$ 摊还时间；
邻接矩阵配合线性扫描最小未结算键，确定性最坏时间为 $\Theta(n^2)$ 、额外空间 $O(n)$ （不计矩阵本身）。

直觉

Dijkstra 把已结算区看成从源点扩张的距离球。堆中每个键代表一条从球内跨出到该顶点的最佳已知路线；取最小键就是选择下一层边界。由于边权不为负，任何尚未进入球的绕行都不可能先走得更远、再以负代价回来改短已结算点。

松弛负责生成与更新候选，贪心选择负责宣布一个候选不再变化。只做松弛而没有最小键次序，是另一类标签修正算法；只取最小键而不扫描出边，也无法把正确距离传播给后继。

Dijkstra 取出最小候选、结算并松弛一条边 — Dijkstra 的取最小与松弛

例子与边界

在边

s\to a:2,\qquad s\to b:5,\qquad a\to b:1,\qquad a\to t:4,\qquad b\to t:1

上，结算 $s$ 后暂定 $(d[a],d[b])=(2,5)$ ；结算 $a$ 后变为 $d[b]=3,d[t]=6$ ；结算 $b$ 后又把 $d[t]$ 降为 $4$ 。父指针恢复路径 $s\to a\to b\to t$ ，其权重 $2+1+1=4$ 。

负边反例不需要负圈。取

s\to b:1,\quad s\to a:2,\quad a\to b:-3,\quad b\to t:2.

算法先结算 $b$ 并令 $d[t]=3$ ；等到结算 $a$ ，真正到 $b$ 的成本才降为 $-1$ 。标准算法不会重新展开已结算的 $b$ ，于是返回 $d[t]=3$ ，而路径 $s\to a\to b\to t$ 的权重是 $1$ 。这表明非负性是足够且可局部检查的前提；“图中没有负圈”仍不足以使用本算法。

负权图可改用Bellman–Ford 算法。零权边和零权圈不破坏正确性，但可能产生多个相同键；平局以任意顺序结算都安全。不可达顶点始终为 $+\infty$ ，实现可在最小键已为无穷时停止。平行边逐条松弛即可，同方向只保留最小权边也不改变距离；非负自环不会改进任何估计。

推论与应用

Dijkstra 解决非负权最短路问题；图表示决定能否只扫描现有边，队列实现决定最小键与减键成本。若只查询一个目标 $t$ ，当 $t$ 被取出并结算时即可停止；在此之前仅仅“发现 $t$ ”不构成最优性证书。

Johnson 算法先用势函数把含负边、无负圈的图重赋为非负权，再逐源调用 Dijkstra。A*在一致启发函数下等价于对约化非负权运行同一结算逻辑；令启发函数 $h\equiv0$ ，A* 恰好退化为 Dijkstra，因此本算法是它的一个特例。

参考资料

Edsger W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik 1, 1959, pp. 269–271。
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§22.3。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§4.4。

形式陈述 ​

反向链接

形式陈述