图 · 单步演示
Dijkstra 最短路
求一个起点到其余各顶点的最短距离。每一步从还没确定的顶点里挑 dist 最小的一个，认定它的距离不会再变，再用它去更新邻居的 dist。要求所有边权都不小于 0。
待定且已可达（dist）A(0)
确定顺序（空）
步 001 / 032起点 A 的 dist 设为 0，其余都是 ∞。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
dist[*] ← ∞；dist[s] ← 0while 还有未确定的顶点u ← 未确定顶点中 dist 最小的；若 dist[u] = ∞ 则结束确定 ufor (v, w) in u 的邻边，v 未确定if dist[u] + w < dist[v]dist[v] ← dist[u] + w；prev[v] ← u
变量
| u | — |
|---|---|
| dist | A:0 B:∞ C:∞ D:∞ E:∞ F:∞ |
| 已确定 | [] |
复杂度
| 最好情况 | O(V²) |
|---|---|
| 平均情况 | O(V²) |
| 最坏情况 | O(V²) |
| 额外空间 | O(V) |
本演示每轮扫一遍所有顶点找最小值，共 V 轮，所以是 O(V²)，适合稠密图。换成二叉堆维护待定顶点，可以做到 O((V + E) log V)。
要点
- 「确定」的依据：所有边权非负时，从已确定区域往外走只会让距离变大，当前最小的 dist 不可能再被别的路径改小。
- prev 数组记下每个顶点是从谁更新来的，倒着追回去就是路径。
常见错误
有负权边时，已经「确定」的顶点之后还可能被改小，结果会出错。本演示遇到负权会直接拒绝。