到某个顶点的一条暂定路线给出的是最短路径距离的上界,并不自动成为最终答案。Dijkstra 算法指出了何时可以安全地确定一个这样的上界:选择当前暂定距离最小的未确定顶点。边权非负保证了之后经过未确定区域的路线不可能改进这个选择。
数学上的选择与优先队列的实现紧密相关,但并不是同一件事。由于一条旧路线可能被更短的路线取代,堆中可能同时保存同一顶点的多条记录。我们先证明贪心步骤,再说明哪些记录仍然有效、何时可以提前停止,以及存在平行边或零权重环时前驱边如何仍能准确记录路径。
定义图和暂定距离
定义 7.2.1
(非负权有向最短路径)
设 的顶点为 ,其中 ,源点为 。每条边的权重都是非负整数。允许有向平行边和自环,每条边的编号是它在固定输入边列表中的位置。
用 表示从源点到 的最小路径权重;若不存在这样的路径,则记为 。源点的距离为零,由空路径给出。由于所有边权非负,删除一个环不会增加游走的权重,因此每个可达顶点都存在一条最短简单路径。
初始化 ,其余暂定标号均为 。处理有限标号的顶点 时,对权重为 的出边进行松弛:检验 是否成立。若成立,就用这个候选值替换 ,并记下产生改进的边。
引理 7.2.2
(标号是上界)
在算法的任何时刻,对每个顶点 都有 。
证明
(每个有限标号都有见证游走)
每个有限标号都是某条已发现的源点游走的权重。源点的零标号如此;松弛时,用 取代 ,它是取得 的游走再接上一条边的权重。任何游走的权重至少为 ,所以候选值可能大于真实最优值,但不可能小于它。无穷标号显然满足不等式。
定义 7.2.3
(已确定顶点)
当顶点的标号已证明为最终值,即 ,它就称为已确定,其出边只扫描一次。未确定顶点的标号仍是暂定的,即使已经被多次改进。
证明最小的当前标号为何是最终值
定理 7.2.4
(最小的未确定标号就是最终值)
设所有边权非负。每当算法确定顶点 (它被选为未确定顶点中有限标号最小者)时, 的标号在该时刻等于 。
证明
(跨过已确定区域的边界)
归纳基础是源点:它的标号为零,而非负权游走的权重不可能更小。假设此前每个已确定顶点的标号都等于其真实距离。令 为暂定标号最小的有限标号未确定顶点。由于它的有限标号由一条源点游走给出,它必然可达。
取一条从 到 的最短路径,令 为路径上第一个未确定顶点,其前驱 必然已经确定。最短路径的前缀本身也是最短路径;否则替换该前缀就会得到一条更短的从源点到 的游走。当处理 时,对它通往 的边进行松弛,因而得到
结合上界不变量,可知 。从 到 的剩余路径权重非负,因此 。由于 的未确定标号最小,
所有不等式都必须取等号,所以 。确定 后,归纳结论仍然成立。
证明透视
每个不等式由哪项事实收尾
不等式链用到四项各自独立的事实。所选标号的最小性给出 ,因为 未确定而且标号有限。把归纳假设用于已确定的前驱 ,再加上上界引理,就得到精确值 。非负性只用一次,说明从 到 的后缀不会降低权重,即 。上界引理以 把链首尾相接。
不明显的一步是讨论边界顶点 ,而不是 本身。 的标号可能经由未确定顶点形成,直接看不出什么。 恰在已确定区域之外一步,松弛已经完成,而且它在通往 的最短路径上。链由 出发,又回到 ,所以每个不等式都必须取等。如果后缀可以有负权重,中间的不等式就不成立,下面的反例正是这种情形。
证明讨论的是具有有限标号的可达顶点。如果算法已无有效的当前堆记录,那么不存在尚未确定的可达顶点:否则,一条从源点到该顶点的路径必然会从已确定顶点跨到未确定顶点,对跨界边的松弛便会赋予后者有限标号并留下待处理记录。不可达顶点永远不会被确定,并保留表示无穷大的标记。
反例模式
负边会破坏非负后缀的论证
考虑边 ,权重为一;边 ,权重为四;边 ,权重为 。贪心算法会先以距离一确定 ,再处理 ;但到 的最短路线权重是 。
这里根本没有有向环。问题在于负边:从未确定路径顶点出发的后缀可能降低路径权重,因此贪心证明中间的不等式不再有依据。下方实现会拒绝每一条负权输入边,包括从所选源点无法到达的边。Bellman–Ford 算法处理的是另一类边权情形。
区分当前标号与堆记录
定义 7.2.5
(堆记录、有效与过时)
堆记录 表示此前某个时刻曾发现一条到 、长度为 的路线。如果 并且 尚未确定,记录称为有效,否则称为过时。过时记录未必等于当前标号 。
惰性实现不会在路线改进时修改已有堆项,而是插入新记录,让旧记录留到之后被弹出时丢弃。
从堆中取出记录时,只有当其键仍等于当前暂定标号、且顶点尚未确定时,才能据此确定该顶点。扫描出边之前,会跳过所有过时记录和已确定顶点的记录。
定理 7.2.6
(惰性记录保持贪心选择)
每当循环取出一条未被跳过的堆记录 ,就有 ,并且 在未确定顶点中标号有限且最小。
证明
(每个未确定标号都有仍在堆中的记录)
每当标号变为有限或得到改进,就插入 。记录只会因被取出而离开堆,而通过两项检查的取出记录会确定其顶点。因此,每个标号有限的未确定顶点,其记录 仍在堆中。堆给出最小记录,所以通过两项检查的取出记录,对每个这样的 都满足 。特别是 , 达到最小值。
例题 7.2.7
(几次改进后旧堆键仍然存在)
取源点 0 和顶点 ,固定边列表如下:
| 边编号 | 有向边 | 权重 |
|---|---|---|
从 0 到 1 的两条边是不同的记录。顶点 3 和 4 构成零权重环,顶点 5 不可达。堆中权重相同时按顶点编号排序。
| 被确定的顶点 | 确定后按顶点顺序排列的标号 | 主要改进 |
|---|---|---|
| 顶点 1 的标号先变为 8,再变为 5 | ||
| 顶点 1 的标号改进为 3 | ||
| 顶点 3 和 4 的标号改进 | ||
| 零权边改进顶点 4 的标号 | ||
| 没有严格改进 |
确定顶点 1 后,旧记录 仍在堆中;由于按顶点编号打破平局,它会先于 被取出。这条记录已经过时,不会使顶点 1 的出边再次被扫描。记录 、 和 最终也会被跳过。表中记录的是确定顶点的步骤,并非每一次弹堆。
最终的前驱边编号为 。到顶点 4 的路线使用边编号 ,即 ,权重为 。
零权重平局不要求在距离相等时重写前驱
使用严格改进条件。如果另一条路线长度恰好等于当前长度,就保持标号和前驱不变。这样能找到一条最短路径,但不会枚举所有最短路径,也不保证所得路径的字典序最小。
定理 7.2.8
(前驱链通回源点)
算法结束后,对每个可达的非源点 ,沿前驱边从 走去,每一步都到达更早确定的顶点,并最终到达 ;即使有些边权为零也是如此。
证明
(前驱先被确定)
在这个实现中,只有已确定顶点能发起松弛,并且已确定的目标顶点会被跳过。因此,未确定顶点每次获得前驱边时,其前驱都已经确定。如果它在被确定之前又更换了前驱,新前驱仍然比它更早确定。
算法结束后,从每个可达的非源点沿前驱边走一步,都会到达一个更早确定的顶点。即使某些边权为零,沿前驱边追溯也不可能成环。由于源点是唯一没有前驱的可达顶点,这条链最终必然到达源点。
存在平行边时,应保存前驱边编号,而不仅是前驱顶点编号。端点相同的两条边可能权重不同,所以仅给出顶点序列未必能确定松弛时实际选中的路径凭证。
完整的惰性堆实现
输入是固定的有向边三元组列表 (from_vertex, to_vertex, weight),约定顶点编号和权重均为有效整数。None 表示距离不可达,与合法的零距离区分开来。搜索前会校验所有边的端点范围和非负权重;代码假定输入满足整数类型约定。Python 整数使示例中的加法保持精确。
from heapq import heappop, heappush
def dijkstra(n, edges, source):
if n < 1 or not 0 <= source < n:
raise ValueError("a positive vertex count and valid source are required")
edges = tuple(edges)
adjacency = [[] for _ in range(n)]
for edge_id, (u, v, weight) in enumerate(edges):
if not 0 <= u < n or not 0 <= v < n or weight < 0:
raise ValueError("edge endpoints must be valid and weights nonnegative")
adjacency[u].append((v, weight, edge_id))
distance = [None] * n
predecessor = [None] * n
settled = [False] * n
distance[source] = 0
heap = [(0, source)]
while heap:
candidate, u = heappop(heap)
if settled[u] or candidate != distance[u]:
continue
settled[u] = True
for v, weight, edge_id in adjacency[u]:
if settled[v]:
continue
proposal = candidate + weight
if distance[v] is None or proposal < distance[v]:
distance[v] = proposal
predecessor[v] = edge_id
heappush(heap, (proposal, v))
return distance, predecessor
def restore_path(edges, predecessor, source, target):
if target == source:
return []
if predecessor[target] is None:
return None
path = []
while target != source:
edge_id = predecessor[target]
path.append(edge_id)
target = edges[edge_id][0]
return path[::-1]
调用 restore_path 时,须传入未改变的原边列表、同一次搜索得到的前驱数组及有效目标。源点返回空列表,不可达目标返回 None,可达目标按正向顺序返回边编号。耗时与路径长度成正比,至多 条边。
在上面的例图中,dijkstra(6, edges, 0) 返回距离 [0,3,2,5,5,None] 和前驱 [None,3,1,5,7,None]。重建到目标 4 的路径得到 [1,3,5,7];目标 5 的结果为 None。
例题 7.2.9
(最小的例子与零权自环)
取 ,源点 ,唯一的边为 ,即权重为零的自环。堆从 开始。取出该记录就确定顶点 ;扫描自环时,发现目标已确定而跳过,所以没有插入新记录。结果为 distance = [0] 与 predecessor = [None],对目标 ,restore_path 返回空列表。零距离是真实的值,与不可达标记 None 不同。
在目标被确定时停止,而非首次发现时停止
反例模式
首次发现的目标路线可能长得多
考虑边 ,权重为九;边 ,权重为二;边 ,权重为一。处理源点时会以标号九发现目标 。如果一发现目标就停止,答案便是错误的;经过 的路线长度为三。
如果只需要目标距离,那么根据贪心证明,在一条有效的当前记录使目标被确定时停止是正确的。然而,此时其他未确定顶点的标号未必是最终值。支持提前停止的接口不能将整个暂定数组都作为已完成的最短路径答案呈现。上面的函数刻意运行至搜索结束。
例题 7.2.10
(在确定时正确停止)
取边 权重九、 权重二、 权重一,堆从 开始。确定 时插入 和 。接着取出 并确定 ;候选值 改进 ,插入 。此时 是最小记录且通过两项检查,所以 以距离三被确定,只求目标的搜索可以停止。记录 仍留在堆中,已经过时,从不会被检查。
除顶点数外还要统计堆记录
令 为输入边记录的数量。
命题 7.2.11
(惰性堆实现的成本)
该实现最多插入 条堆记录,时间为 ,空间为 ,包括邻接表和堆。
证明
(统计确定、松弛与记录的次数)
初始化和校验需要 次操作。每个顶点至多被确定一次,因此每条出边至多被扫描一次。成功的松弛至多有 次,因而包括源点在内,至多插入 条记录。每条记录至多被取出一次,每次花费 。
惰性堆可能包含 条记录,而不是每个顶点仅一条。多重图中任意多条平行边可以使 很大而 仍很小,因此不能仅凭顶点数就假设每次堆操作的界为 。
例如,在只有两个顶点的图中,按权重严格递减的顺序列出从源点到目标的平行边。扫描源点时,每条边都会改进目标标号,而此时尚未取出任何目标记录,因此这些记录会同时留在堆中。使用 decrease-key 操作的索引优先队列则需要另一套存储和操作分析。
上述界按算术操作和比较操作计数;定宽整数的加法不能悄然溢出。无论选用哪一种合适的队列,正确性都依赖非负权重、选取当前最小标号,以及区分暂定与已确定状态。
常见错误
常见错误
(用真假值检查距离)
把 distance[v] is None 写成 not distance[v],会把合法的距离 当作不可达。取源点 和边 、、,确定顶点 时,正确的 会被改写成 ,顶点 于是以距离 而不是 被确定。
常见错误
(对已确定顶点接受等长候选)
假设更新条件改为 proposal <= distance[v],并且不跳过已确定的目标。对零权边 、、,确定 时会把 的前驱改写成边 。从 出发的前驱链就在 与 之间来回,永远到不了 ,路径重建不会终止。严格比较加上已确定检查可排除这种情况。
练习与详解
快速检查
(重建多重图中的精确路径凭证)
对于例图,给出到顶点 4 的最终距离,以及正向排列的前驱边编号链。存在平行边时,为什么仅保存前驱顶点编号提供的信息较少?
解答 · 答案
距离为五。边编号 给出 ,相应权重为 。同一对顶点之间可能有多条权重不同的边记录,因此边编号可以确定实际选中的凭证,而不只是其顶点序列。
快速检查
(选择正确的目标停止条件)
对于边 、 和 ,当 首次获得有限标号时就停止有什么问题?只求目标距离的搜索何时可以安全停止?
解答 · 答案
首次标号为九,但经过 的最短路线长度为三。跳过过时或已确定的提议后,当目标作为有效的当前最小记录被取出并确定时,只求目标距离的搜索可以停止。此时其余暂定数组并不因此被证明已经完成。
快速检查
(理解过时的堆提议)
顶点 1 的标号已改进为三,堆中仍有 。取出该记录时应当再次扫描顶点 1 的出边吗?如果实现保留了已确定检查,堆键相等检查是否本身就是正确性所必需的?
解答 · 答案
应跳过,不再扫描。采用严格改进和最小堆时,更小的新记录必先于旧记录取出,所以已确定检查已能防止重复扫描;显式相等检查只是清楚地确认提议仍为当前值,在该实现中并非独立必需。
快速检查
(解释零权重环为何不会使返回路径成环)
例中顶点 3 和 4 之间双向都有零权边。为什么沿返回的前驱边追溯仍不可能绕圈?代码如何处理等长的候选路线?
解答 · 答案
每个选中的前驱都比当时未确定的目标更早确定。因此,前驱链严格沿确定顺序向后追溯,不可能成环。代码跳过已确定的目标,只接受严格改进,所以等长提议不会改变前驱,源点作为空路径的根也保持不变。
快速检查
(用正确的参数界定惰性堆)
只有两个顶点时,若按权重递减顺序列出从源点到目标的 m 条平行边,处理完源点后可以同时存在多少条目标记录?为什么顶点数不能界定这个堆的存储量?
解答 · 答案
全部 条都可能同时存在,因为每条边都在下一次弹堆之前改进标号并插入新记录。惰性插入保留已被取代的提议,所以存储量取决于边记录数。一般的对数堆界使用 ;每顶点一项的 decrease-key 实现是另一种数据结构。
快速检查
(区分零距离、不可达和禁止的权重)
若 的权重为零,而 b 不可达,函数对 s、a 和 b 应分别返回什么距离标记?按照给定的输入约定,不可达连通部分中的负边是否可以接受?
解答 · 答案
返回值依次为零、零和 None。零权重路线是一条真实的有限最短路径,而不是无穷大标记。即使负边不可达,函数也会拒绝它,因为约定要求每条输入边非负,并且校验发生在遍历之前。