每条边的代价都是 1 时,BFS 按边数递增探索顶点。如果边的代价可以是 0 或 1,最短路径指的是权重和最小,而不是边数最少。经过零代价边的绕路可能胜过代价为 1 的直接边。Dijkstra 算法能处理这些权重,但两种取值的特殊结构允许使用更简单的队列:零代价改进放在队首,一代价改进放在队尾。
设定与复习路线
定义 16.2.1
(0–1 最短距离)
设 是有限有向图,源点为 ,边权 。允许平行边和自环:每条边都是单独的邻接表条目。对无向图,将两个方向的关联边都放入表中,权重相同。路径代价为边权之和; 表示从 到 的最小代价,不可达时为 。零边路径给出 。删除非负权环不会增加代价,所以每个可达顶点的最小值都由一条简单路径达到。
先追踪双端队列,观察暂定标号如何改进;再证明两个连续键值的不变量,并用它说明为什么可以确定顶点;最后统计边扫描与队列条目。队列中存储的键值是快照:顶点当前距离改进时,旧键值不会悄悄更新。
显式保留过期条目的算法
使用由 (key, vertex) 对构成的双端队列和布尔数组 settled。假设两端操作为常数时间,整数加法与比较精确。
对每个 v:dist[v] = infinity;settled[v] = false
dist[s] = 0
D = [(0,s)] # 左端是队首
当 D 非空:
(k,u) = pop_front(D)
如果 settled[u] 或 k != dist[u]:继续下一次循环
settled[u] = true
按邻接表顺序遍历每条边 (u,v,w):
如果 not settled[v] 且 k + w < dist[v]:
dist[v] = k + w
如果 w == 0:push_front(D, (dist[v],v))
否则: push_back(D, (dist[v],v))
返回 dist
每个有限标号都是一条实际已发现途径的代价。严格改进会建立一个新快照;旧快照仍留在队列中,弹出时被丢弃。相等候选值不产生新条目。只有当前快照被移出时才确定顶点,而非首次发现时。
概念视角组合
对零权边封闭的距离层
设 。则 是从 沿零权边可达的顶点集; 则是不属于更早各层、并可由 伸出的权重为 1 的边的终点,沿零权边到达的顶点集。在通向 的最短路径上,最后一条权重为 1 的边之前的部分本身也是最短的,成本为 。这个算法就是对这些层所作的广度优先搜索。
定义 16.2.2
(快照、过期条目与已确定顶点)
双端队列中的条目 是一个快照:记录该条目插入时 的值。若 已确定,或 ,该条目是过期的。当 的一个非过期条目从队首被移除时, 就已确定,其标号此后不再改变。
为什么双端队列有序
引理 16.2.3
(双端队列的双键不变量)
在每次移除步骤开始时,双端队列中存储的键值(无论过期与否)从队首到队尾非递减,并且存在整数 ,使每个键值都是 或 。
证明
(对移除步骤作归纳)
每次移除开始时,所存键值按非递减顺序排列,且跨度至多为一:对某个整数 ,每个存储键值都是 或 。起初唯一键值为零。移除队首,包括移除过期条目,都保持剩余条目的这一性质。如果处理一个键值为 的有效条目,每次成功的零权边松弛都在队首插入键值 ,每次成功的一权边松弛都在队尾插入键值 。因此顺序和跨度保持不变。这里讨论的是所有存储键值,不论过期与否;过期检查决定是否扫描边,而不决定条目在队列中的位置。
为什么确定操作安全
定理 16.2.4
(已确定的标号是精确的)
若所有权重都在 中,则每个顶点 在被确定的一刻都有 。算法终止时,对每个顶点 都有 ,不可达者为 。
证明
(最短路径上第一个未确定的顶点)
归纳证明每个已确定顶点都有真实最短距离。首先确定的是 ,距离为零。假设下一次有效移除以键值 确定 ,而此前确定的顶点均正确。其标号是一条途径的代价,因此 。如果 ,取一条到 的最短路径,令 为其上第一个尚未确定的顶点,其前驱 已确定。到 的前缀代价为 ;否则替换成更便宜的前缀会给出到 的更便宜途径。处理 时,其到 的边要么设置、要么保持一个不超过该路径到 的前缀代价的标号。有限标号本身是一条途径的代价,所以不能低于 ;因此 的当前标号为 。
分两种情况。若 ,则 ,与有效条目检查 矛盾。若 ,它最近一次严格改进留下了一个当前快照,仍在双端队列中:当前快照若早已被移除,就会确定 ;而刚移除的条目属于 。这个快照的键值小于 ,与移除 时队列有序矛盾。因此 。归纳也说明跳过指向已确定顶点的松弛是合理的。每个可达顶点最终都会被确定:否则,从已确定区域沿路径指向某个未确定可达顶点的边会插入一个有限有效条目,与算法终止矛盾。不可达顶点仍为无穷大,因为有限标号只由实际途径产生。
证明透视
证明中哪两个事实相互抵触
证明把被移除的条目 与通往 的最短路径上第一个未确定的顶点 比较。对前驱 的归纳给出 ,而路径其余部分的代价至少为 ,故 。上一个引理说明,没有任何存储的键值可以排在被移除的队首条目的键值 之前,因此不可能存在键值更小的 的当前快照。情形 是同一个矛盾,只是改与有效条目检查 抵触。权重属于 的假设只在不变量内部使用:权重 的边可能把较小的键值排到较大的键值之后,这正是下面反例所示的失败。
例题追踪:快照变为过期
例题 16.2.5
(一个条目变为过期)
按所示邻接顺序取边 (权重 1)、(权重 0);(权重 0)、(权重 1);(权重 1)、(权重 0);(权重 0)。数对为 (key,vertex),左端为队首。
| 移除 | 操作 | 操作后的双端队列 |
|---|---|---|
| 确定;发现 | ||
| 确定;将 改进为 0,发现 | ||
| 确定;发现 | ||
| 确定;将 改进为 0 | ||
| 确定 | ||
| 跳过:过期或已确定 | ||
| 跳过:过期或已确定 |
五个距离均为零:例如 的代价为零。旧条目 和 并不是错误,而是已经失效的快照。相反,若直接边首次发现 时就永久标记它,便会阻止经过 的改进。
例题 16.2.6
(自环与不可达顶点)
取顶点 与边(依此次序)(权重 )、(权重 ); 没有入边。移除 并确定 。自环因 已确定而被跳过,通往 的边给出 ,条目 放到队尾。移除 即确定 ,双端队列变空。对 输出 :自环不改变任何东西, 保持 ,因为只有真实的途径才会产生有限标号。
例题 16.2.7
(全是零权重边的环)
取边 (0)、(0)、(0)、(1)。移除 : 放到队首。移除 : 放到队首。移除 :回到 的边因 已确定而被跳过, 放到队尾。移除 即确定 。 的距离为 。零权重环不需要特别处理:已确定的顶点不会再被松弛,所以它不会令循环无限执行。
复杂度与约定
命题 16.2.8
(0–1 BFS 的开销)
设 ,并以 计有向邻接表条目的数目。算法至多向双端队列插入 个条目,时间为 ,辅助空间为 。
证明
(计算扫描次数与插入次数)
记 、,每个有向邻接表条目各计一次。初始化耗时 。每个顶点只确定一次,所以每个出边条目最多扫描一次。每次成功的严格松弛对应一次边扫描并插入一个数对;这种插入至多 次,加上初始数对一次。双端队列操作,包括移除过期条目,共 次。在所述常数时间算术与双端队列模型下,时间为 ,包括无边的图。数组使用 空间,双端队列可包含 个快照,因此这一显式实现的辅助空间为 ,不计图的表示。
对权重 2 或负权,证明不能原封不动地使用:两个键值的不变量或确定标号的证明可能失效。零权环对最小距离无害,却可能产生无限多条等代价途径。本算法计算距离,不统计最短途径的数量。
反例模式
权重 2 的边会破坏队列次序
声称:同一个算法把所有正权重的边都放到队尾,对权重属于 的图也适用。取边(依此邻接次序)(2)、(1)、(0)。移除 得 、,双端队列为 ,次序是乱的。移除 即以标号 确定 ;之后移除 ,边 因 已确定而被忽略。输出 是错的: 的代价为 。补救办法是把权重限制在 ,或对一般的非负权重改用以堆实现的 Dijkstra 算法。
常见错误
常见错误
(边数最少不等于代价最低)
权重为 的直接边只用一条边,而两条零权重边的绕路代价为 。按边数排序的普通 BFS 会报告直接边;在上面的追踪中,它会给出 而不是 。
常见错误
(顶点一被发现就标记为已访问)
由权重 的边得到的标号,仍可能被稍后处理的零权重绕路改进。若边 一发现 就把它标记为已确定,便会挡住经由 的改进。只有在非过期条目从队首被移除时才确定顶点。
检查清单
- 写明有向或无向邻接约定、 及权重属于 。
- 权重 0 放队首,权重 1 放队尾;保留键值快照。
- 跳过过期或已确定的条目;在移除时而非首次发现时确定顶点。
- 分别证明队列有序和最短距离正确,并区分两者。
- 统计边扫描与排队快照;计入初始化与无边图。
练习
快速检查
(依下列邻接次序对边 (1)、(1)、(0)、(0)执行算法。写出每次移除后的双端队列与最终距离。)
序对为(键值,顶点),左端为队首。
解答 · 答案
移除 :、 放到队尾,得 。移除 :确定 ;权重 0 的边给出 放到队首,得 。移除 :确定 ,得 。移除 :确定 ;通往 的边被跳过,得 。 的距离为 。
快速检查
(边依次为 (1)、(0)、(0)。若把权重 0 的改进放到队尾而不是队首,算法对 输出什么? 又是多少?)
写出移除 之后的双端队列。
解答 · 答案
移除 得 放到队尾,接着 也放到队尾:。次序颠倒的条目 先被移除,以标号 确定 ;之后的边 被忽略。输出为 ,但经 可得 。把零代价的改进放到队首,才能保证较小的键值排在前面。
快速检查
(图是无向图,有 条边,每条权重为 或 。界 中的 是多少?)
回想无向边是怎样存储的。
解答 · 答案
每条无向边贡献两个有向邻接表条目,所以 。因此界 即 ,但双端队列的插入次数可以达到 。