Dijkstra 算法
Dijkstra 求非负边权图中，从一个源点到所有其他顶点的最短距离。它维护暂定距离，每次从优先队列取出距离最小的未确定顶点，确定其距离，再松弛出边。
可以把边长看成连接图钉的绳长：从源点提起，近处图钉先离开桌面。算法用距离计算表达这种由近及远的顺序。关键条件是所有边权非负，后续路径只能增加成本，不能绕回来降低已经确定的最小距离。有负边时应考虑 Bellman-Ford；本课负边预设会展示错误发生的位置。
Dijkstra 如何工作
状态包括 dist、visited 和优先队列。源点距离为 0，其余为 ∞；visited 记录距离已确定的顶点；队列存储 (distance, node)，每次取最小值。
取出并确定。 弹出未访问顶点 u 后，标记已访问。此时 dist[u] 就是真实最短距离：通往其他未访问顶点的路线仍需越过距离不小于它的搜索前沿，而非负边不能再把成本减小。
松弛。 对边 u → v、权重 w，比较 dist[u] + w < dist[v]。若成立，更新 dist[v]，将 u 记为前驱，把新 (dist[v], v) 入队。若不成立，保持原值。
普通二叉堆的懒更新不查找并修改旧条目，而是插入更小的新条目。旧条目成为过期项，之后弹出时若顶点已在 visited，直接丢弃。它们是省去 decrease-key 索引维护的代价。
Dijkstra 逐步演示
默认加权有向图有 A–F 六个顶点，从 A 开始。边为 A→B (2)、A→C (5)、B→C (1)、B→D (7)、C→D (2)、D→E (1)、D→F (3)、E→F (2)。
- 初始化
dist[A]=0，其余为 ∞。队列[(0,A)]。 - 确定 A。松弛后 B 为 2，C 为 5。队列
[(2,B), (5,C)]。 - 确定 B，距离 2。
B→C提供2+1=3，把 C 从 5 降到 3；两条边A→B→C比一条边A→C更便宜，这是只计边数的 BFS 无法判断的。B→D将 D 设为 9。队列[(3,C), (5,C), (9,D)]，C 同时有新旧条目。 - 确定 C，距离 3。
C→D提供3+2=5，将 D 从 9 降为 5。队列[(5,C), (5,D), (9,D)]。 - 弹出
(5,C)，C 已确定，丢弃。队列[(5,D), (9,D)]。 - 确定 D，距离 5。松弛后 E 为 6，F 为 8。队列
[(6,E), (8,F), (9,D)]。 - 确定 E，距离 6。
E→F提供6+2=8，等于旧值，不更新。队列[(8,F), (9,D)]。 - 确定 F，距离 8，没有出边。队列
[(9,D)]。 - 弹出过期的
(9,D)并丢弃，队列空，结束。
最终距离为 A:0, B:2, C:3, D:5, E:6, F:8。确定顺序 A、B、C、D、E、F 对应距离 0、2、3、5、6、8，始终非递减。弹出 C 的 3 时，其余条目都至少为 3，非负边不会把后续路径降到它之下。
时间与空间复杂度
| 操作 | 次数 | 单次成本 | 总成本 |
|---|---|---|---|
| 二叉堆入队、出队 | O(V + E) | O(log V) | O((V + E) log V) |
| 松弛检查 | O(E) | O(1) | O(E) |
在本课这种简单图模型下，时间为 O((V + E) log V)，空间为 O(V + E)。每条边最多触发一次成功松弛，懒更新堆累计插入 O(E) 个条目；dist 和 visited 占 O(V)，堆占 O(E)。严格说堆操作依赖堆大小，为 O(log E)，简单图中可写成 O(log V)。
使用支持 decrease-key 的 Fibonacci 堆，理论时间可达到 O(E + V log V)，但维护和常数成本可能抵消收益。
边界情况
- 不可达顶点不入队、不确定，距离保持 ∞。
- 单个顶点以 0 入队，弹出并确定后结束。
- 距离相同时，先确定哪一个都不改变最终距离。本课按顶点标识打破平局，以固定轨迹。
- 零权边合法，顶点可连续以相同距离确定。
- 只求一个目标时，可在该目标被确定的瞬间停止，其余队列无需处理。
常见错误
- 用于负权图。 负边预设先把 B 确定为 2，之后
C→B权重 −5 才给出A→C→B的成本 −2。B 已锁定，改进被拒绝，最终报告 2 而非 −2，画面用红环标出 B。调整队列不能恢复已失效的前提。 - 试图修改已确定距离。 在正确的非负权模型中不应出现严格改进；若出现，应检查边权和实现，而非继续使用原来的确定性证明。
- 用 BFS 比较不同边权。 BFS 最小化边数，只有各边成本相同等条件下才等价于最低总成本。
- 漏掉过期检查。
if u in visited: continue防止通过旧条目重复处理顶点，保持本课懒删除实现的逻辑。 - 入队就标记确定。 入队只表示发现路线，弹出成为当前最小候选时才能确定。
展示中的简化
优先队列画成排序行，便于阅读；真实二叉堆只保证堆顶最小，其余部分有堆序而非全序。展示代码跳过已确定邻居的松弛（v not in visited）。其他实现可省略这项检查并依靠弹出时的过期检查，在非负权下距离一致。更改负权处理方式需要重新证明，不能继续使用 Dijkstra 的原有保证。