课前零食：从乱走到松弛

“最短路”听起来像地图题，其实它是在练一件很通用的事：不断拿到一个更好的到达方案，并且知道什么时候可以不再怀疑它。这节先把这件事练顺手。

本节目标

学完后，你能：

把“到达某状态的最小代价”翻译成点、边和边权；
从按层 BFS 推出距离的含义，再发现权值不同时为什么需要松弛；
区分 BFS、0-1 BFS 和 Dijkstra 各自能保证什么；
给出负边让 Dijkstra 失效的原因，而不是只背“不能有负边”。

前置知识与课前自测

前置：图、队列、优先队列、整数加法。

所有道路长度都是 1 时，BFS 第一次到达一个点为什么就是最少边数？
若有一条长度 1 的直达路，以及两条长度 0 的绕路，边数最少的路线一定最短吗？
dist[v] 初始设为无穷大，后来变小，这个数是答案还是“目前已知的上界”？

答案

1. 队列按走过边数逐层扩展，前面层数更小。2. 不一定，总代价最小才是目标。3. 是上界：它对应一条真实已知路线，但以后可能发现更短路线。

互动规则：把每个“到达价格”写成可撤销的报价

画预设有向图，并在每个点旁留一个格子写 dist。初始只有起点 S 写 0，其余写 ∞。每发现一条路线，都要写成“从谁来 + 边权 = 新报价”；报价变小才允许覆盖旧值。纸上不要写“最短”二字，直到你能证明某点不可能再更便宜。

本节反复使用四栏：已确定的点、待处理的候选、每点当前报价 dist、一条边松弛后谁被重新安排。这比一开始记 BFS/Dijkstra 名字更重要。

从零搭框架：先让路线枚举失败，再保留每点最便宜的代表

第 0 步：把路径写成动作序列

从 S 到 T 有时有多条走法，甚至可以绕环无限走。先画无权图 S-A-T 与 S-B-T。列出所有长度至多 2 的路线，并把每个点第一次被碰到时的“走了几条边”写上。

停顿 0：若所有边都花 1，为什么队列里先放入的点一定不比后来放入的点远？请用“层”而不是算法名解释。

展开：BFS 的第一份不变量

从 S 出发的点距离 0；先入队的是距离 1；处理完它们才会产生距离 2。FIFO 队列维护按层扩张，所以第一次到达一个点已经用了最少边数。这里的状态是“最少边数”，不是什么通用最小代价。

第 1 步：给边贴价格，观察“先到”失去资格

画 S→A(1), S→B(0), B→A(0)。请按普通 BFS 的邻接顺序先处理 S→A 再处理 S→B，写出 A 第一次的报价；随后走 B 的边，写出新报价。

停顿 1：A 已经“访问过”了，为什么仍必须允许它被改成更小的 0？如果拒绝更新，错的是哪条路线？

展开：从 visited 变成 dist 上界

A 首次得到 1，后来通过 `S→B→A` 得到 0。权不同时，“第一次访问”不再是证书；`dist[A]` 只能表示目前已知的一条真实路线价格，即上界。新路线更便宜时要松弛并重新安排 A。

第 2 步：先手算一句松弛，再把它当作唯一更新入口

对每条边 $u\to v$、权 $w$，把下句抄在纸上，给 S→B(0) 与 B→A(0) 分别代数：

$$ \text{若 }dist[u]+w<dist[v]\text{，就用 }dist[u]+w\text{ 覆盖 }dist[v]. $$

请写出每次覆盖前后 A、B 的值。然后回答：这句话为什么不会把 dist[v] 压到真答案以下？

展开：每个报价都要有路线发票

`dist[u]` 若有限，就对应一条真实 S 到 u 的路线；再接边 $(u,v)$ 仍是一条真实 S 到 v 的路线。因此候选只可能是真答案或更大的上界，不会凭空小于真答案。松弛的正确性起点是“报价有发票”，不是堆的写法。

第 3 步：同一句松弛，为什么要三种工作队列

对下面三类边权，先在纸上给新报价贴标签：应当优先处理、稍后处理、还是可定案？

边权	新报价相对当前层	合理的容器	你要维护的顺序
全为 1
只有 0/1
非负任意整数

停顿 3：0 边的新点为什么应塞到双端队列前端？Dijkstra 为什么不允许负边？先用一张具体反例说明。

展开：容器是在维护“谁可能最便宜”

全 1 用 FIFO 层序；0 边不增加价格，应放队首，1 边放队尾；非负任意权用最小堆取当前最小报价。负边能让一个看似较远的未处理点绕回来压低已弹出的点，破坏“当前最小可定案”的论证。

第 4 步：状态可能不止地点

想象到同一地点 P 时，开关是开或关会决定可走的路。请写出：P,开 与 P,关 能否合并成一个 dist[P]？若不能，图中的一个点究竟代表什么？

展开：最短路先建状态图，再选算法

不能合并，因为后续动作集合不同。一个图点代表“足以决定未来合法动作与代价的状态”，可写成 `(位置,模式)`。正式课的难点常在这里；BFS/Dijkstra 只是状态图建好后的调度员。

问题动机：枚举路线会让环偷偷繁殖

