01先从一个问题出发
道路耗时不一样时,最少经过道路不代表最早到达。需要按累计代价扩展。
无向带权边 0–1:4、0–2:2、2–1:1、1–3:5、2–3:8;节点 4 孤立。
发现一条路,不代表它已经最短
0 到 1 有权重 4 的直接边,到 2 有权重 2 的边,2 到 1 权重为 1。首次看到 1 时只能说存在一条长度 4 的路径;经过 2 后可以改成 3。与无权 BFS 不同,不能在首次发现时就永久固定答案。
维护 dist[v]:当前已经发现的到 v 的最小代价。起点为 0,其他为 ∞。每轮从尚未确定的节点中选 dist 最小者 u,将它确定,再用它改善邻居:若 dist[u]+w(u,v)<dist[v],就更新 dist[v]。这个改善叫松弛。
为什么最小的临时值可以最终确定
想象另有一条更短的路径到 u。沿这条路径从起点走,找到第一个尚未确定的节点 x:它的前驱已经确定,所以那条边已经有机会松弛 x。于是 x 的临时距离不会大于这条更短路径到 x 的前缀代价。
因为后续边权非负,从 x 继续走到 u 不会让总代价变小。这样 x 的临时距离应小于当前 dist[u],却又没有优先被选中,产生矛盾。所以当前最小的 u 可以确定。这段论证正是负权边会破坏的地方。
02最直接的办法,为什么慢?
枚举所有简单路径计算代价。
大量路径共享相同前缀,候选数量可呈阶乘级增长。
03一步步,推导出优化思路
保存每个节点的临时距离
给每个节点维护当前已知最小距离 dist。
确定当前最近的候选
非负边权保证:未确定节点中 dist 最小的节点,距离可以最终确定。
沿邻边松弛,再选下一点
用这个节点尝试松弛每条出边,再选择下一个最近节点。
已确定节点的距离就是最短路;未确定节点记录目前已发现路径的最小代价。
拿一个小输入,逐步手算
无向带权边 0–1:4、0–2:2、2–1:1、1–3:5、2–3:8;节点 4 孤立。
| 确定节点 | dist[0..4] | 本轮改善 |
|---|---|---|
| 初始化 | [0,∞,∞,∞,∞] | 只有起点已知 |
| 0,距离 0 | [0,4,2,∞,∞] | 发现 1、2 |
| 2,距离 2 | [0,3,2,10,∞] | 1 从 4 改为 3,3 先设为 10 |
| 1,距离 3 | [0,3,2,8,∞] | 3 从 10 改为 8 |
| 3,距离 8 | [0,3,2,8,∞] | 无更短候选 |
| 剩余最小为 ∞ | [0,3,2,8,∞] | 停止;4 不可达 |
到 3 的最佳路线是 0→2→1→3,代价 2+1+5=8。经过的边更多,却比 0→2→3 的 10 更便宜。
不变量必须同时覆盖两类节点
- dist 的每个有限值都对应一条实际发现的路径;已确定节点的值为真实最短距离。起点在非负图中距离为 0。
- 选择未确定节点中临时距离最小者。通过第一个未确定节点的反证论证,它不可能再被其他非负后缀改得更短。
- 松弛其邻边加入新的候选路径,保持临时值的含义。重复直至没有可达的未确定节点,剩余 ∞ 表示不可达。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
源点为 0。其距离为 0,其余暂为无穷大。所有边权必须非负。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
distance[start] = 0- 起点到自己走空路径,代价 0。其他节点初始应为无穷大,不能用 0 表示未知。
node = -1- 每轮重新寻找未确定节点中的最小值;本课用线性扫描,便于观察选择过程。
visited.add(node)- 这里的 visited 表示最终确定。它与 BFS 中首次发现即标记的含义不同,不能照搬标记时机。
distance[node] + weight < distance[next]- 候选必须是『到当前节点的总代价+这条边权』,不能只拿边权与 dist[next] 比较。
05复杂度,来自具体的工作量
本课采用直观的线性选最小值:V 次选择,每次扫描 V 个节点,加上所有边的松弛。二叉堆版本可改善到 O((V+E)log V)。
dist、visited 和候选节点集合都是 O(V),不含输入邻接表。
把工作量具体数出来
本课每轮扫描 V 个节点选最小值,最多 V 轮,选择部分 O(V²);所有邻边松弛合计 O(E),总时间 O(V²+E)。
二叉堆可把选择过程改进为优先队列。对常见简单图实现,常写 O((V+E)log V);需要处理堆中距离过期的候选,不能只把容器名字替换一下。
本版 dist 与已确定集合各 O(V),辅助空间 O(V),不含输入邻接表。返回的是距离数组,恢复路径需额外保存成功松弛时的前驱。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
不能处理负权
负权会破坏已确定距离不会变小的证明,应考虑 Bellman–Ford。
不可达不是 0
不可达节点距离保持为 ∞。
负边会让已确定距离重新变小
考虑有向边 0→1:2、0→2:5、2→1:−4、1→3:1。按临时最小值先确定 1 和 3 后,才发现经过 2 可把 1 改到 1,真正到 3 的代价应为 2;已经完成的展开却不会自动重做。此反例是有向图,不能直接填入本页只接受非负权的无向画布。
怎样修正:非负边权是必要前提。负权最短路应考虑 Bellman–Ford 等方法,并检查可达负权环;如果存在能影响目标的负权环,最短代价可能没有有限下界。
08把想法带进真实题目
比较『第一次发现』与『最终确定』
无向图中 0–1 权重 8、0–2 权重 1、2–1 权重 2。从 0 开始列出前两轮松弛后的 dist,回答何时才能确定节点 1。
需要一点提示
初始化后最小的候选是节点 2,而不是编号较小的 1。
查看完整推导与答案
- 确定 0 后,dist=[0,8,1]。节点 1 只是被发现,尚未确定。
- 确定 2 后,用 1+2 改善节点 1,dist=[0,3,1]。
- 下一轮选择 1 时才能确定其最短距离为 3。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01Dijkstra 的关键前提?
02松弛是什么?
03本课线性选点版本的时间复杂度?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。