算法与数据结构 · 第 25 课
四种正确性证明:什么时候能相信一个局部决策?
2026 年 11 月 13 日|第 4 周 · 第 4 天|17 分钟(自测另计)
上四课已经分别学过 Bellman–Ford、Dijkstra、Johnson 和最小生成树(MST)。今天不再重复四个算法的操作步骤,而是回答更难的问题:为什么这些算法敢于相信某种局部信息?各自的证明究竟用了什么前提? 这是从“会运行算法”走向“能设计新算法”的关键一步。
一、学习目标与总览(约 2 分钟)
本节应能:①识别四种不同的正确性证书;②区分“暂时正确的上界”“可以永久定型的距离”“可行势函数”“可以安全选入的边”;③对给定小图核查势函数与最优解;④找到证明失败的最小反例;⑤说明复杂度和适用前提。
| 算法 | 当前保持什么 | 关键证明 | 必不可少的前提 |
|---|---|---|---|
| Bellman–Ford(同步版) | 至多 k 条边的最优游走代价 | 按最后一条边归纳 | 距离最终收敛需无源点可达负环 |
| Dijkstra | 已定型顶点的距离绝不再变 | 最短路首次跨过定型集合 | 边权全部非负 |
| Johnson | 新边权非负、同端点路径保序 | 差分约束与望远镜求和 | 全图无负环 |
| Kruskal / Prim | 当前选择能扩展为某棵 MST | 割性质与交换论证 | 无向加权图;求生成树时需连通 |
注意两个容易混淆的词:Dijkstra 的“定型”指一个数值已经是最短距离;MST 的“安全”指至少存在一个最优解包含目前选中的边,并非某一条边必须属于每个最优解。
二、Bellman–Ford:不贪心,先证明允许的路线范围(约 2 分钟)
对于有向图源点 s,定义 (d_k(v)) 为从 s 到 v 使用至多 k 条边的最小游走代价,无这样的游走记作 (+\infty)。初始化 (d_0(s)=0),其余为无穷大。同步递推为:
[ d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}{d_{k-1}(u)+w(u,v)}\right). ]
不变量证明: 对 k 归纳。至多 k 条边到 v 的路线,要么不超过 k−1 条边,要么有最后一条边 u→v,去掉最后一条边后至多 k−1 条。两种情况正对应公式的两项,没有遗漏。这里即使存在负环,有限 k 的不变量仍成立。
若不存在从 s 可达的负环,任何重复顶点的游走都可以删去非负权闭合段,不增加代价,最后得到至多 n−1 条边的简单路径。因此第 n−1 轮得到真实最短距离;再一轮若还能严格改善,就能检测源点可达负环。
这里的证明从来没有宣称某个顶点“提前永久最优”。它只承诺:每一轮都完整解决了一个边数受限的子问题。
三、Dijkstra:为什么能永久定型?(约 3 分钟)
Dijkstra 的承诺更强。设 S 是已定型顶点集合,不变量为:
[ \forall x\in S,\quad dist[x]=\delta(s,x). ]
每次从最小堆取出一个尚未定型、且其键等于当前 dist 的顶点 u。反设仍有一条更短的 s→u 路线 P。沿 P 找到第一个不在 S 的顶点 y,其前驱 x 在 S。由于 x 已正确,扫描 x→y 时已经执行松弛,所以
[ dist[y]\le \text{P 从 s 到 y 的前缀代价}. ]
因为所有边权非负,P 从 y 到 u 的后缀代价也非负,从而
[ dist[y]\le w(P)<dist[u], ]
与 u 是最小暂定距离的顶点矛盾。于是 u 的距离可以永久定型。
这就是首次跨越已定型集合的证明:不是因为贪心“看起来合理”,而是任何假想的更短路线都会导致一个更小、应当先被取出的候选顶点。
负边使证明在哪里断裂? 若 P 的后缀权重为负,便不能断言“到 y 的前缀代价 ≤ 整条 P 的代价”。例如 s→a(2)、s→b(5)、b→a(−10)。图无环,但 a 首次以 2 出堆时真实最短距离是 −5。没有负环并不能代替非负边权前提。
四、Johnson:不直接定型,而是先修复证明条件(约 3 分钟)
如果图中有负边但没有负环,不能直接用上一节的 Dijkstra 证明。Johnson 先引入超级源点 q,并添加 q→v(0) 到所有原顶点;用 Bellman–Ford 计算:
[ h(v)=\delta(q,v). ]
由于最短距离满足三角不等式 (h(v)\le h(u)+w(u,v)),定义新边权
[ \boxed{w’(u,v)=w(u,v)+h(u)-h(v)\ge0.} ]
至此 Dijkstra 所需的非负边权前提被构造出来了。但还要证明:重赋权不会换掉最短路线。对任何 s→t 路径 P,把每条边的势函数差相加,中间项全部抵消:
[ \boxed{w’(P)=w(P)+h(s)-h(t).} ]
同一起终点的每条路径都被加上同一个常数,所以最短路径次序不变。求得新权距离后用
[ \boxed{\delta(s,t)=d’(s,t)-h(s)+h(t)} ]
恢复原距离。差分约束保证新图可用 Dijkstra,望远镜求和保证解没有被换掉;两条证明缺一不可。
五、数值 Trace:亲手核查一份“可行证书”(约 2 分钟)
有向图只有如下五条边:
flowchart LR
S((S)) -->|"5"| A((A))
S -->|"10"| B((B))
A -->|"-4"| B
A -->|"9"| T((T))
B -->|"3"| T
从 q 向四个点连 0 权边后,Bellman–Ford 得到:
| 顶点 | S | A | B | T |
|---|---|---|---|---|
| 势函数 h | 0 | 0 | −4 | −1 |
新边权分别为 S→A:5、S→B:14、A→B:0、A→T:10、B→T:0。新图中,沿 S→A→B→T 的距离为 5;恢复原距离为 (5-0+(-1)=4),直接用原边权验算也是 (5-4+3=4)。
这个计算提供两张可检查的证书:每条新边的权重都非负;还原的路径长度与原图一致。但要证明全图算法正确,仍需上节的普遍代数证明,而不能只靠一个例子。
六、MST:不是定型距离,而是交换一条边(约 2 分钟)
无向图的一道割是 ((U,V\setminus U))。已选边集合 A 若没有边跨过该割,称该割尊重 A。割性质说:当 A 能扩展为一棵 MST 时,该割上任意一条最轻跨割边 e 都是安全的。
证明:取一棵包含 A 的 MST T。若 e 已在 T 中,直接成立。否则把 e 加入 T 会形成一个环;该环中必有另一条跨割边 f,而且 f 不在 A 中。由于 e 是最轻跨割边,(w(e)\le w(f))。于是
[ T’=T-{f}+{e} ]
仍是一棵包含 A∪{e} 的生成树,权重不大于 T,所以也是 MST。Kruskal 每次连接两个不同分量的最轻可选边,Prim 每次选当前访问集合向外的最轻边,安全性都来自这个证明。
MST 与最短路径树不是一回事。 三角形 AB=1、BC=1、AC=1.5。从 A 求最短路径树要选 AB 和 AC,总边权 2.5;MST 选 AB 和 BC,总边权 2,却让树上 A→C 的路径长为 2(原图最短是 1.5)。一个目标最小化每条源点路径,另一个最小化全树总边权。
七、一张证明路线图与复杂度(约 2 分钟)
flowchart TD
Q["算法为什么正确?"] --> BF["Bellman–Ford:限制边数"]
Q --> D["Dijkstra:永久定型距离"]
Q --> J["Johnson:转换权重"]
Q --> M["MST:安全添加边"]
BF --> B1["最后一条边归纳"]
D --> D1["首次越出 S + 非负后缀"]
J --> J1["差分约束 + 势差抵消"]
M --> M1["跨割最轻边 + 交换"]
设 n 为顶点数、m 为边数。同步 Bellman–Ford 每轮复制距离并扫描边,最坏 (O(n(n+m)));允许重复入堆的二叉堆 Dijkstra 为 (O(n+m+(m+1)\log(m+2)));Johnson 先付一次 Bellman–Ford,再运行 n 次 Dijkstra,显式保存全部点对结果另需 (\Theta(n^2)) 空间;Kruskal 排序加 DSU 为 (O(m\log(m+1)+(n+m)\alpha(n)))。其中 (\alpha) 为反 Ackermann 函数。上述时间均包括相应初始化成本,不要把不同实现下的上界混为一个公式。
共同的设计方法: 先写出算法每一步打算“永久相信”的结论,再找能维持它的证书。如果缺少必要前提,不要强行使用原证明;要么换算法(Bellman–Ford),要么先变换问题以恢复前提(Johnson)。
八、边界总结与下一课(约 1 分钟)
Bellman–Ford 的第 n 轮检测只针对固定源点可达的负环;Johnson 的超级源点使全图负环都可检测。Dijkstra 要求新边权非负,不要求严格正。割性质容许负权和等权,但只保证存在一棵包含安全边的 MST;非连通图只能求最小生成森林。含负权的无向图做 MST 与含负边的有向图做最短路,问题性质不同,不能混用负环结论。
下一课(2026-11-14,第 26 课):MST 的唯一性、边的敏感性与次小生成树。 我们将从割与环的相互制约推导“替换一条树边后增加多少成本”,进一步理解为什么有些边必选、有些边可替换;第 4 周第 7 天再做综合考核。
九、四级自测(100 分;首次不给答案)
前 3 题客观判分,最后一题按分步证明评分。课堂不公布答案或解析,下面只有中立提示。
Lv1|机制与证明目标|15 分|预计 2 分钟|单选
比较 Bellman–Ford、Dijkstra、Johnson 和 MST 的正确性证明。下面哪一项同时满足其算法前提与证明结论?
A. Bellman–Ford 同步执行第 k 轮后,所有顶点都已经得到不受边数限制的最短距离。
B. Johnson 用超级源点求得的势函数使重赋权边非负,并保持同一起终点路径间的代价次序。
C. Kruskal 选中的每条跨割最轻边必然出现在原图的每一棵 MST 中,包括有等权边时。
D. Dijkstra 只要求图中没有负环,就能把有效最小堆顶点永久定型。
中立提示:分别检查:Bellman–Ford 的轮数限制、Johnson 的两个证明目标、割性质的量词和 Dijkstra 的权重前提。
Lv2|Johnson 数值 Trace|20 分|预计 4 分钟|数值
有向图的边为 S→A(5)、S→B(10)、A→B(−4)、A→T(9)、B→T(3),没有其他边。Johnson 增加超级源点 q,向 S、A、B、T 各连一条 0 权边,求 h;重赋权后从 S 运行 Dijkstra。最终还原的原图最短距离 δ(S,T) 是多少?只提交数值,可附 h 和 d’ 的手算过程。
中立提示:先计算从 q 到各点的最小距离;逐边检查 w’=w+h(u)−h(v),最后从新权距离减去起点势、加上终点势。
Lv3|边界、反例与反向推理|25 分|预计 4 分钟|多选
下面哪些结论成立?(多选,选择全部正确项。)
A. 同步 Bellman–Ford 的“至多 k 条边”不变量,在图中存在源点可达负环时,对每个有限轮数 k 仍成立。
B. 对任意给定势函数 h,恒等式 w’(P)=w(P)+h(s)−h(t) 都成立,但新边权不一定非负。
C. 无向连通图只要出现两条等权边,MST 就必然不唯一。
D. 若最短路径树连接了全部顶点,它一定同时最小化所选 n−1 条边的权重总和。
中立提示:把有限步动态规划与无界最短路区分开;代数恒等式不依赖可行势;再用三顶点三角形分别检验等权与两种优化目标。
Lv4|综合算法正确性审计|40 分|预计 10 分钟|开放推导
给定可能含负边的有向图 G,以及另一张连通无向带权图 H。请完成一份“正确性审计”:(a)(10 分)写出同步 Bellman–Ford 的递推并归纳证明第 k 轮至多 k 条边不变量;说明在什么前提下 n−1 轮足够。(b)(10 分)陈述 Dijkstra 的定型不变量,使用最短路径首次离开已定型集合的论证证明其安全性;给出无负环却有负边的反例。(c)(10 分)说明 Johnson 怎样借超级源点和 Bellman–Ford 构造 h,证明新权非负、路径保序和距离恢复式。(d)(10 分)给出 H 的割性质交换证明,说明 Kruskal 为什么安全;写出四种方法各自的核心时间界,并给出一个最短路径树不是 MST 的小图。
中立提示:分别找到四种证书:限制边数的归纳式、非负后缀、势函数差分约束、跨割边的替换。MST 交换时注意“至少存在一棵”而非“每一棵”。
十、提交与反馈
回复 Lv1:选项;Lv2:数值和势函数计算;Lv3:全部正确选项;Lv4:(a)–(d) 的证明。我会按 15/20/25/40 分逐题批改:80–100 分按课表继续;60–79 分补一道对应知识点的练习;低于 60 分先回看证明中被误用的前提。补练不修改自然日确定的课号。