动机
没有环的有向图具有一种特殊的处理顺序:每条边都指向前方。一旦顶点按这种顺序排好,最短路径算法就可以在某个顶点的所有可能前驱都处理完之后,再确定该顶点的结果。由于后面的边不可能再回到前面的顶点并修改其结果,所以允许出现负边权。
本章证明两部分内容:如何得到拓扑序或检测出有向环,以及为什么按该顺序对各边做一遍松弛就能求得最短路径。拓扑排序失败,就是一份结构性证明,说明一遍扫描算法的前提不成立。
定义
定义 3.4.1
(拓扑序与 DAG)
设 为有限有向图,有 个顶点和 条边。拓扑序是对所有顶点的一种排列,使得每条边 中 都排在 之前。有向无环图简称 DAG。自环是一个有向环;平行边是允许的,并且在计算入度时分别计数。
定义 3.4.2
(Kahn 算法)
Kahn 算法先计算各顶点的入度,把所有入度为零的顶点放入队列,然后反复取出一个队列中的顶点并输出。对于该顶点的每条出边,算法将其头部顶点的当前入度减一,当计数变为零时把该头部顶点加入队列。这些计数针对的是由尚未移除的顶点所导出的子图。如果输出的顶点少于 个,算法就报告存在环。
定义 3.4.3
(源点标号与松弛)
对于最短路径,假设每条边都有有限实数权重,并且给定了源点 。初始化 ,其余所有标号为 。按拓扑序处理各顶点;对每条出边 ,把 替换为 。约定 仍为 。
定理
定理 3.4.4
(拓扑排序与环)
有限有向图存在拓扑序,当且仅当它无环。Kahn 算法在 DAG 上输出这样的拓扑序,否则报告存在环。
定理 3.4.5
(DAG 中的最短路径)
在带权 DAG 上,一遍拓扑松弛算法可以求出源点到各顶点的最短距离(不可达顶点的距离为 )。在图以邻接表表示之后,所需时间为 。
证明
证明:源点与队列
证明
(DAG 必有源点,Kahn 算法输出拓扑序)
有限非空的 DAG 必有入度为零的顶点。否则,从任一顶点出发,反复沿一条入边向后走。由于顶点只有有限个,必有某个顶点重复出现,重复的那一段就给出一个有向环。从 DAG 中移除一个入度为零的顶点,所得仍是 DAG,所以在无环图中,只要还有顶点剩余,Kahn 算法的队列就不会变空。
当一个顶点被移除时,它的当前入度为零,因此它的所有前驱都已被移除。所以,对于完全输出的图,每条边在输出顺序中都指向前方。反过来,含有有向环的图不可能有拓扑序:沿着环上的边走,要求环上每个顶点都排在下一个顶点之前,最终将要求某个顶点排在它自己之前。
证明
(提前停止会暴露一个环)
如果 Kahn 算法提前停止,则剩余子图非空,并且其中每个剩余顶点在该子图内的入度都为正。沿入边向后走必然重复某个顶点,从而暴露出一个有向环。因此提前停止的判断是正确的。未处理的集合中可能含有不在环上的顶点;证明所保证的是,其中至少包含一个环。
证明:拓扑松弛
证明
(拓扑松弛求出最短距离)
每个有限的暂定标号都是某条真实的源点到该顶点路径的权重:初始时只有到 的空路径,权重为零;而每次松弛都是在一条已被表示的路径后追加一条边。因此,没有任何有限标号会小于真实的最短路径距离。
按拓扑序考察各顶点。在处理顶点 之前,它的每个入邻点都已被处理,所以它的每条入边都已被松弛过。若 可达且不是 ,取一条到 的最短路径,设 是该路径上 的前驱。DAG 中的有向路径不会重复顶点。该路径到 的前缀是一条源点到 的最短路径;否则,把这段前缀换成更短的路径,就会得到一条到 的更短路径。由归纳假设, 被处理时 已经正确,所以对 的松弛使 不超过最短距离。路径见证不变量给出相反的不等式,因此二者相等。
对于 ,空路径的权重为零,并且在 DAG 中没有有向路径能回到 。从 不可达的顶点永远得不到有限的路径见证,因此保持为 。负权重不会给归纳带来任何困难:保证每个相关前驱先被处理的是拓扑序,而不是“最小标号优先”的规则。
证明透视
为什么一遍扫描就够了
归纳沿着拓扑序进行,而不是沿着距离的大小进行。无环性用了两次:第一,它提供了次序,所以在处理 之前,进入 的每条边都已被松弛;第二,它使每条路径都是简单路径,所以到 的最短路径存在,而且它到前驱的前缀仍是最短路径。“每个有限标号都是某条真实路径的权重”这一不变量使 恒成立,其中 是真实距离。某条最短路径的最后一条边在其尾部顶点定案之后被松弛,就给出 。权重的正负号在两个不等式中都没有出现,所以负边是无害的。若没有无环性,消失的是次序:在环上,没有任何顶点可以排在它所有前驱之后处理。
时间与路径重构
Kahn 算法通过扫描一遍所有边来计算入度。每个顶点至多入队和移除一次,每条边在其尾部顶点被移除时被扫描一次。使用邻接表时,其时间和空间均为 。松弛过程同样对每个顶点和每条边各扫描一次,因此包括拓扑排序在内,总时间为 。
每当 被严格改进时,记录 以及边 作为前驱。对于可达且 的顶点,沿前驱回溯会在拓扑序中不断向前移动,因此一定会终止于 。把所记录的边反向排列,就得到一条最短路径。当代价相等时保留已有的前驱,可以避免不必要的改动;如果需要精确的边序列,则应当分别标识各条平行边。
例题详解
例题 3.4.6
(负边是无害的)
设有三条边: 权重为二, 权重为五, 权重为 。按顺序 ,处理 时得到 与 。处理 时把 改进为 。之所以允许出现负边,是因为该图是无环的。
例题 3.4.7
(源点不必排在第一位)
若 是一条边,但 从 不可达,则拓扑序可以把 排在 之前。它的标号保持为 ,所以松弛它的出边不会改变 。源点不必是拓扑序中的第一个顶点。
例题 3.4.8
(环阻碍了拓扑序)
对于边 、 和 ,每个顶点的入度都为正。Kahn 算法的初始队列为空,没有任何顶点被输出。这三条边构成一个有向环,所以不存在拓扑序。
例题 3.4.9
(入度为零的并列情形)
对于边 和 , 与 的初始入度都为零,可以先移除其中任何一个。 与 都是合法的拓扑序;算法并不要求拓扑序唯一。
常见错误
反例模式
负边并不总是需要多遍扫描
在上述无环例子中, 的权重为 ,但一遍拓扑扫描就得到了正确的值 。Dijkstra 算法对非负权重的要求,源于它按最小标号确定顶点的证明;DAG 则提供了另一种顺序,即使有负边,这种顺序仍然有效。
常见错误
(提前停止并不表示所有剩余顶点都在环上)
Kahn 算法提前停止,证明的是剩余子图含有环,而不是每个未处理的顶点都在某个环上。位于环下游的顶点可能保持未处理,但它本身并不属于任何环。
反例模式
按非拓扑序进行松弛
考虑这样的说法:只要每个顶点处理一次,一遍松弛在任何 DAG 上都是正确的,不论采用什么次序。取边 权重为 , 权重为 , 权重为 , 权重为 ,并按次序 处理各顶点。处理 得 、。处理 得 。处理 把 降为 ,但 已经处理过,所以 仍为 。处理 没有任何变化。真实距离是 。次序 把 排在它的前驱 之前,所以不是拓扑序。在拓扑序 之下,标号依次成为 、、。修正后的说法需要拓扑序,使每个顶点都在它所有前驱之后处理。
常见错误
(次序取决于边,而不是权重)
拓扑序是有向图本身的性质,与边权无关。改变权重不会使拓扑序失效,而加入一条反向边则可能产生环,使拓扑序不再成立。例如 是路径 的拓扑序,但加入边 之后就不存在任何拓扑序。
提前停止后提取一个明确的环
如果 Kahn 算法的队列变空而仍有顶点剩余,就为每个剩余顶点选定一条剩余的入边。这是可以做到的,因为每个剩余顶点的入度都为正。从任一剩余顶点出发,反复沿所选的入边向后走,并记录每个顶点第一次出现的位置。至多经过 次访问,必然出现重复。
按所记录的边的正向读取,重复的那一段就是一个有向环。例如,反向遍历可能依次访问 ,所用的边为 、 和 ;把这些边按正向读出,就是 。自环是长度为一的环。为每个顶点找出一条剩余入边,可以在提前停止后通过扫描原始边表完成,所以提取环仍然只需 时间。
环下游的顶点说明了为什么整个未处理集合不能充当环的证明。在环 上加一条边 。初始时没有任何顶点的入度为零,所以四个顶点全部留下。如果 没有出边,它就不在任何有向环上,但剩余子图含有由 构成的环。
DAG 中的最长路径
同一个拓扑序也可以用来计算 DAG 中的最长路径权重。初始化 ,其余标号为 ,然后在处理出边时,把头部标号替换为 。每个有限标号都是某条路径的权重,同样的前驱归纳法在不等号反向后证明其最优性。不可达顶点以 作为哨兵值保持不变。
DAG 只有有限多条有向路径,所以即使某些边的权重为正,可达的最长路径也存在。这一结论不能原样推广到任意图:若存在一个可达的正权环,并且该环能到达目标顶点,则存在权重无界的游走。如果问题要求的是有环图中的最长简单路径,则禁止重复顶点会改变问题本身,DAG 上的一遍扫描证明不再适用。
对于边 权重为二、 权重为五、 权重为 ,到 的最长距离为五,而最短距离为 。这两种算法使用同一个拓扑序,但更新运算相反。不可达标号也必须使用正确的哨兵:求最小值时用 ,求最大值时用 。
并列、多重边与算术运算
一个图可以有许多种拓扑序。每一步都可以选取任一入度为零的顶点,正确性证明对所有选择都成立。如果有多条最短路径权重相同,不同顺序得到的前驱路径可能不同,但每个报告出来的有限距离都是同一个最优值。
存在平行边时,入度计数要包括每一条边的副本。移除它们共同的尾部顶点时,头部顶点的入度对每个副本各减一次,而松弛时则分别检查每个权重。如果把两个副本只算作一次入度贡献,却减了两次,队列的记账就可能出错。自环使其所在顶点的入度永远不能降为零,因此会被正确地识别为环。
线性时间的结论假设对边权和标号的算术运算与比较都是精确的。对于有限精度或任意精度的权重,这些运算的代价和可靠性取决于具体表示方式。图论上的不变量不变,但其数值实现需要另行分析。特别地,有限数值的哨兵值在加上边权时不能溢出,也不能与合法的有限路径值混淆。
总结
DAG 总有入度为零的顶点,所以 Kahn 算法反复移除这样的顶点,就得到拓扑序。按此顺序,所有入边的松弛都发生在顶点被处理之前,因此即使有负权重,也能在线性时间内求出最短路径。
练习
快速检查
(给出边 和 的一个拓扑序。)
一开始哪些顶点的入度为零?
解答 · 答案
或 都是合法的。 与 的初始入度都为零,而 必须排在两者之后。
快速检查
(在负边的例子中,计算从 到 的距离。)
比较直接的边与经过 的路径。
解答 · 答案
路径 的权重为 ,小于权重为五的直接边。最短距离为 。
快速检查
(为什么有限非空的 DAG 必有入度为零的顶点?)
沿入边向后走。
解答 · 答案
否则每个顶点都有入边,从任一顶点出发反复沿入边向后走,在有限图中最终会重复某个顶点,重复的那一段是有向环,与无环矛盾。
快速检查
(Kahn 算法提前停止后,能否认为每个未处理的顶点都在某个环上?)
想一想只从环接收一条边的顶点。
解答 · 答案
不能。位于环下游的顶点,即使不在任何环上,也可能因入度为正而留下。只能保证剩余子图至少含有一个环。