算法与数据结构 · 第 22 课
Dijkstra:为什么“目前最近”的顶点可以永久定型?
2026 年 11 月 10 日|第 4 周 · 第 2 天|讲授约 17 分钟(自测另计)
昨天的 Bellman–Ford 允许负权边,靠“至多 k 条边”的逐轮松弛得到正确答案,但要反复扫描边。今天在一个关键前提——所有边权非负——下,使用最小优先队列,每次选出当前距离最小的顶点,并证明:它一旦被正式取出,就再也不可能被更短的路径改进。
一、学习目标与模型(约 1 分钟)
学完应能:①区分暂定距离、已定型距离与真实最短距离;②手工运行使用二叉最小堆的 Dijkstra;③证明“有效最小键出堆即可定型”;④分析允许重复堆条目(lazy heap)的时间、空间与边界;⑤解释负权边为什么破坏证明,明确与 Bellman–Ford、后续 Johnson 的关系。
| 本课处理有向图 (G=(V,E)),(n= | V | )、(m= | E | ),固定源点 (s),边权 (w(u,v)\ge0),允许零权边和重边;不可达点距离为 (+\infty)。(\delta(s,v)) 表示真实最短路长度,(dist[v]) 是目前发现的最好路线长度。图以邻接表存储,堆项为 (距离, 顶点)。 |
二、动机:Bellman–Ford 为什么要扫描很多轮?(约 2 分钟)
Bellman–Ford 不知道某次松弛后的 (dist[u]) 是否已最优,所以最多需要 (n-1) 轮传播改进。Dijkstra 寻找能安全停止修改的一批顶点:已定型集合 (S)。
初始只有 (dist[s]=0),其余为 (\infty)。假如未定型顶点中 (u) 的暂定距离最小;如果今后存在更短的 (s\to u) 路线,它必须跨过某个尚未定型的顶点,而从该顶点往后走的边都非负,不可能越走越便宜到低于眼下的最小值。这一想法将成为严格证明。
注意:“第一次发现 (u)”不等于“可以定型 (u)”;只有它以当前有效的最小暂定距离被取出时才可以。
三、有向图与手工 Trace(约 3 分钟)
考虑如下非负权有向图:
flowchart LR
S((S)) -->|6| A((A))
S -->|2| B((B))
S -->|12| D((D))
B -->|1| A
B -->|5| C((C))
A -->|2| C
A -->|8| D
C -->|1| D
我们使用允许同一个顶点重复入堆的简单实现:发现更短距离时 push 新的 (dist,v),不删除堆里旧项;旧项以后弹出时被丢弃。若距离相等,按顶点字母序打破平局。
| 有效出堆 | 此轮关键松弛 | 改善后的暂定距离 (A,B,C,D) |
|---|---|---|
| S:0 | 发现 A=6、B=2、D=12 | (6,2,∞,12) |
| B:2 | A:6→3,C:∞→7 | (3,2,7,12) |
| A:3 | C:7→5,D:12→11 | (3,2,5,11) |
| C:5 | D:11→6 | (3,2,5,6) |
| D:6 | 无进一步改善 | (3,2,5,6) |
堆里还留有旧项 (6,A)、(7,C)、(11,D)、(12,D)。它们弹出时,键已不等于当前 dist,所以不会再次扩展邻边。距离为 6 的过期 A 与有效 D 谁先弹出,不影响结果。
到 D 的最短路线为 (S\to B\to A\to C\to D),总代价 (2+1+2+1=6)。A 先以 6 被发现,后以 3 定型;D 最初以 12 被发现,后以 6 定型。 这就是“发现”和“定型”的区别。
四、Lazy-Heap Dijkstra 伪代码(约 3 分钟)
DIJKSTRA(G, s):
for v in V:
dist[v] = +INF
settled[v] = false
parent[v] = NIL
dist[s] = 0
pq = min_heap()
pq.push((0, s))
while pq not empty:
(d, u) = pq.pop_min()
if d != dist[u] or settled[u]:
continue # 跳过过期/重复项
settled[u] = true # 从这一刻永久定型
for each edge (u, v, w) in adj[u]:
assert w >= 0
if not settled[v] and d + w < dist[v]:
dist[v] = d + w
parent[v] = u
pq.push((dist[v], v)) # 不用 decrease-key
return dist, parent
流程图对应三个动作:
flowchart TD
P["弹出堆中最小条目 (d,u)"] --> Q{"d 是当前 dist[u] 且 u 未定型?"}
Q -->|否| X["跳过旧条目"]
Q -->|是| F["定型 u"]
F --> R["扫描 u 的每条出边"]
R --> T{"d+w 小于 dist[v] 且 v 未定型?"}
T -->|是| U["更新 dist[v]、parent[v] 并 push"]
T -->|否| V["不更新"]
parent 记录一条最短路线;若有多条等长最短路,严格小于比较保留先发现的其中一条。若只需要终点 t,可在有效弹出并定型 t 时提前停止,不能在第一次给它写入有限距离时停止。不可达点保持 (+\infty)。
五、正确性核心:定型集合的“割”不变量(约 3 分钟)
不变量 I: 对每个已定型 (x\in S),(dist[x]=\delta(s,x));每个有限的暂定 (dist[v]) 都是一条真实 (s\to v) 路线的代价,因此始终有 (dist[v]\ge\delta(s,v))。
初始化成立:s 的空路线代价为 0,其余为无穷大。沿边松弛只把一条真实路线加上一条边,所以不会凭空产生低于真实最短路的估计。
关键归纳步骤: 假设 S 内所有顶点均已正确定型。现从堆取出当前最小有效条目 (dist[u],u),准备把 u 加入 S。反设存在更短的 (s\to u) 路线 P,长度 (\delta(s,u)<dist[u])。
沿 P 从源点出发,找到第一个尚未定型的顶点 y,其前驱 x 必已定型。x 定型时扫描过边 x→y;因为已定型点的值正确,并且最短路径的前缀也是最短路径,故
[ dist[y]\le dist[x]+w(x,y) =\delta(s,x)+w(x,y) \le \text{P 到 y 的前缀代价}. ]
从 y 走到 u 的路径后缀权重非负,前缀代价不大于整条 P,因此
[ dist[y]\le w(P)=\delta(s,u)<dist[u]. ]
这与 u 是未定型顶点中暂定距离最小者矛盾。故 (dist[u]=\delta(s,u)),可安全定型。零权边与并列出堆同样成立。
最小堆中虽然可能有过期项,但跳过后,每个未定型且已有有限距离的点仍有对应的有效堆项;因此有效出堆仍选中最小暂定距离的点。未被访问的不可达点不会被错误定型。
六、复杂度:重复入堆会不会失控?(约 2 分钟)
每个顶点最多有效定型一次,因此其出边只扫描一次,所有边扫描次数最多 m。每次扫描至多引起一次严格改善和一次入堆,连同初始源点入堆:
[ \boxed{\text{push 次数}\le m+1,\qquad \text{pop 次数}\le m+1.} ]
二叉堆每次入堆或出堆用 (O(\log(m+2))),数组初始化与边扫描花费 (O(n+m))。lazy-heap 版本最坏时间为
[ \boxed{O(n+m+(m+1)\log(m+2))} ]
也可宽松写为 (O((n+m)\log(n+m)))。堆最多有 (O(m+1)) 个条目;邻接表、距离、前驱、标记数组共占 (O(n+m)),故总空间 (O(n+m))。
若堆支持 decrease-key,可让每个顶点最多有一个活动堆项,得到常见二叉堆时间 (O((n+m)\log n))((n\ge2))。lazy 实现简洁,代价是旧条目占用部分堆空间。
七、负边反例与 Bellman–Ford 的分工(约 2 分钟)
负边究竟破坏哪一步? 正确性证明用到了“y 到 u 的后缀权重非负”。有很大负权边时,后面反而可能更便宜。
考虑四点图:s→a(2)、s→b(5)、b→a(−10)、a→t(1),没有任何环。标准 Dijkstra 先以 2 定型 a、再以 3 定型 t;然而路线 s→b→a→t 的代价是 (5-10+1=-4)。采用永久定型、不再修改已定型顶点的标准实现就会出错。无负环不意味着可以直接用 Dijkstra。
Bellman–Ford 允许负边且能检测源点可达的负环,代价是多轮松弛。后续的 Johnson 算法将先借助 Bellman–Ford 构造势函数,把无负环图的边重赋为非负值,同时保留任意两点间路径的相对优劣,然后才安全地多次使用 Dijkstra。
其余边界:无向图中的负权边允许来回走出负权闭合游走;不可达点保持 +∞;固定宽度整数实现须防止距离加法溢出;对单个终点的提前终止应以“有效定型”为准。
八、小结与下一课(约 1 分钟)
[ \boxed{\text{非负权} \Rightarrow \text{最小暂定距离可安全定型} \Rightarrow \text{每点只扩展一次} \Rightarrow \text{堆优化最短路}.} ]
Bellman–Ford 的核心是“每轮允许更长的路线”,Dijkstra 的核心是“每轮证明一个点已经最优”。
下一课(2026-11-11,第 23 课):Johnson 重赋权入门。 从势函数 (h(v)) 出发,推导 (w’(u,v)=w(u,v)+h(u)-h(v)\ge0),解释为什么最短路径次序保持不变,而不是直接背公式。
九、四级自测(总分 100;首次不给答案)
前三题可客观判分,Lv4 为开放证明题。题目分别检查关键机制、手工 Trace、边界与复杂度、完整算法证明;课堂只提供中立提示,标准答案和解析只保存在独立测验 JSON 中。
Lv1|定型机制与前提|15 分|预计 2 分钟|单选
对于边权均非负的有向图,采用允许重复入堆的 Dijkstra,下列哪项说法正确?
A. 一个顶点首次被松弛并入堆时,距离就已永久最优。
B. 当从最小堆弹出 (d,u),且 d=dist[u]、u 尚未定型时,可以把 u 永久定型;较旧的较大键应跳过。
C. 若出现 0 权边,Dijkstra 的定型证明不再成立。
D. 只要没有负环,即使存在负边,仍可使用相同的定型证明。
中立提示:区分首次发现与取出当前最小距离;检查证明使用的是边权严格为正,还是非负。
Lv2|松弛与堆条目 trace|20 分|预计 4 分钟|数值
从 S 出发,对有向边 S→A(8)、S→B(3)、S→D(20)、B→A(2)、B→C(6)、B→D(12)、A→C(1)、C→D(2) 运行 Dijkstra。使用 lazy 最小堆:每次严格改善 dist[v] 才 push 新条目,不执行 decrease-key,旧条目弹出时跳过。问整个执行中总共 push 多少个条目(包括初始的 (0,S))?
中立提示:按出堆的有效顶点逐步列出成功松弛;一个顶点可能因距离下降而多次入堆,过期条目不会再次扩边。
Lv3|负边、提前终止与复杂度边界|25 分|预计 4 分钟|多选
关于使用邻接表、二叉最小堆和过期条目跳过策略的 Dijkstra,下列哪些判断成立?(多选)
A. 0 权边仍满足安全定型证明所要求的非负权条件。
B. 负权边即使没有构成负环,也可能使标准的永久定型策略失效。
C. 每条边至多在其起点被有效定型时扫描一次,因而成功松弛至多 m 次,累计入堆至多 m+1 次(m 为边数)。
D. 只要第一次发现目标点并给它写入有限 dist,就可以立即停止,保证得到最短路。
中立提示:分别判断定型证明中的不等式、边被扫描的次数,以及目标点只是发现还是已经定型。
Lv4|定型不变量、算法与复杂度证明|40 分|预计 10 分钟|开放推导
给定含 n 个顶点、m 条有向边的图,所有边权均非负,源点 s。设计带重复入堆的二叉最小堆 Dijkstra。(a)(12 分)写出初始化、RELAX、弹出过期条目、定型及不可达处理的伪代码;(b)(13 分)写出定型集合 S 的关键不变量,并用最短路径首次越过 S 的边证明:每次有效最小键弹出的顶点 u 满足 dist[u]=δ(s,u);(c)(9 分)推导邻接表+lazy 堆的时间/空间复杂度,说明每条边扫描及入堆的次数,并对比支持 decrease-key 的堆;(d)(6 分)构造无负环但有负边的具体小图,说明永久定型为什么可能出错,并指出 Bellman–Ford 在该场景的适用性。
中立提示:证明时在假设存在更短的 s→u 路径上,找第一位尚未定型的顶点 y;其前驱 x 已定型。比较松弛产生的 dist[y]、真实最短距离及最小堆弹出的键,特别使用后半路径权重非负。
十、提交与反馈
回复 Lv1:选项;Lv2:总入堆次数及关键松弛;Lv3:所有正确选项;Lv4:(a)–(d) 分步推导。我会按 15/20/25/40 分逐题批改:80–100 分按原计划继续,60–79 分补一题针对性巩固,低于 60 分优先复习最小割定型证明与负权反例。补练不改变自然日课号。