一个图可以支持若干不同的问题。哪些顶点可达?最短路线使用多少条边?一条路线的最小总边权是多少?哪些边能以最低代价把整个网络连通?图形相似并不意味着这些问题可以互换。要理解相应的算法,最好的办法是为每一个前沿、每一个距离标号和每一条被选中的边赋予精确的含义。
动机
设想顶点是地点,边是允许的移动。当每次移动的代价相同时,按发现顺序处理顶点,自然会依次揭示越来越长的路线长度。当代价不同时,仅凭发现顺序就不够了:一条昂贵的单边路线可能输给一条廉价的多边路线。此时必须用优先规则来追踪暂定的总代价。
生成树问题再次改变了目标。它对一组边只付一次费用,使所有顶点连通起来,而不是使每位出行者到选定源点的距离最小。建造代价最低的网络,可能迫使某些顶点之间的行程更长。说明这一区别,可以防止把最短路径算法误用为最小生成树算法这一常见错误。
这三个问题都可以从前沿的角度来看。BFS 把已处理的层与尚未发现的顶点分开。Dijkstra 把距离已经最终确定的顶点与只有暂定标号的顶点分开。生成树算法则把各个连通分量或一棵不断生长的树与其余部分分开。不同之处在于:如何证明以所提出的方式越过前沿是安全的。
定义
定义 4.5.1
(游走、路径与可达性)
有限有向图具有顶点集 和有向边集 。无向边在不指定方向的情况下连接两个顶点;在遍历时,它可以用两个有向关联来表示。游走(walk)沿着相连的边前进,可以重复经过顶点。路径(path)指没有重复顶点的游走。若存在从 到某顶点的游走,则称该顶点从 可达;当可达性成立时,删去重复的闭合部分即可得到一条路径。
定义 4.5.2
(无权距离与 BFS)
在无权图中,距离 是从 到 的游走所含边数的最小值;若不存在这样的游走,则为无穷大。BFS 使用先进先出的队列。它令 ,将 标记为已发现,然后反复取出队首顶点 。每个尚未被发现的邻点 立即被标记,赋予 和父结点 ,并加入队尾。
定义 4.5.3
(带权距离与 Dijkstra 算法)
对于带权图,一条游走的权是其各边权之和。Dijkstra 算法假设每条边的权都是非负的。它初始化 ,其余标号为无穷大。算法反复选取一个标号有限且最小的未确定顶点,将其确定,并松弛它的出边:若 ,则替换后者的标号并记录父结点 。当不再有标号有限的未确定顶点时停止。带权距离 是从 到 的游走的权的最小值;若不存在这样的游走,则为无穷大。
定义 4.5.4
(生成树、最小生成树与割)
对于连通的无向图,生成树是包含所有顶点的连通无环子图,它有 条边。最小生成树(minimum spanning tree,简称 MST)使其边权之和最小。MST 的边权可以为负:与最短游走不同,树不能重复经过负环。图的割是把顶点划分为两个非空部分。若一条边的两个端点分属不同部分,则称该边横跨此割;若边集中没有边横跨该割,则称该边集与此割相容。
定理/命题
定理 4.5.5
(BFS 计算无权距离)
在以邻接表表示的有限图中,BFS 恰好发现从源点可达的那些顶点,并为每个顶点赋予其最小边数距离。每个顶点至多入队一次,包括初始化在内的运行时间为 。
定理 4.5.6
(Dijkstra 算法中已确定的标号是最终的)
对于边权非负的有限有向图或无向图,Dijkstra 算法所确定的每个顶点都满足 ,其中 为带权距离。算法终止时仍为无穷大的顶点是不可达的。
定理 4.5.7
(最小生成树的割性质)
设 为连通的有限无向带权图, 为包含于某棵 MST 的边集。取定一个割,即把顶点划分为两个非空部分,且 中没有边横跨该割。若 是横跨该割的权最小的边,则存在一棵包含 的 MST。特别地,横跨割的最轻边属于某棵 MST,但在出现权相等的情形时,它不一定属于每一棵 MST。
在安全边的表述中,“先前的选择”被假定包含于至少一棵 MST,并且割必须与它们相容,即其中没有边横跨该割。在算法中反复使用割性质时,必须明确这一不变量。
证明思路或证明
证明
(BFS 标号等于距离)
BFS 队列中的标号从队首到队尾是非递减的:处理一个标号为 的顶点,至多只会在当前队列中所有标号为 的顶点之后追加标号为 的顶点。每个被赋予的标号都由其父结点链实现,因此不会小于真实距离。反之,取一个真实距离为 的顶点及到它的一条最短路径。其前驱的距离为 ,由对 的归纳,它被处理时带有正确的标号。该顶点要么已被发现且标号至多为 ,要么此时被发现并获得标号 。结合由路径实现的不等式,便得到等式。可达顶点都出现在某个有限的路径长度上,所以归纳法保证它们全部被发现;不可达顶点不可能获得从 出发的父结点链。
证明
(被选中的标号已经精确)
对于 Dijkstra 算法,每个有限标号都是某条源点游走的权,所以 。假设所有先前已确定的标号都是正确的,并设 是下一个被选中的顶点。在到 的一条最短路径上,令 为第一个未确定的顶点,其前一个顶点 已确定;若在初始步骤中 ,则另当别论。从 出发的松弛给出 ,因此等式成立。其余各边非负,给出 。所选标号的最小性给出
因此所有不等式都是等式, 被正确确定。源点是归纳的起点。每个可达顶点都存在最短路径:在权非负时,去掉环不会增加权,所以最小值可以在有限多条简单路径中取得。若某个可达顶点仍为无穷大,则一条路径上第一个未被发现的顶点会从其已确定的前驱得到一次有限的松弛,这与算法终止矛盾。
证明透视
非负性在哪一步起作用
两个不等式确定一个已确定标号。容易的一个是 ,因为有限标号是某条真实游走的权。困难的一个是 ,它来自到 的一条最短路径上第一个未确定的顶点 :取第一个未确定顶点,就保证它之前的顶点都已确定,所以 是由正确标号松弛而得,;又因 在未确定顶点中标号最小,故 。非负性恰好只在链中的一环起作用,即 :从 到 的其余路径不能有负权。在下面的负边反例中, 先被选中,它的最短路径上第一个未确定的顶点是 ,这一环便失效:。
证明
(以最轻的横跨边交换较重的横跨边)
对于割性质,先取一棵包含先前选择的 MST。若它含有所提出的横跨边 ,则无需再做什么。否则,加入 会产生唯一一个环:原树在 的两个端点之间已有唯一一条路径。这条路径横跨该割,所以该环含有另一条横跨边 。因为割与所有先前的选择相容, 不是其中之一。删去 ,得到的是一棵保留先前选择并含有 的生成树。由于 是横跨边中最轻的,,所以新树的权不大于原树。由最小性,它是一棵 MST。这是一个交换论证,其可行性由环的替换来保证。
Prim 算法从一个顶点出发,反复选取从其不断扩大的顶点集通向外部的最小权边。其割与所有先前选中的边相容,所以割性质保持了“已选森林可扩展为一棵 MST”这一不变量。Kruskal 算法按权从小到大处理各条边,仅当一条边的两个端点属于当前不同的分量时才加入它。对于被加入的边,把其中一个分量与其余部分分开的割是相容的,而且在不同分量之间不可能有更轻的横跨边曾被拒绝。同一个不变量即可证明其正确性。每次成功加入一条边都会使分量数减少,所以对连通的输入,最终得到一棵生成树。
例题详解
例题 4.5.8
(按边数与按权计算的距离)
考虑无向图,其边为 、、、、、、、。从 出发的 BFS 给 赋距离零,给 赋距离一,给 赋距离二。Dijkstra 则按 的顺序确定顶点,带权距离依次为 。到 的最便宜路线是 ,使用四条边。存在一条两条边的路线,但其权为十一,所以对 BFS 自身的目标而言正确的答案,并不是带权最短路线。
例题 4.5.9
(最短路径树不一定是 MST)
取三个顶点,边权为 、、。以 为根的最短路径树使用两条源点边,总边权为四。MST 使用 和任一条源点边,总权为三。在该 MST 中,源点到某个顶点的距离变成三,而不是最优的二。使建造代价最小与使源点距离最小,对同一个图提出了不同的要求。
例题 4.5.10
(带权图上的 Kruskal 算法与被拒绝的边)
在第一个例题的图上,把边排序:、、、、、、、。取 :它连接分量 与 。取 :它连接 与 ;两条权为一的边互不相交,所以先后次序不影响结果。取 :它把 与 连起来。把 与其余顶点分开的割,被 、、 和 横跨,而 最轻,正符合割性质的要求。取 :它把 并入其余部分,此时森林有 条边,总权为 。其余的边 、、、 的两个端点都在唯一的分量内,加入会形成圈,所以 Kruskal 算法拒绝它们。被拒绝的边就是边界情形:只要端点已经连通,不论边的权是多少,这条边都会被舍弃。
反例模式
负边使永久确定失效
一个看似合理的说法是:只要图中没有负环,Dijkstra 的规则就能给出正确的距离。取有向图: 的权为二, 的权为五, 的权为负四。它完全没有圈。第一轮松弛后的标号是 、,所以 Dijkstra 确定 ,标号为二。接着它确定 ;松弛 本会给出 ,但 已经确定。游走 的权为一,所以 。修正的办法是对这种确定规则要求边权非负。有负边时,需要一个可以重新访问已确定标号的过程,那就不再是上面所证明的算法了。
使用邻接表时,BFS 对每条有向边扫描一次(无向边的每个关联扫描两次),对每个顶点扫描一次。Dijkstra 的简单数组实现通过扫描所有顶点来找出每个最小值,共需 次运算。使用二叉堆并配合适当的减键(decrease-key)实现,对非平凡的图需要 次运算。Kruskal 算法需要对边排序并维护分量;即使是简单的分量实现也是多项式时间的,而不相交集合结构可以改进分量操作。这些代价假定对边权的比较和算术运算的代价为常数。编码很长的精确有理数权,则需要另行做比特代价分析。
常见错误
常见错误
(只在出队时才标记 BFS 的顶点)
若要使用“只入队一次”的不变量,应当在入队时而不是仅在出队时标记 BFS 的顶点。否则,在某个顶点被处理之前,可能有多个邻点把它重复入队。这样得到的过程也许仍可修复,但其状态和代价证明都已改变。
常见错误
(把割的证明套用到不连通或有向的图)
对于不连通的输入,覆盖所有顶点的 MST 并不存在;自然的类比是最小生成森林,每个连通分量一棵树。有向图中的最小代价连通问题也不同于无向 MST 问题。当有向可达性取代了无向连通性时,不要不加说明地套用割的证明。
常见错误
(以为最轻的边必属于每一棵 MST)
权相等可以产生多棵 MST。割性质保证的是存在一棵包含所选最轻边的 MST,而不是在存在权相等的替代边时该边属于每一棵 MST。在三条边权都是一的三角形中,任意两条边都是一棵 MST,所以每条边都会被其中一棵 MST 舍去。如果某个割有唯一的最轻边,则交换论证可以加强,证明它属于每一棵 MST。
总结
BFS 使用层,因为每条边贡献一个单位。Dijkstra 使用暂定权重,并且需要边权非负,才能最终确定前沿中的最小值。MST 算法最小化的是整个边集的全局代价,并使用割与环的交换。数据结构实现这些想法;而不变量则解释了所得答案为何能解决所述问题。
练习
快速检查
(求“按边数与按权计算的距离”例题中五顶点图的一棵 MST,并给出其总权。)
把边排序,并跳过会形成圈的边。
解答 · 答案
选取权为一的 、权为一的 、权为二的 和权为三的 。这些边连通全部五个顶点且没有圈,总权为七。每一步都套用割性质(如 Kruskal 例题所示),就保证了最小性。在这个例子中,所选的四条边恰好也构成从 出发的带权最短路径树,但第二个例题表明这种巧合并不具有一般性。
练习 4.5.11
(证明横跨某个割的唯一最轻边属于每一棵 MST。)
核心证明
设 为连通的带权无向图, 是横跨某个固定割的唯一权最小的边。
解答(3)
- 1
假设某棵 MST 不含
是生成树,所以在 的两个端点之间有唯一一条路径。把 加入 恰好产生一个圈。
- 2
在该圈上找出另一条横跨边
关键一步
这个圈含有横跨该割的 ,所以还含有另一条横跨边 。因为 是唯一的最轻横跨边,。
依据: 圈横跨一个割的次数是偶数。
- 3
交换两条边并与最小性矛盾
∎从唯一的圈中删去一条边,余下的仍是生成树,所以 是生成树,且 。这与 的最小性矛盾,所以每棵 MST 都含有 。严格不等式正是权相等时所不具备的额外事实。
快速检查
(解释为什么当图中所有边的权都相同且为正时 BFS 是有效的,并说明如何由其输出得到带权距离。)
比较一条游走的权与它所含的边数。
解答 · 答案
若每条边的权都是 ,则含 条边的游走的权为 ,所以最小化权等价于最小化边数。把每个有限的 BFS 距离乘以 ;不可达的顶点仍为无穷大。 的情形很平凡:所有可达顶点的带权距离都是零。
快速检查
(在负边的例题中,计算正确的距离,并指出 Dijkstra 归纳中恰好是哪一步失效。)
找出到 的真实最短路径上第一个未确定的顶点。
解答 · 答案
距离为:到 为零,到 为五,到 为一。当 先于 被选取时,到 的真实最短路径上第一个未确定的顶点是 ,其距离五大于最终的路径成本一。因此后缀不等式 不成立,因为该路径的最后一条边权为负。