形式陈述

给定带非负边权 $w(e)\ge 0$ 的有向或无向图和源点 $s$，Dijkstra 算法维护暂定距离 $d[v]$。初始化 $d[s]=0$、其余为无穷；反复抽取未确定顶点中 $d$ 最小者 $u$，将其永久确定，并对每条出边执行松弛

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

正确性关键是：非负边权保证任何经未确定顶点绕行到 $u$ 的路径都不可能更短。二叉堆实现时间为 $O((|V|+|E|)\log |V|)$。

直觉

像从源点向外扩张一个按距离排序的波前；最靠近波前的未确定点一旦被取出，未来只能再加非负长度，无法从更远处回来改短它。

例子与边界

边 $s\to a$ 权 2、$s\to b$ 权 5、$a\to b$ 权 1 时，先确定 a 并把 b 改为 3。若存在负边 $s\to b=2$、$s\to a=5$、$a\to b=-10$，b 可能过早被确定，算法失败；即使没有负环也如此。不可达顶点保持无穷。零权边允许。负权图应使用 Bellman–Ford 等算法。

推论与应用

Dijkstra 用于路由、地图、网络延迟和作为 Johnson 全源最短路的子程序。数据结构选择决定稠密/稀疏图上的实际复杂度。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 22, single-source shortest paths with nonnegative weights。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 4, Dijkstra algorithm and greedy proof。