次序令依赖关系安全
令 为以邻接表表示的有限有向无环图(DAG)。为清楚起见,假设没有平行边;一条路径由其有序顶点序列指定。选定容许的起点集合 。每个 到自身的零边路径算作一条路径。我们会数出由任一容许起点到各顶点的路径,并在边带实数权重时求最大路径权重。不可达顶点的路径数为零,没有有限的最大值。
拓扑排序一节已证明,在 DAG 的任何拓扑次序中,每条边都由较早顶点指向较后顶点。这正是动态规划所需的条件:处理某个顶点时,其所有前驱到达的路径已经作出贡献。不同合法次序的中间表未必相同,但最终答案相同。
定义 5.5.1
(由容许起点出发的路径数与最大路径权重)
令 为满足下列条件的路径 的集合:,每个 都是边,,。路径数为 。最大路径权重 是 中 的最大值,其中零边路径的权重为 ;若 为空,则 ,。
可供观察的次序
对于边 、、,初始入度为零的顶点是 和 。先后移除 的两种顺序都可以;移除二者后,可再移除 ,然后是 。若边为 、、,且 孤立,移除 和 后剩下环 ,没有零入度顶点。
用入度进行拓扑排序
选择任何剩余入度为零的顶点。移除顶点时也会移除其出边;入度只计算仍存在的边。
有向边: A → C, B → C, C → D
当前次序: 没有. 选择可用顶点以继续。
| 顶点 | 入度 |
|---|---|
| A | 0 |
| B | 0 |
| C | 2 |
| D | 1 |
选择不同的零入度顶点可得到不同但有效的次序。有向无环图在所有顶点移除前,必有至少一个这样的顶点。
在组件的第一个情况,先选 再选 ,或撤销后先选 再选 。显示次序虽然不同,两者都把 放在两个前驱之后。组件显示移除次序及剩余入度;它不计算路径数或边权。下面会自行计算。第二个情况则显示剩余有向环如何令 DAG 前提失效。上一段在静态阅读或导出时提供相同的必要状态。
按最后一条边数路径
初始化:当 时令 ,否则令 。按拓扑次序处理顶点;处理 时,对每条出边 执行
定理 5.5.2
(按最后一边计数)
当 时令 ,否则令 ,并按拓扑次序用上述更新式处理 DAG 的顶点。则对每个顶点 都有 ,而且 在 被处理之后不再改变。
证明
(按拓扑次序归纳)
为何计数正确?每条以 结尾的非空路径都有唯一最后一边 ;删去该边后得到一条以 结尾的路径。反过来,加上该边便得到一条以 结尾的路径。不同类别的最后一边不同,因此互不重叠。当 ,初始的 贡献一条零边路径。即使另一个容许起点有路径通往某个起点,这些贡献也会额外加入其零边路径。按拓扑次序归纳,处理 之前,所需贡献已全部且只有它们到达。
证明透视
无环性、零边路径与简单边用在哪里
关键的一步是最后一边分解:它把长度不受限的路径集合换成以 的入边为下标的不相交并集,所以每条边只需作一次加法。拓扑次序使归纳有依据:每条边 的 都排在 之前,所以处理 时每个入邻居都已推送其最终计数,之后不可能再有东西加到 。无环性保证这样的次序存在,同时使 为有限集, 才是一个数。没有平行边也在同一步用到:若有两条 ,同一个顶点序列就会对应两次加法,与“路径就是其顶点序列”的约定不符。初始值 对应唯一没有最后一边的路径;它是被加上去而不是被取代,因为属于 的顶点也可以是较长路径的终点。论证在处理完最后一个顶点时收尾,此时以任何顶点结尾的每条路径都已恰好记在某一条最后一边上。
最大权重,包括负边
给每条边有限实数权重 。对 初始化 ,其余顶点取 。按拓扑次序,对每条满足 的边 执行
定理 5.5.3
(按最后一边求最大权重)
对 令 ,其余顶点令 ,并按拓扑次序用上述更新式处理 DAG 的顶点,跳过起点满足 的边。则对任意有限实数权重,每个顶点 都有 。
证明
(对最大权重作同样的归纳)
同样以最后一边归纳可证: 是由容许起点到 的路径之最大总权重;若没有路径,则保留 。对容许起点,零边路径权重为零,但进入该点的路径可以改善它。有限 DAG 的路径只有有限多条,因此可达时最大值存在。负权重不会造成困难,因为拓扑次序先处理每个前驱,且没有有向环;这不是 Dijkstra 算法。
例题 5.5.4
(第一幅图上的计数与权重)
对组件的第一幅图,取 ,权重 、、。两种显示次序都给出以下最终值:
| 顶点 | ||||
|---|---|---|---|---|
| 1 | 1 | 2 | 2 | |
| 0 | 0 | 2 | 5 |
由容许起点到 有两条路径: 及 。再加上 得到两条到 的路径;权重最大的由 出发,权重为 。 及 的计数来自零边路径。组件不显示此权重/计数表;它显示计算所使用的次序。
例题 5.5.5
(有路径通往的容许起点)
取 ,边 权重为 、 权重为 ,拓扑次序为 。对 ,初始 、。沿 处理 :,。沿 处理 :,。到 的路径是零边路径 和路径 ,所以 ;零边路径的权重为 ,胜过权重为 的 。到 的路径是 (权重 )和 (权重 ),所以 ,。这就是容许起点在自己的零边路径之外还收到其他贡献的情形。
例题 5.5.6
(四个顶点上的完全前向 DAG)
取顶点 ,所有 的边 权重为 ,,按 的次序处理。则 、、、,内部顶点集 的每个子集对应一条路径。权重方面,、、、:最长路径是 ,有三条边,虽然共有四条路径。当 ,同一公式给出 ,即一条单边。
概念视角代数
把计数看成三角线性方程组
设 为邻接矩阵,边 对应 ;设 为行向量, 时 ,否则为 。按最后一条边计数,就是 ,即 。在拓扑序下 是严格上三角矩阵,所以 是对角线全为 的三角矩阵,而更新规则恰是前向代入:每个 都由更早的项决定。等价地,,这是有限和,因为 达到顶点数时 。对上面的四个顶点,得 。
常见错误
(把每个顶点的计数都从一开始)
只有容许起点才有零边路径。取 与唯一的边 ,若令每个顶点 ,就会得到 ,但从 到 的唯一路径是 。只应在 时令 。
常见错误
(把每个最大权重都从零开始)
把非起点初始化为 会掩盖负权重。取 与权重为 的边 ,真值是 ,但更新式 返回 ,没有任何路径达到这个权重。同样的初始化还会使不可达顶点看似可达,权重为 。非起点应取 ,并跳过起点值为 的边。
实现与限制
先求拓扑次序,并检查它是否包含全部 个顶点。否则应报告 DAG 方法不适用,不能把部分次序当成完整答案。
反例模式
含有向环的图上的递推式
断言:即使图中有有向环,只要按某个固定次序处理顶点,计数递推式同样有效。取 ,边 、、,次序为 。初始 ,。处理 使 加 ;处理 使 加 ;处理 使 加 。最终表为 、、。这张表无论怎样解读都不对:从 出发的简单路径有三条,即 、、,计数应为 ;若改数途径,则到 与到 都有无穷多条(、,等等)。 处的 包含途径 ,但它的贡献从未传给 。任何次序都会剩下这样一条向后的边,因为有向环没有最早的顶点。完整的拓扑次序恰在图无环时存在,所以检查次序是否包含全部 个顶点是方法的前提,而不是形式。
然后初始化数组,并扫描每个出边邻接表一次。这使用 次算术操作,图本身以外需要 个数组存储项;其比特空间也会随所编码的数值增长。若需要实际最大权重路径,当最大值改善时存储前驱;若多条路径同样最优,应指定平局规则。
操作次数假设对路径数的算术为常数时间。精确计数可能很大:对顶点 、包含所有 的边 的简单 DAG,当 ,由 到 有 条路径,每个内部顶点子集对应一条。因此精确整数需要越来越多比特。模数计数回答的是另一个问题;固定字长溢出可能破坏精确结果。
习题
快速检查
(令 ,边为权重 的 、权重 的 、权重 的 ; 为孤立点。给出四个顶点的 和 。)
解答 · 答案
计数为 、、、。最大权重为 、、、。经 的路径权重为 ,胜过权重为零的直接边。
快速检查
(为何把每个容许起点初始化为计数一,不代表其计数必然保持为一?)
解答 · 答案
初始值数的是零边路径;动态规划之后可加入由另一个起点进入该顶点的路径。
快速检查
(若 Kahn 次序不完整而仍有顶点,为何算法必须拒绝把它当作答案?)
解答 · 答案
部分次序没有处理所有顶点,余下依赖及输出尚未计算。对 Kahn 算法而言,剩余图含有向环;有限 DAG 的证明不适用。