动机
广度优先搜索使经过的边数最少。边的费用不同时,边数最少却未必总费用最低:一条昂贵的直达边,可能不如两条便宜的边。我们需要比较累计权重,而不只是队列中的层数。
Dijkstra 的规则是反复把暂定距离最小的顶点定案。尚未检查所有路线,为什么已经可以认定这个值正确?答案在于一条经过已定案集合边界的路径,以及证明中一个恰好用到非负性的地方。给规则冠以“贪心”之名,并不能代替正确性证明。
本节还区分求出答案与核验答案。一组距离若配有适当的前驱边和次序,只需扫描一次图便能证明最优性。这样的证书既能揭示负边导致的算法失败,也能解释为什么只挑等号成立的边还不够:它们必须真正连回源点。
定义
定义 5.5.1
(带权游走、距离与暂定标号)
设 为有限有向多重图,,。允许平行弧与自环;每条弧有独立身份及有限实权 。固定源点 。游走可以重复顶点,路径则没有重复顶点;长度是各弧权重之和。源点 的空游走长度为零。
记 为从 到 的游走长度的下确界;没有这样的游走时,定义为 。算法部分假设每条弧满足 ;后面的证书定理则明确允许任意有限实权。
暂定标号 或是某条候选游走的有限长度,或为无穷。已定案顶点已被选出,其标号视为最终值。对 到尚未定案顶点 的弧做松弛:只有候选值 严格更小时才替换 ,同时存储这条实际弧作为 的前驱。不要对无穷标号进行加法。
所有比较先按精确运算理解。我们先计算加法、比较及索引操作次数,再单列整数的位成本。本节以数组扫描实现,不预先假设优先队列。关于树与广度优先搜索的一节提供无权可达性和 BFS 的背景。
定理/命题
定理 5.5.2
(非负权最短游走可以选为路径)
若所有弧权非负,每个可达顶点都有一条从 出发、至多含 条弧的最短路径。因此距离有限且能取到,并且 。不可达顶点的距离为无穷。
定理 5.5.3
(最小暂定标号可以安全定案)
初始化 ,其他标号为无穷,所有顶点未定案。反复从未定案顶点中选取标号最小者;若最小值为无穷便停止,否则将它定案,并松弛其指向未定案端点的出弧。平局可任意处理。
每个定案标号都等于真实距离。结束时,已定案顶点恰为可达顶点,其前驱边能够恢复最短路径。数组实现需要 次精确操作,连同图共用 个存储字。
定理 5.5.4
(可以单独核验的最短距离证书)
本定理允许任意有限实权。给定含 的集合 、 上的有限标号且 ,以及取值于 的次序号,源点次序号为零。要求:
- 没有弧从 指向 外。
- 内每条弧都满足 。
- 每个 内非源点 都有来自 内的前驱弧,前驱次序号严格较小,且 。
那么 恰为源点可达集合,其标号就是真实距离;其他顶点均不可达。只需 次精确操作检查这些局部条件,无须重跑最短路算法。
证明思路或证明
先删去闭游走,再证明最小值存在
证明
(先删闭子游走,再在路径中取最小)
取一条到达目标的游走。若某顶点重复出现,两次访问之间是一段权重非负的闭游走。删去它,端点不变,长度不会增加。不断删除,每次弧数减少,最终得到路径。
有限多重图只有有限条简单路径:每条至多 条弧,弧都取自有限集合。可达目标至少有一条路径,因此这些路径长度中存在最小值。删圈论证说明它不大于任何游走长度,所以它实现了距离。源点的空游走长度零,又没有负长度游走,故距离为零。权重为零的闭游走同样可以删除;无需每次都严格缩短长度。
找到贪心证明中使用非负性的准确位置
证明
(沿最短路径上首个未定案顶点对定案作归纳)
整个过程中,每个有限标号都是某条实际源点游走的长度。开始时由空游走见证;松弛时在已有游走末尾接一条实际弧。因此有限标号不可能低于真实距离,也不可能出现在不可达顶点上。
源点首先定案且标号正确。归纳假设此前定案顶点全部正确,设 是下一个有限最小标号顶点。取一条 到 的最短路径 ,令 为 上首个未定案顶点, 为它的前一顶点。源点已经定案,所以 存在。 定案时, 还未定案,故该弧已被松弛。此后标号只会下降,于是
第一步用最小值选择,第二步用 的正确标号。真实的 距离不大于 到 的那条特定前缀。最后一步才使用非负性:剩余后缀不能降低总长度。游走见证又给出反向不等式,因此 标号正确。
如果最小标号为无穷时仍有可达顶点未定案,取到它的任意源点路径。首个未定案顶点前面是已定案顶点;后者早已通过松弛给前者一个有限标号,矛盾。至多定案 个顶点,故算法终止且定案集合准确。
证明透视
贪心是选择规则,前缀不等式才是证明
最小值选择把当前顶点与真正最短路径上的首个未定案顶点比较。松弛用路径前缀约束后者标号;非负性再把前缀长度压到完整最优值以下。存在负后缀时,最后一步可能失败,即使此前每个定案值都正确。
零权圈不会使算法前驱形成圈
证明
(定案次序使前驱无圈)
按定案先后给顶点次序号。前驱只由已经定案的顶点设置,而被更新端点尚未定案,所以端点最终定案时,其前驱次序号严格更小。严格改进时,前驱与改进后的标号一同更新;相等候选不改变前驱。
每个有限非源点标号都来自松弛。沿前驱回溯,次序号严格下降,不会成圈;只有源点无须前驱,故最终到达源点。各弧上的等式相加,恢复路径的长度就是最终标号。平行弧要求保留实际选择的弧身份,不能只记两个端点。
避免圈靠的是次序号,而非距离严格增加,故零权弧没有问题。算完距离后随意挑一些紧弧,不会自动获得同样的保证。
双向证明独立证书
证明
(次序给出可达性,不等式给出下界)
对满足三个条件的任意证书,严格下降的前驱次序先保证每个 内顶点有一条 内源点路径。有限下降链不可能循环,只有 可以没有前驱。反过来,没有弧离开 ,所以源点游走不可能到达外部。 恰为可达集合。
对任意从 到 的游走,沿弧累加不等式。中间标号相消,,得到 不大于该游走长度。因此它不大于所有候选长度的下确界。紧前驱路径又恰好有长度 ,故下确界也不大于 。两边合起来即为相等,并证明最小值取到。
这里没有使用权重非负。因此带负弧的图也可能有有效证书,尽管贪心算法不再普遍正确。可达集合之外的负圈与这个单源证书无关。逐点检查归属、次序范围和前驱身份,再逐弧检查紧性及不等式,只需一次点弧扫描。
算法输出也具备这样的证书。前驱和次序已经证明正确。若有弧从定案集合离开,它在停止前就会提供另一个有限候选,矛盾。最后,真实距离满足所有边不等式:在到弧尾的最短路径后追加该弧即可。
概念视角算法
路径给上界,不等式给匹配的下界
展示一条费用为 的源点路径,只能证明最优值至多为 。边不等式则保证每条竞争游走至少花费 。前驱路径与不等式是互补证据;单独一个暂定标号还不能证明最优性。
按实际存储方式计算成本
存储出弧邻接表、标号、前驱弧和定案标志。每次扫描全部 个顶点选取最小者,至多 次,所以扫描成本为二次。每个定案顶点的出弧表只扫描一次,松弛总数至多 。初始化与记录次序也包含在该界内,图和数组总存储量为 的线性量。输出一条路径时回溯前驱并反转列表,输出本身可能含 个顶点。
若整数权重在 与 之间,最终有限距离至多 ,临时松弛候选可安全界为 。标号、弧身份及循环索引需要
位,无穷另设标志。在把寻址作为基本操作的索引数组模型中,按这个位长计算加法、比较和索引算术,得到它乘 的算术位成本。精确实数证明本身不保证有限精度实现或误差界;更快的优先队列界也需要另证数据结构成本。
例题详解
例题 5.5.5
(定案之前,一条路线两次改进)
顶点为 。弧及权重为:,,,,,,。 没有任何关联弧。
定案 后, 标号为 、。定案 , 改为 , 得到 ;定案 , 改为 , 得到 ;定案 , 改为 。随后定案 ,在无穷的 之前停止。定案顺序 ,对应标号 。
的前驱路径为 ,费用 。直接经 的另一条路线费用十一。 到 的弧在最终标号下不是紧弧:候选 大于 的真实距离 。证书要求每条弧满足不等式,只有所选前驱弧必须取等号。
例题 5.5.6
(零权平局仍有无圈前驱)
弧 、、、 的权重都为零, 和 的权重均为 。定案 后, 标号均为零,前驱均为 。若先定案 ,其到 的相等候选不覆盖 的前驱;它可将 标号设为 、前驱设为 。随后定案 ,相等的 候选也不覆盖旧值。
尽管 形成零权圈,所有前驱仍回到 。反向处理平局会得到另一棵有效最短路树。相等的最优距离,并不要求次序号相等,更不允许前驱成圈。
例题 5.5.7
(证书能够处理负弧)
,,。令 ,标号 、、,次序为 ;前驱选 和 。
两条前驱等式成立,剩余弧满足 。因此证书直接证明这些距离,包括负距离,无须依赖非负权算法定理。这不表示贪心定案在所有含负边图上都正确。
常见错误
反例模式
负后缀破坏过早定案
,,。 的真实距离为零,但算法在选择 前已把 定案为 。由于不再松弛定案顶点,最终 的标号错误。所得证书在弧 的不等式失败: 不成立。图中没有负圈;单条负弧已经足以造成失败。
常见错误
(BFS 层数不是带权距离)
不要把 BFS 的边数层次当作带权距离。在第一个例题中, 沿 只离 两条弧,但该路线费用为 ,而四条弧的路线 只需 。
常见错误
(永不回到源点的紧前驱)
不要把任意紧前驱当作源点路径证书。在零权例题中,选 和 都是紧的,因为 之间的四条弧权重都是 ,三个标号也都是 ;但从 沿前驱回溯永远回不到 。排除这种情形的正是严格次序条件。
常见错误
(无穷不是很大的有限费用)
无穷表示没有路线,不是很大的有限费用。若用 之类的哨兵值代替 ,并对它加上权重,不可达顶点便可能得到标号 ;检查哨兵值的停止条件就会把它当作已到达。
本节处理单源距离;使边权总和最小的生成树,以及允许负边的最短路算法,是不同问题。
只要从源点到达不了负权圈,逐轮松弛所有弧就可行,只是代价较高。
自然的下一个问题
有负权弧时,怎样计算距离?
只要从源点到达不了负权圈,逐轮松弛所有弧就可行,只是代价较高。
若从 到达不了任何负权圈,删去闭子游走仍不会增加长度,所以最短游走可取为简单路径,至多 条弧。进行 轮,每轮松弛所有弧:第 轮后,每个标号至多是弧数不超过 的源点游走的最短长度,而标号永不低估。这个 Bellman–Ford 过程用 次运算;若第 轮仍有标号改进,就揭示了一个可到达的负权圈。上面的证书可以检查它的输出。
总结
非负权既保证最短游走可以选成路径,也使最小暂定标号能安全定案。从较早定案顶点发出的严格松弛,即使遇到零权圈也会产生有次序的前驱路径。另一方面,有根紧路径配合边不等式可独立证明精确距离,将答案的构造与最优性的核验区分开来。
练习
快速检查
(在第一个例题中只将弧 的权重由 改为 。求 的新距离及一条到 的最短路径。)
解答 · 答案
的距离仍为 ,由 到达。 的距离现为 ,经 ; 的距离为 ,经 ; 仍不可达。 定案后 标号为 ,可先于 定案,其 候选为 。较晚经 得到的 候选 不会改进它。新路径费用 。
快速检查
(令 孤立,另外两个顶点 之间有双向零权弧。三点都标零, 互为前驱。为什么边不等式和紧性都成立,却不是有效距离证书?)
解答 · 答案
每条弧权为零,端点标号相等,所以不等式及所选等式都成立。但 均不从 可达。严格前驱次序同时要求 的次序小于 的, 的又小于 的,不可能。次序条件拒绝假圈,使紧边真正成为源点路径;只凭可行不等式与局部紧性不能断定标号正确。
快速检查
(所有弧权为一时,说明带权距离为何等于 BFS 层数。再分析 、 的反例。)
解答
单位权时,每条游走的长度就是弧数,最小化两者是同一件事。因此真实带权距离等于 BFS 已证明的可达层数;不可达点按两种约定都是无穷。
所给带权图中,BFS 将直达弧 看成一条边的路线,但其费用为四。经过 的两条边费用二,反而更便宜。带权距离必须比较累计费用,这正是暂定标号所保留的信息。