学习顺序主线第 21 / 22 课 · 阶段 6

为什么现在学:在 BFS 的无权最短路上增加边权,区分发现与最终确定。

返回算法课程
图与搜索进阶

Dijkstra 最短路Dijkstra

反复确定当前最近的节点,再用它改善邻居的候选距离。

45 分钟前置:图 · BFS · 贪心思想

学完这一课,你应该能做到

  • 区分临时距离与已确定的最短距离
  • 写出并解释松弛条件
  • 证明非负边权为什么不可缺少

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最直接的办法,为什么慢?

枚举所有简单路径计算代价。

暴力 · 最坏 O(V!) 条路径

大量路径共享相同前缀,候选数量可呈阶乘级增长。

03一步步,推导出优化思路

1

保存每个节点的临时距离

给每个节点维护当前已知最小距离 dist。

2

确定当前最近的候选

非负边权保证:未确定节点中 dist 最小的节点,距离可以最终确定。

3

沿邻边松弛,再选下一点

用这个节点尝试松弛每条出边,再选择下一个最近节点。

贯穿算法的不变量

已确定节点的距离就是最短路;未确定节点记录目前已发现路径的最小代价。

拿一个小输入,逐步手算

无向带权边 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 更便宜。

不变量必须同时覆盖两类节点

  1. dist 的每个有限值都对应一条实际发现的路径;已确定节点的值为真实最短距离。起点在非负图中距离为 0。
  2. 选择未确定节点中临时距离最小者。通过第一个未确定节点的反证论证,它不可能再被其他非负后缀改得更短。
  3. 松弛其邻边加入新的候选路径,保持临时值的含义。重复直至没有可达的未确定节点,剩余 ∞ 表示不可达。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Dijkstra交互演示
STEP 01 / 26
421580d = 01d = ∞2d = ∞3d = ∞4d = ∞
无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01

源点为 0。其距离为 0,其余暂为无穷大。所有边权必须非负。

dijkstra.py参考实现 · 当前第 4 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

distance[start] = 0
起点到自己走空路径,代价 0。其他节点初始应为无穷大,不能用 0 表示未知。
node = -1
每轮重新寻找未确定节点中的最小值;本课用线性扫描,便于观察选择过程。
visited.add(node)
这里的 visited 表示最终确定。它与 BFS 中首次发现即标记的含义不同,不能照搬标记时机。
distance[node] + weight < distance[next]
候选必须是『到当前节点的总代价+这条边权』,不能只拿边权与 dist[next] 比较。

05复杂度,来自具体的工作量

时间复杂度
O(V2+E)O(V^2+E)

本课采用直观的线性选最小值:V 次选择,每次扫描 V 个节点,加上所有边的松弛。二叉堆版本可改善到 O((V+E)log V)。

辅助空间
O(V)O(V)

dist、visited 和候选节点集合都是 O(V),不含输入邻接表。

拖动 n,看看增长速度

把工作量具体数出来

本课每轮扫描 V 个节点选最小值,最多 V 轮,选择部分 O(V²);所有邻边松弛合计 O(E),总时间 O(V²+E)。

二叉堆可把选择过程改进为优先队列。对常见简单图实现,常写 O((V+E)log V);需要处理堆中距离过期的候选,不能只把容器名字替换一下。

本版 dist 与已确定集合各 O(V),辅助空间 O(V),不含输入邻接表。返回的是距离数组,恢复路径需额外保存成功松弛时的前驱。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

不能处理负权

负权会破坏已确定距离不会变小的证明,应考虑 Bellman–Ford。

02

不可达不是 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。

查看完整推导与答案
  1. 确定 0 后,dist=[0,8,1]。节点 1 只是被发现,尚未确定。
  2. 确定 2 后,用 1+2 改善节点 1,dist=[0,3,1]。
  3. 下一轮选择 1 时才能确定其最短距离为 3。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01Dijkstra 的关键前提?

02松弛是什么?

03本课线性选点版本的时间复杂度?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。