从起点枚举所有走法，遇到环甚至会有无限多条路线；即使只枚举简单路径，数量也可能指数级。真正应该保存的不是“所有走法”，而是每个状态目前最便宜的到达价格。若一条新边让价格更低，就更新它；这一步叫松弛（relaxation）。

上图中从 $S$ 直接到 $A$ 要 1，但 $S\to B\to A$ 的总权是 0。普通 BFS 若把“先到”误当成“永远最好”，就会做出错误承诺。

步步式引导

1. 全部边权为 1：层数就是代价

若每次动作代价相同，距离等于经过边数。BFS 的队列让所有距离为 $d$ 的状态先于距离为 $d+1$ 的状态出队；第一次访问就可以定案。

dist[start] = 0
queue.push(start)
while queue not empty:
    u = queue.pop_front()
    for v in neighbors[u]:
        if dist[v] is INF:
            dist[v] = dist[u] + 1
            queue.push_back(v)

2. 权值不同：先到不再有法律效力

对边 $u\to v$、权 $w$，若 dist[u] + w < dist[v]，我们发现一条更短的真实路线，便更新：

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    put v back into the work structure

不同算法的差别主要是“下一个处理谁”，而非这句松弛本身。

边权条件	适合的取出顺序	核心理由
都为 1	FIFO 队列	层数单调
只有 0/1	双端队列	0 边放前面，1 边放后面
都非负	最小堆	当前最小距离不会被未来绕路压低

3. Dijkstra 为什么敢“定案”

从堆中取出未定案且 dist 最小的 $u$。假设存在一条尚未发现的更短路线到 $u$，它从已定案区域第一次跨出的边会到达某个未定案点 $x$。由于边权非负，那条路线到 $x$ 的长度不大于到 $u$ 的长度，$x$ 本应更早被取出，矛盾。

负边会拆掉这个论证：一个先看起来较远的点能借负边回来，把已经定案的距离再压低。不是堆不够努力，是“非负”这张保证书被撕掉了。

纸上模拟：把报价变化写成时间线

对边 S→A(1), S→B(0), B→A(0), A→T(1), B→T(1)，从 S 开始。先预测，再填写：

取出/处理谁	当前 `dist`	尝试的边	是否松弛	新工作队列或堆
S		`S→A(1)`
S		`S→B(0)`
B		`B→A(0)`
B		`B→T(1)`

然后把 A 以距离 1 的旧条目也画进最小堆；它晚些弹出时为何必须被跳过？

展开：旧条目不是 bug

S 后有 `dist[A]=1,dist[B]=0`；处理 B 后 A 变 0、T 变 1。堆中旧 `(1,A)` 仍在，但当前 `dist[A]=0`，它代表一条已被更优路线淘汰的报价，跳过即可。允许旧条目避免了昂贵的堆内删除，同时仍只会按真实最小报价扩张。

核心知识：距离是可证的上界，定案是额外结论

任何时刻 dist[v] 要么是无穷大，要么对应一条从起点到 $v$ 的实际路线，因此永远不会小于真答案。松弛只会让上界变紧。BFS、0-1 BFS、Dijkstra 分别在各自边权条件下安排处理顺序，保证某个点被正确时机取出后，其上界已经等于真最短路。

0-1 BFS 中，走 0 边的新状态应放队首，走 1 边放队尾；这模拟了按距离递增处理，不必每次使用堆。三者的图上时间通常为 $O(V+E)$、$O(V+E)$、$O((V+E)\log V)$。

实现指南

INF 取足够大的 long long，常用 max/4，避免 INF+w 溢出。
Dijkstra 的堆中允许旧条目；弹出时若条目距离不等于当前 dist[u]，跳过它。
0-1 BFS 只允许权 0 或 1；不要看到“小权值”就强行塞进双端队列。
状态不一定是原图顶点。若“是否开过开关”影响下一步，就应把 (位置, 开关状态) 看作不同点。

互动小实验室

运行从乱走到松弛.py。可选择 BFS、0-1 BFS 或 Dijkstra；预设图会逐条打印松弛，以及状态进入队列、队首或堆的原因。

建议先选 0-1 BFS，预测 $A$ 会先以距离 1 被发现、后以距离 0 被改写；再选 Dijkstra，观察旧堆条目为何被跳过。

扩展与联系

最短路的“状态扩点”会通向正式课中的免费切换、时间周期和差分约束。若存在可达负环，最短值可以无限下降，此时问题不再是“找一个有限最短路”；若图是 DAG，按拓扑序松弛能处理某些负边。

总结与自检

一次松弛为什么不会把距离错误地压到真答案以下？
0-1 BFS 中权 0 的新点为什么放队首？
Dijkstra 的“最小未定案点可定案”具体依赖哪条条件？

自检答案

它由一条真实路线拼成；它与当前层同价，应先于加 1 的点处理；所有边权非负。

一周预热安排

第 1 天：在单位边小图上手做 BFS 层号。
第 2 天：画出零权反例，解释普通 BFS 的失败。
第 3 天：给每条边写一次可能的松弛不等式。
第 4 天：运行互动程序，比较 0-1 BFS 和 Dijkstra 的工作队列。
第 5 天：进入最短路模型选择正式课。

00-课前零食-从乱走到松弛.md 11 KB Permalink History Raw