写在前面
我们先提出与"回路"有关的几个问题.
problem 1.1
试分析存在回路的状态空间对动态规划是否具有适用性.
problem 2.1
在一个无负回路的图中有两个节点 s, t, 试求两点间的第 k 短路径.
对于第一个问题, 我们将沿着半环上的动态规划继续走下去, 探讨一下非幂等半环上的动态规划问题, 从而给出动态规划的一个更为广义的适用范围; 对于后面一个问题, 我们将从 Dijkstra 算法的适用性谈起, 并分析几个典型的最短路径问题的算法, 最后给出一个普适的求前 k 短路径的算法和一个非常漂亮的 k 最优 Dijkstra 算法, 来完成这个问题的解答.
problem 1.1
试分析存在回路的状态空间对动态规划是否具有适用性.
problem 2.1
在一个无负回路的图中有两个节点 s, t, 试求两点间的第 k 短路径.
对于第一个问题, 我们将沿着半环上的动态规划继续走下去, 探讨一下非幂等半环上的动态规划问题, 从而给出动态规划的一个更为广义的适用范围; 对于后面一个问题, 我们将从 Dijkstra 算法的适用性谈起, 并分析几个典型的最短路径问题的算法, 最后给出一个普适的求前 k 短路径的算法和一个非常漂亮的 k 最优 Dijkstra 算法, 来完成这个问题的解答.
维特比算法(Viterbi's Algorithm)
在 <舞动在半环上的"动态规划"> 一文中我们谈到, 对于幂等半环, 我们可以从偏序关系出发, 构建出状态空间的一个拓扑结构, 从而进行动态规划. 注意这里我们有两个不同的偏序关系的概念: 第一个是幂等半环中元素之间的偏序关系, 第二个是状态空间上的拓扑结构上的偏序关系.
那么, 如果元素之间不存在偏序关系, 我们能不能构造出这样的拓扑结构呢? 我们先举一个例子, 考虑一般的维特比问题.
假定现在我们有 k+1 层节点 V[i][j], 其中 i = 0, 1, ... k, 每一个节点存在一个权重 w ; 此外, 当且仅当两个节点处于相邻的两层时, 它们之间存在一条边V[i][j1] -> V[i+1][j2], 这条边也存在一个权重 e .
考虑一个半环 <K, (+), (*), 0, 1>, 这里 (+) 和 (*) 是泛指. 现在我们对一个路径也定义一个权重, 这条路径的权重就是该路径上所有的点和所有的边的权重进行 (*) 运算的结果, 注意仅有一个节点的路径也是有权重的. 考虑任意一个节点, 对于它来说, 有很多条从第 0 层出发的路径抵达它, 每一条路径都有一个权重, 我们把这些权重进行 (+) 运算, 记为该节点的得分. 维特比问题就是求一个节点的得分的问题.
例如, <R+, min, *, 0, 1> 就是在这个图中求一个最短路径的问题. 再如, <R, +, *, 0, 1> 就是求从第 0 层出发, 抵达一个节点的所有路径的权重之和, 其中一个路径权重是点和边的权重的积. 注意在这两个例子中, 前者是幂等半环, 而后者不是. 两者却都可以通过维特比算法进行动态规划.
维特比算法, 即用动态规划方法求解维特比问题的一种算法. 根据上面对维特比问题的定义, 我们很容易找到一个节点得分之间的状态转移方程.
那么, 如果元素之间不存在偏序关系, 我们能不能构造出这样的拓扑结构呢? 我们先举一个例子, 考虑一般的维特比问题.
假定现在我们有 k+1 层节点 V[i][j], 其中 i = 0, 1, ... k, 每一个节点存在一个权重 w ; 此外, 当且仅当两个节点处于相邻的两层时, 它们之间存在一条边V[i][j1] -> V[i+1][j2], 这条边也存在一个权重 e .
考虑一个半环 <K, (+), (*), 0, 1>, 这里 (+) 和 (*) 是泛指. 现在我们对一个路径也定义一个权重, 这条路径的权重就是该路径上所有的点和所有的边的权重进行 (*) 运算的结果, 注意仅有一个节点的路径也是有权重的. 考虑任意一个节点, 对于它来说, 有很多条从第 0 层出发的路径抵达它, 每一条路径都有一个权重, 我们把这些权重进行 (+) 运算, 记为该节点的得分. 维特比问题就是求一个节点的得分的问题.
例如, <R+, min, *, 0, 1> 就是在这个图中求一个最短路径的问题. 再如, <R, +, *, 0, 1> 就是求从第 0 层出发, 抵达一个节点的所有路径的权重之和, 其中一个路径权重是点和边的权重的积. 注意在这两个例子中, 前者是幂等半环, 而后者不是. 两者却都可以通过维特比算法进行动态规划.
维特比算法, 即用动态规划方法求解维特比问题的一种算法. 根据上面对维特比问题的定义, 我们很容易找到一个节点得分之间的状态转移方程.
$$ s(i, j) = \begin{cases} w(i, j) & i = 0 \\ w(i, j) * (+_{V(i-1, k) \in G} t(i, k, j)) & i > 0\end{cases} $$ $$ t(i, k, j) =s(i-1, k) * e(i-1, k, i, j) $$
之后, 我们可以从第 0 层出发, 按照层的顺序 (实际上就是拓扑顺序) 来求每一个节点的得分, 直到得到目标节点的得分为止.
关于维特比问题, 我们注意其中两点. 第一, 这个例子说明了只要状态之间存在拓扑结构, 我们就可以做动态规划, 而与半环本身是否幂等无关. 事实上, 对于幂等半环来讲, 我们很容易对元素间的偏序关系和状态间的偏序关系建立直观的联系, 这也是幂等半环易于构建算法且易于理解的原因之一.
第二, 维特比问题本身就已经给出了一个拓扑结构, 而实际问题中大多拓扑结构需要自己构造. 事实上, 对已经给定拓扑结构的问题, 采用动态规划方法是容易而且直观的, 我们只需关注效率问题(如何合并会更快); 而动态规划的难点在于如何构建一个拓扑结构.
关于维特比问题, 我们注意其中两点. 第一, 这个例子说明了只要状态之间存在拓扑结构, 我们就可以做动态规划, 而与半环本身是否幂等无关. 事实上, 对于幂等半环来讲, 我们很容易对元素间的偏序关系和状态间的偏序关系建立直观的联系, 这也是幂等半环易于构建算法且易于理解的原因之一.
第二, 维特比问题本身就已经给出了一个拓扑结构, 而实际问题中大多拓扑结构需要自己构造. 事实上, 对已经给定拓扑结构的问题, 采用动态规划方法是容易而且直观的, 我们只需关注效率问题(如何合并会更快); 而动态规划的难点在于如何构建一个拓扑结构.
回路(cycle)
现在我们对于动态规划适用性的理解扩充了. 只要状态空间存在拓扑结构, 其一定适用动态规划. 下面我们讨论一个状态空间中的复杂结构, 从而给出 problem 1.1 的解.
假定状态空间中存在回路, 即有 k 个状态 S, S[1] 指向 S[2], S[2] 指向 S[3], ... S[k] 指向 S[1]. 我们举个例子. 考虑一个图中的最短路径问题, 我们现在要求点 A 到点 B 的最短路径. 现在有 k 个点之间存在一个回路, 试问我们所要求的最短路径是否存在.
一个很显然的结论是如果这个回路遍历一周的权重是负数, 我们的最短路径肯定不存在. 因为, 在原有路径的基础上, 我们只需要沿着这个回路再走一遍, "最短路径"一定可以变的更短, 从而没有下限. 我们把这样的回路叫做负权回路, 或者负回路. 轻松可知, 存在负回路的图中不存在任意两点的最短路径, 只要这两点和这个负回路连通.
考虑另一种情况, 即这个图中不存在负回路. 事实上, 如果图中不存在负回路的话, 我们可以通过几种典型的动态规划策略来求解最短路径. 例如 Bellman-Ford 算法, 其优化后的 SPFA 算法, 以及 O(n^3) 就可以求出任意两点间最短路径的 Floyd 算法. 这些算法我们会在下面详细讨论.
我们关心这样一个问题, 就是对一个回路迭代有限次后, 其结果是否会收敛. 一般地, 对于任意一个半环和一个固定的正整数 k , 如果 (+) 运算迭代 k 次以上之后结果不会再变化, 我们则称这样的半环为 k-封闭半环.
假定状态空间中存在回路, 即有 k 个状态 S, S[1] 指向 S[2], S[2] 指向 S[3], ... S[k] 指向 S[1]. 我们举个例子. 考虑一个图中的最短路径问题, 我们现在要求点 A 到点 B 的最短路径. 现在有 k 个点之间存在一个回路, 试问我们所要求的最短路径是否存在.
一个很显然的结论是如果这个回路遍历一周的权重是负数, 我们的最短路径肯定不存在. 因为, 在原有路径的基础上, 我们只需要沿着这个回路再走一遍, "最短路径"一定可以变的更短, 从而没有下限. 我们把这样的回路叫做负权回路, 或者负回路. 轻松可知, 存在负回路的图中不存在任意两点的最短路径, 只要这两点和这个负回路连通.
考虑另一种情况, 即这个图中不存在负回路. 事实上, 如果图中不存在负回路的话, 我们可以通过几种典型的动态规划策略来求解最短路径. 例如 Bellman-Ford 算法, 其优化后的 SPFA 算法, 以及 O(n^3) 就可以求出任意两点间最短路径的 Floyd 算法. 这些算法我们会在下面详细讨论.
我们关心这样一个问题, 就是对一个回路迭代有限次后, 其结果是否会收敛. 一般地, 对于任意一个半环和一个固定的正整数 k , 如果 (+) 运算迭代 k 次以上之后结果不会再变化, 我们则称这样的半环为 k-封闭半环.
<Foundations of Machine Learning> 的作者, 纽约大学的教授 Mehryar Mohri(森) 早在2002年的时候发表了一篇文章 <Semiring Frameworks and Algorithms for Shortest-Distance Problems>, 其中包含了 k-封闭半环的内容.
有兴趣的读者可以参考一下.
从狭义上讲, 对于任意一个 k-封闭半环, 我们总可以通过拆分状态的方法把它转化成一个幂等半环. 对广义而言, 我们不必把简单模型复杂化, 直接对 k-封闭半环的结构构建动态规划算法即可.
Answer 1.1
如果存在一个正整数 k , 对于该状态空间的任意一个回路和任意一个大于 k 的正整数 k', 满足在该回路上进行 k' 次 (+) 迭代和进行 k 次 (+) 迭代的结果相同, 那么这个状态空间上是适用动态规划模型的. 反之, 如果找不到这样的 k (该回路对于 (+) 运算是发散的) , 那么这个状态空间对动态规划不适用.
Answer 1.1
如果存在一个正整数 k , 对于该状态空间的任意一个回路和任意一个大于 k 的正整数 k', 满足在该回路上进行 k' 次 (+) 迭代和进行 k 次 (+) 迭代的结果相同, 那么这个状态空间上是适用动态规划模型的. 反之, 如果找不到这样的 k (该回路对于 (+) 运算是发散的) , 那么这个状态空间对动态规划不适用.
最短路径(shortest path)
现在我们尝试解决problem 2.1. 在上文中我们提到了求最短路径问题的几个经典算法, 下面我们把这些算法梳理一下. 首先, 对于存在负回路的图, 一定不存在两点间的最短路径, 只要这两点和某个负回路连通.
一般地, 对于一个无回路的图 G 和 G 中的两个节点 s 和 t , s 和 t 之间存在若干路径. 最短路径问题就是求解这些路径中长度最小的. 其中, 一条路径的长度是该路径中所有边的长度之和.
现在我们讲一个最短路径上的重要性质, 这个性质是构建最短路径问题上几乎所有算法的出发点. 考虑 s 到 t 的最短路径 P(s, t) , 假定这条最短路径上经过了另一个节点 u , 我们则可以从 P(s, t) 中截取一段 P(s, u). 那么, P(s, u) 是点 s 到点 u 的一条最短路径吗?
一般地, 对于一个无回路的图 G 和 G 中的两个节点 s 和 t , s 和 t 之间存在若干路径. 最短路径问题就是求解这些路径中长度最小的. 其中, 一条路径的长度是该路径中所有边的长度之和.
现在我们讲一个最短路径上的重要性质, 这个性质是构建最短路径问题上几乎所有算法的出发点. 考虑 s 到 t 的最短路径 P(s, t) , 假定这条最短路径上经过了另一个节点 u , 我们则可以从 P(s, t) 中截取一段 P(s, u). 那么, P(s, u) 是点 s 到点 u 的一条最短路径吗?
这个问题为我们提供了一个分治策略的可能性. 假如 P(s, u) 一定是 s 到 u 的一条最短路径, 那么我们就可以类似地得到 P(u, t) 也一定是 u 到 t 的一条最短路径. 这样的话, 我们就可以把一个求最短路径的母问题分解为子问题了.
事实上, 我们可以在这条性质中得到一条关于松弛操作(relaxation)的信息, 并利用它建模求解最短路径问题. 我们分情况讨论.
假定图中的每一条边的权重都是正数. 那么, P(s, u) 一定是 s 到 u 的最短路径. 考虑反证法. 如果 P(s, u) 不是其最短路径, 那么必有另一条路径 Q(s, u) < P(s, u). 如果 Q(s, u) 不经过 t 的话, 我们得到了一个矛盾, 因为 Q(s, u) + P(u, t) < P(s, t), 因此 P(s, t) 不是 s 到 t 的最短路径; 如果 Q(s, u) 经过 t 的话, 我们把它拆成 Q(s, t), Q(t, u), 则我们有 Q(s, t) + Q(t, u) < P(s, u) < P(s, t), 进而得到 Q(s, t) < P(s, t), 矛盾. 因此 P(s, u) 一定是 s 到 u 的一条最短路径. 相似地, 我们可以得到, P(u, t) 一定是一条 u 到 t 的最短路径.
注意, 仅当每一条边的权重都是正数的时候上述不等式成立.
进而, 我们考虑另一种情况. 图中的边的权重可能是负数. 现在假定 P(s, u) = 3, P(u, t) = -1, 图中存在另一条不经过 u 的路径 Q(s, t) = 3, 以及一条 t 到 u 的路径 Q(t, u) = -1 (无向图不需此前提). 那么, 我们知道 P(s, u) 不是 s 到 u 的最短路径, 因为 Q(s, t) 不经过 u, 我们可以用 Q(s, t) + Q(t, u) 来作为 s 到 u 的一条更短的路径. 因此在有负权的边的时候, 这个问题的回答是否定的.
我们进一步考虑 s, u, t 这三个点的关系. 假如我们上述的几个路径之外不存在其他路径, 那么我们可以观察得知, s 到 t 的最短路径经过 u, s 到 u 的最短路径经过 t . 这是因为我们引入了 P(u, t) 和 Q(t, u) 两条负边. 这样的话, P(s, u) 被另一条路径 Q(s, t) + Q(t, u) 更新了.
我们加入时间顺序来考虑这个问题. 由于最短路径具有反向有界性, 我们会先把 s 到 u 的最短路径的上限设为一个极大值. 在我们找到了 P(s, u) 之后, 我们把这个上限更新成 P(s, u) ; 之后我们找到了另一条路径 Q(s, t) + Q(t, u), 我们继续更新这个上限. 每一次更新, 我们都把 s 到 u 的最短路径满足的一个上限做了一次强化, 类似于不等式中的松弛( a < 5 是 a < 3 的一个松弛, 所以两个条件同时存在时我们可以抛弃前者), 我们把一次更新称为一次松弛操作(relaxation).
总结一下我们讨论的两个情况. 对于每条边权值都为正的图, 最短路径的子路径也一定是一条最短路径; 对于存在负边的情况, 我们这个性质不成立, 但我们依然可以通过松弛操作来求解最短路径. 于是我们把这类最短路径问题分为两种, 一种是正权图的最短路径, 另一种是一般图的最短路径(无负权环皆可).
注意, 仅当每一条边的权重都是正数的时候上述不等式成立.
进而, 我们考虑另一种情况. 图中的边的权重可能是负数. 现在假定 P(s, u) = 3, P(u, t) = -1, 图中存在另一条不经过 u 的路径 Q(s, t) = 3, 以及一条 t 到 u 的路径 Q(t, u) = -1 (无向图不需此前提). 那么, 我们知道 P(s, u) 不是 s 到 u 的最短路径, 因为 Q(s, t) 不经过 u, 我们可以用 Q(s, t) + Q(t, u) 来作为 s 到 u 的一条更短的路径. 因此在有负权的边的时候, 这个问题的回答是否定的.
我们进一步考虑 s, u, t 这三个点的关系. 假如我们上述的几个路径之外不存在其他路径, 那么我们可以观察得知, s 到 t 的最短路径经过 u, s 到 u 的最短路径经过 t . 这是因为我们引入了 P(u, t) 和 Q(t, u) 两条负边. 这样的话, P(s, u) 被另一条路径 Q(s, t) + Q(t, u) 更新了.
我们加入时间顺序来考虑这个问题. 由于最短路径具有反向有界性, 我们会先把 s 到 u 的最短路径的上限设为一个极大值. 在我们找到了 P(s, u) 之后, 我们把这个上限更新成 P(s, u) ; 之后我们找到了另一条路径 Q(s, t) + Q(t, u), 我们继续更新这个上限. 每一次更新, 我们都把 s 到 u 的最短路径满足的一个上限做了一次强化, 类似于不等式中的松弛( a < 5 是 a < 3 的一个松弛, 所以两个条件同时存在时我们可以抛弃前者), 我们把一次更新称为一次松弛操作(relaxation).
总结一下我们讨论的两个情况. 对于每条边权值都为正的图, 最短路径的子路径也一定是一条最短路径; 对于存在负边的情况, 我们这个性质不成立, 但我们依然可以通过松弛操作来求解最短路径. 于是我们把这类最短路径问题分为两种, 一种是正权图的最短路径, 另一种是一般图的最短路径(无负权环皆可).
我们把现在讨论的问题称为"一类"最短路径问题. 因为基于不同结构的图(非简单图, 超图等等), 最短路径问题的变种有很多. 即便是对于一个简单图, 我们对第 k 短路径也有不同的定义. 比如另一种第 k 短路径考虑长度排序时相异值的第 k 短. 举个例子, 所求的第二短路径一定要比最短路径长, 第三短路径一定要比第二短路径长, 等等.
本文所讨论的最短路径和第 k 短路径是最一般化的定义.
迪科斯彻算法(Dijkstra's algorithm)
现在我们考虑正权图. 在正权图中, 最短路径的子路径一定是最短路径. 考虑一个点 s 到所有点的最短路径, 那么, 这些最短路径一定只有两种存在方式: 第一, 该最短路径 P(s, t) 只有一条边; 第二, 该最短路径 P(s, t) 是另一个最短路径 P(s, u) 再加上一条边 E(u, t) 构成的. 换言之, 首先我们可以找 s 出发, 只有一条边的最短路径; 其次, 给定从 s 出发, 有 k 条边的最短路径之后, 我们可以求出有 k+1 条边的最短路径. Dijkstra算法就是基于这个原则的一种贪心法.
贪心法, 是一种从局部最优出发, 每一步都选取局部最优, 从而试图达到全局最优的算法. 一切基于贪心策略的算法都必须有一个理论支持, 证明局部最优一定可以一步一步达到全局最优.
我们继续考虑最短路径问题在正权图上的重要性质. 注意, 从 s 出发的最短的一条边 E(s, v), 生成的单边路径 P(s, v) 一定是一条最短路径, 因为 s 经过其他点抵达 v 所花费的代价一定比它高. 进一步而言, 考虑一个包含 s 的子图 G', 它的点集是 s 和一些点, s 到这些点的一条最短路径包含在 G' 中. 那么, 从 G' 中任意一个节点出发的到 G' 之外的最短的一条路径 P(s, v) = P(s, u) + E(u, v) 一定是一条最短路径, 其中 u 在 G' 中但是 v 不在, P(s, u) 是一条 s 到 u 的最短路径. 这个原因和上面相同, 因为 s 经过其他点抵达 v 所花费的代价一定比 P(s, v) 高.
Dijkstra 算法便是利用上面的性质来不断地扩展子图 G', 直到 G' = G. 这个性质保证了局部最优一定可以达到全局最优, 因而 Dijkstra 算法所采用的贪心策略是正确的. 注意, G' 进行拓展之后, 只需要把新添加的点拿来对其相邻节点进行松弛操作就可以了, 这样做就可以不断更新 s 到 G' 之外的一个节点的最短路径.
1) s 到 s 的距离初始化为 0 , s 到其他点的距离利用反向有界性初始化;
2) G' 只包含 s , 用 s 对 s 到 s 的相邻节点最短距离的上界进行松弛操作;
3) 循环以下操作, 直至 G' = G: 找到 G' 之外的一个节点 u, 使得 P(s, u) 是最小的; 之后把 u 添加进 G' , 用 u 对 s 到 u 的相邻节点最短距离的上界进行松弛操作.
一遍 Dijkstra 算法执行下来之后, 就可以求出正权图中 s 到所有节点的最短路径.
贪心法, 是一种从局部最优出发, 每一步都选取局部最优, 从而试图达到全局最优的算法. 一切基于贪心策略的算法都必须有一个理论支持, 证明局部最优一定可以一步一步达到全局最优.
我们继续考虑最短路径问题在正权图上的重要性质. 注意, 从 s 出发的最短的一条边 E(s, v), 生成的单边路径 P(s, v) 一定是一条最短路径, 因为 s 经过其他点抵达 v 所花费的代价一定比它高. 进一步而言, 考虑一个包含 s 的子图 G', 它的点集是 s 和一些点, s 到这些点的一条最短路径包含在 G' 中. 那么, 从 G' 中任意一个节点出发的到 G' 之外的最短的一条路径 P(s, v) = P(s, u) + E(u, v) 一定是一条最短路径, 其中 u 在 G' 中但是 v 不在, P(s, u) 是一条 s 到 u 的最短路径. 这个原因和上面相同, 因为 s 经过其他点抵达 v 所花费的代价一定比 P(s, v) 高.
Dijkstra 算法便是利用上面的性质来不断地扩展子图 G', 直到 G' = G. 这个性质保证了局部最优一定可以达到全局最优, 因而 Dijkstra 算法所采用的贪心策略是正确的. 注意, G' 进行拓展之后, 只需要把新添加的点拿来对其相邻节点进行松弛操作就可以了, 这样做就可以不断更新 s 到 G' 之外的一个节点的最短路径.
1) s 到 s 的距离初始化为 0 , s 到其他点的距离利用反向有界性初始化;
2) G' 只包含 s , 用 s 对 s 到 s 的相邻节点最短距离的上界进行松弛操作;
3) 循环以下操作, 直至 G' = G: 找到 G' 之外的一个节点 u, 使得 P(s, u) 是最小的; 之后把 u 添加进 G' , 用 u 对 s 到 u 的相邻节点最短距离的上界进行松弛操作.
一遍 Dijkstra 算法执行下来之后, 就可以求出正权图中 s 到所有节点的最短路径.
迪科斯彻算法 (Dijkstra's Algorithm) 是一种典型的贪心策略. 该算法由荷兰计算机科学家 Dijkstra 于1956 年提出, 并于1959 年发表. 此后, Dijkstra 于1972 年获得图灵奖.
在荷兰语中 ijk 三个字符的音节发音类似英语的 like 中 ike 的发音, 因此把荷兰计算机科学家 Dijkstra 翻译成"迪杰斯特拉"不甚准确. 本文避开这个翻译问题.
Dijkstra 算法的空间复杂度是O(n), 我们只需要存储 n 个最短路径的上限, 对其更新即可. 时间复杂度分析牵扯到一些相对复杂的数据结构, 我们先分析一下它的开销, 之后解释这个事情.设图 G 中的边数是 E , 点数是 V , 则这个算法的开销总共有两个地方: 第一, 对于每一个 G' 的拓展, 我们都需要寻找一个 G' 之外路径长度最小的节点, 假定它的时间代价是O(find_min) 或 O(extract_min) ; 第二, 我们拿到一个新的节点之后需要利用它的所有临边进行松弛操作, 它的时间代价记为 O(update) . 对于后者来说, 我们考虑 Dijkstra 的整体过程, 每一条边都会被用来做一次松弛操作, 因此总共只会执行 E 次的松弛操作. 因此, Dijkstra 算法的时间复杂度 C 如下.
$$ C = O(V * findmin + E * update) $$
现在我们就可以解释为什么 Dijkstra 算法的时间复杂度分析牵扯到很多复杂的数据结构了. 如果我们用一个线性存储空间来存储 s 到所有点的最短路径的上界, 那么 find_min = V, update = 1. C = O(V^2).
可以看到, 当图比较稀疏的时候这个复杂度是偏高的, 因为 E 往往达不到 V^2 的数量级. 我们需要一种动态的数据结构, 既可以用低于线性的时间来取出最小值, 又可以降低一次更新的开销. 因而我们需要优先队列.
当前最好的方法是采用一种用 Fibonacci 堆实现的优先队列来存储这样 V 个需要维护的最短路径的上界, 在 Fibonacci 堆之下, update = 1, find_min = log V. 因此, Dijkstra算法的复杂度被优化到了 O(V log V + E).
可以看到, 当图比较稀疏的时候这个复杂度是偏高的, 因为 E 往往达不到 V^2 的数量级. 我们需要一种动态的数据结构, 既可以用低于线性的时间来取出最小值, 又可以降低一次更新的开销. 因而我们需要优先队列.
当前最好的方法是采用一种用 Fibonacci 堆实现的优先队列来存储这样 V 个需要维护的最短路径的上界, 在 Fibonacci 堆之下, update = 1, find_min = log V. 因此, Dijkstra算法的复杂度被优化到了 O(V log V + E).
这里的难点在于数据结构要求是动态的. 因为 G' 之外的点的集合在不断缩小, 因此每次弹出一个节点之后都需要维护这个数据结构, 使得下一次找最小值的开销依然会很低. 优先队列可以进行插入, 弹出和维护操作.
优先队列有不同的实现方法, 比如堆, 二项堆, Fibonacci堆等. 不同的数据结构对不同的操作的时间代价不同, 有优有劣. 仅考虑弹出最小值和更新节点这两个操作的话, 时间代价最低的是 Fibonacci 堆.
早在1987年, UCSD的教授 Michael Fredman 和 Tarjan (Tarjan 算法的发明者) 合作了一篇文章<Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms>, 首创性地提出了 Fibonacci 堆, 并用它优化了一系列的算法, 其中包括 Dijkstra 算法.
有兴趣的读者可以参考一下.
松弛(Relaxation)
下面我们考虑第二种情况, 即有负权但是无负回路的图中的最短路径. 注意这种情况下虽然我们不满足之前提出的重要性质, 但是我们依然可以通过松弛操作来找到最短路径. 考虑到最短路径问题也是在一个半环的模型下进行的, 所以我们尝试做动态规划, 并且在这个过程中尽可能合并更多的状态.
注意到 Dijkstra 的本质是利用贪心策略合并了一系列的状态, 把状态空间压缩到了 O(V) 上面. 引入负权之后, 单调性不再保持, 因此我们需要对状态空间进行维度拓展以保证单调性. 未经优化的状态空间是所有的路径的集合, 我们需要从中找到一条最短路径.
现在假定我们有一个子图 G', 在子图中我们得到了所有点到所有点的最短路径. 现在在这个子图中新增加了一个点 v 以及 v 与 G' 中的节点的连边, 我们把这个新图设为G''. 那么我们需要多少次更新之后, 就可以得到 G'' 中所有点到所有点的最短路径?
注意, 尽管在 G'' 中路径的个数仍是指数级的, 但是我们可以利用 G' 中所有点间的的最短路径. 事实上, 我们并不需要考虑 G' 中边的分布, 仅考虑 G' 中所有点间的最短路径即可. 换言之, 在 G'' 中 s 到 t 的最短路径可以由一些路径 P 累计而成: P 是一条相邻于 v 的边; P 是 G' 中某两点间的最短路径. 这个结论可以由反证法轻松得到, 只需考虑新路径中 v 的分布即可. 那么, 我们从 G' 中所有点到所有点间的最短路径更新到 G'' 中所有点到所有点间的最短路径, 仅花了多项式时间的代价, 因为 G' 中指数级的路径个数被优化到了n^2条最短路径.
事实上, 我们并不需要选取 G' 之外的点 v. 对于一个图 G , 我们定义 R(V') 为 G 中任意两点间的最短路径, 其中这些路径只能经过V'中的节点, 不能经过其他节点. 那么, 我们通过上述方法可以在 O(n^2) 的时间从R(V') 到 R(V' + v) 过渡, R(V) 就是任意两点间的最短路径.
Floyd-Warshall 算法就是基于这个理论构建的. 我们用数字编号来表示所有节点, 假定O(i, j, k) 是从节点 i 出发到节点 j 出发只经过节点 1..k 的路径中的最短路径, 那么 O(i, j, k) 满足状态转移方程如下.
注意到 Dijkstra 的本质是利用贪心策略合并了一系列的状态, 把状态空间压缩到了 O(V) 上面. 引入负权之后, 单调性不再保持, 因此我们需要对状态空间进行维度拓展以保证单调性. 未经优化的状态空间是所有的路径的集合, 我们需要从中找到一条最短路径.
现在假定我们有一个子图 G', 在子图中我们得到了所有点到所有点的最短路径. 现在在这个子图中新增加了一个点 v 以及 v 与 G' 中的节点的连边, 我们把这个新图设为G''. 那么我们需要多少次更新之后, 就可以得到 G'' 中所有点到所有点的最短路径?
注意, 尽管在 G'' 中路径的个数仍是指数级的, 但是我们可以利用 G' 中所有点间的的最短路径. 事实上, 我们并不需要考虑 G' 中边的分布, 仅考虑 G' 中所有点间的最短路径即可. 换言之, 在 G'' 中 s 到 t 的最短路径可以由一些路径 P 累计而成: P 是一条相邻于 v 的边; P 是 G' 中某两点间的最短路径. 这个结论可以由反证法轻松得到, 只需考虑新路径中 v 的分布即可. 那么, 我们从 G' 中所有点到所有点间的最短路径更新到 G'' 中所有点到所有点间的最短路径, 仅花了多项式时间的代价, 因为 G' 中指数级的路径个数被优化到了n^2条最短路径.
事实上, 我们并不需要选取 G' 之外的点 v. 对于一个图 G , 我们定义 R(V') 为 G 中任意两点间的最短路径, 其中这些路径只能经过V'中的节点, 不能经过其他节点. 那么, 我们通过上述方法可以在 O(n^2) 的时间从R(V') 到 R(V' + v) 过渡, R(V) 就是任意两点间的最短路径.
Floyd-Warshall 算法就是基于这个理论构建的. 我们用数字编号来表示所有节点, 假定O(i, j, k) 是从节点 i 出发到节点 j 出发只经过节点 1..k 的路径中的最短路径, 那么 O(i, j, k) 满足状态转移方程如下.
$$ o(i, j, 0) = e(i, j) $$ $$ o(i, j, k+1) = min( o(i, j, k), t) $$ $$ t = o(i, k+1, k) + o(k+1, j, k) $$
t 的本质是用 k+1 这个点对 P(i, j) 做一次松弛操作. 我们在实现的时候把 k 按照自然序从小到大做 n 次迭代, 每次迭代对全局任意两点间的最短路径做松弛操作即可. 其中 n 是 G 中点的个数.
Floyd 算法的本质是利用一个子问题的最短路径的集合来代替其边的集合, 从而把指数级的路径数量合并成多项式级, 进而完成动态规划. 它的时间复杂度是 O(n^3), 空间复杂度是 O(n^2).
Floyd 算法的本质是利用一个子问题的最短路径的集合来代替其边的集合, 从而把指数级的路径数量合并成多项式级, 进而完成动态规划. 它的时间复杂度是 O(n^3), 空间复杂度是 O(n^2).
负权回路(negative cycle)
通过上面的分析我们可以知道, Dijkstra 算法可以处理正权图中一个点到所有点的最短距离; Floyd-Warshall 算法可以处理有负边无负环的图中所有点到所有点的最短距离. 这样的话, 考虑 problem 1.1 中 k = 1 的情况 (即最短距离), 我们便可以做出解答了.
我们再介绍一种在有负边无负环的图中一个点到所有点的最短距离的算法, Bellman-Ford 算法. 弄懂了 Floyd-Warshall 算法的原理之后, 这个算法就很好理解了. 我们用每一条边来对 s 到所有点的最短距离做松弛操作, 这样的话 n-1 轮松弛操作之后, 就一定可以得到 s 到所有点的最短距离. 这个算法的复杂度是 O(VE).
为什么n-1次对所有边做松弛操作之后必定收敛呢? 因为一个最短路径的边的个数不超过 n-1, 我们对任何一个边的个数不超过 k 的最短路径可以通过 k 次松弛操作得到. 具体证明的思路和上述的方法类似.
我们再介绍一种在有负边无负环的图中一个点到所有点的最短距离的算法, Bellman-Ford 算法. 弄懂了 Floyd-Warshall 算法的原理之后, 这个算法就很好理解了. 我们用每一条边来对 s 到所有点的最短距离做松弛操作, 这样的话 n-1 轮松弛操作之后, 就一定可以得到 s 到所有点的最短距离. 这个算法的复杂度是 O(VE).
为什么n-1次对所有边做松弛操作之后必定收敛呢? 因为一个最短路径的边的个数不超过 n-1, 我们对任何一个边的个数不超过 k 的最短路径可以通过 k 次松弛操作得到. 具体证明的思路和上述的方法类似.
1994年, 来自西安交通大学的段凡丁用优先队列改进了这个算法, 在这里提及一下. 改进后的算法叫做Shortest Path Faster Algorithm 算法(SPFA), 时间复杂度为 O(kE), 其中 k 在大多数图中是一个不超过 2 的常数.
解决实际问题时推荐使用SPFA来代替Bellman-Ford算法.
现在我们关心的问题是, 这几种典型的最短路径算法能否判断出一个图是否有负权回路呢?
首先我们可以肯定 Dijkstra 算法做不到, 因为它在有负边的时候就挂掉了. 考虑 Bellman-Ford 算法, 一个负权回路可以在每次迭代之后优化一条连通的最短路径, 因此我们只需要继续进行第 n 轮松弛操作就可以了: 如果第 n 轮操作中有任何一个最短路径被更新了, 那么这个图中一定有负权回路.
对于 SPFA 算法, 类似地, 我们只需要记录一下每个节点入队的次数即可. 如果一个节点的入队次数超过了一个值(最大可能的更新次数), 那么这个图中即有负权回路.
下面考虑 Floyd 算法. 事实上, 在这几种算法中, Floyd 算法判定负权回路是最方便的. 考虑到我们对所有点之间的最短路径进行了 n 轮的松弛操作, 而且存在一个负权回路的边长个数不超过 n , 因此我们在 n 轮的松弛操作之后, 这个负权回路上的点对自己的最短距离一定是一个负数. 换言之, 如果 i 在某一个边长为 k 的负权回路上, 那么 k 轮迭代之后就有 P(i, i) < 0. 这样一来, 我们只需要在 Floyd 算法中观察是否有P(i, i) 被更新就可以了.
总而言之, 这几种可以求有负边的图的最短路径的算法都可以判定该图中是否存在负权回路. Dijkstra 算法不能判断负权回路.
首先我们可以肯定 Dijkstra 算法做不到, 因为它在有负边的时候就挂掉了. 考虑 Bellman-Ford 算法, 一个负权回路可以在每次迭代之后优化一条连通的最短路径, 因此我们只需要继续进行第 n 轮松弛操作就可以了: 如果第 n 轮操作中有任何一个最短路径被更新了, 那么这个图中一定有负权回路.
对于 SPFA 算法, 类似地, 我们只需要记录一下每个节点入队的次数即可. 如果一个节点的入队次数超过了一个值(最大可能的更新次数), 那么这个图中即有负权回路.
下面考虑 Floyd 算法. 事实上, 在这几种算法中, Floyd 算法判定负权回路是最方便的. 考虑到我们对所有点之间的最短路径进行了 n 轮的松弛操作, 而且存在一个负权回路的边长个数不超过 n , 因此我们在 n 轮的松弛操作之后, 这个负权回路上的点对自己的最短距离一定是一个负数. 换言之, 如果 i 在某一个边长为 k 的负权回路上, 那么 k 轮迭代之后就有 P(i, i) < 0. 这样一来, 我们只需要在 Floyd 算法中观察是否有P(i, i) 被更新就可以了.
总而言之, 这几种可以求有负边的图的最短路径的算法都可以判定该图中是否存在负权回路. Dijkstra 算法不能判断负权回路.
次短路径(second shortest path)
我们尝试解决 problem 2.1 . 在此之前, 我们先看一个简单的问题, 次短路径问题.
Problem 2.2
在一个无负回路的图中有两个点 s, t, 试求两点间的第二短路径.
我们进一步分析, 假定一个图中有一条最短路径 P(s, t), 另有一条次短路径 Q(s, t), 那么 P 和 Q 有什么联系呢? 答案是它们必有至少一条边不相同. 换言之, 在 P(s, t) 上总存在一条边, 使得 Q(s, t) 不经过这条边.那么, 我们把这条边去掉之后再求整个图的最短路径, 这个路径的长度是不是和 Q(s, t) 相同呢? 答案是肯定的. 用反证法可以证明.
在我们对 Problem 2.2 作出回答之前, 我们对这个算法做一个优化. 假定这个图是一个无负权图, 我们可以用 Dijkstra 算法求解最短路径. 当前删掉的边假定是 E(u, v), 于是 P(s, t) 在删掉边之后保留了一个前缀 P(s, u), 出于对称性我们暂时不考虑后缀. 用相同的反证法我们可以得出, 一条长度等于Q(s, t) 的次短路径可以在枚举每一个 E(u, v) 的前提下由 P(s, u) 加上 u 到 t 的最短路径求得. 而且, 在考虑 u 到 t 的最短路径的时候不仅不包含 E(u, v), 而且可以删掉 P(s, u) 涉足的所有节点, 相当于对一个子图求最短路径, 节省了很多冗余计算.
Problem 2.2
在一个无负回路的图中有两个点 s, t, 试求两点间的第二短路径.
我们进一步分析, 假定一个图中有一条最短路径 P(s, t), 另有一条次短路径 Q(s, t), 那么 P 和 Q 有什么联系呢? 答案是它们必有至少一条边不相同. 换言之, 在 P(s, t) 上总存在一条边, 使得 Q(s, t) 不经过这条边.那么, 我们把这条边去掉之后再求整个图的最短路径, 这个路径的长度是不是和 Q(s, t) 相同呢? 答案是肯定的. 用反证法可以证明.
在我们对 Problem 2.2 作出回答之前, 我们对这个算法做一个优化. 假定这个图是一个无负权图, 我们可以用 Dijkstra 算法求解最短路径. 当前删掉的边假定是 E(u, v), 于是 P(s, t) 在删掉边之后保留了一个前缀 P(s, u), 出于对称性我们暂时不考虑后缀. 用相同的反证法我们可以得出, 一条长度等于Q(s, t) 的次短路径可以在枚举每一个 E(u, v) 的前提下由 P(s, u) 加上 u 到 t 的最短路径求得. 而且, 在考虑 u 到 t 的最短路径的时候不仅不包含 E(u, v), 而且可以删掉 P(s, u) 涉足的所有节点, 相当于对一个子图求最短路径, 节省了很多冗余计算.
这个优化是 Yen's algorithm 的一部分, 由 Jin Y. Yen 于1971年提出.
Yen 算法就是在 Dijkstra 的基础上用上述方法迭代 k 次, 每次删边的时候保留前面的路径结果, 并且只对后面的子图做最短路径就可以了.
我们后面讲到的普适的优先队列的方法也可以把这个优化加上去.
Answer 2.2
对于存在负权边的图, 我们先用 SPFA 求出一条最短路径 P(s, t), 然后枚举 P(s, t) 中的每一条边, 求出很多条删边后的最短路径. 这些路径中最短的即为所求.
对于不存在负权边的图, 我们先用 Dijkstra 算法求出一条最短路径 P(s, t), 然后枚举 P(s, t) 的每一条边 E(u, v), 求出不包含 E(u, v) 也不包含 P(s, u) 上任意一个节点的 u 到 t 的最短路径 Q(u, t), 把 P(s, u) + Q(u, t) 作为删边后的最短路径. 这些路径中最短的即为所求.
这样我们就解决了 Problem 2.2. 那么, 我们如何利用这个思路去求第 k 短路径呢? 我们先提出一个普适的算法.
前面我们提到, P(s, t) 删掉每一条边都可以求出一个"准次短路径", 我们把所有的"准次短路径" 添加到一个备选集(candidates)里面. 在求次短路径的时候, 我们我们从备选集里弹出了一个最优值, Q(s, t). 那么, 第三短路径会是一个怎样的构造呢? 我们知道, 它有可能仍然在备选集里, 它也有可能是 Q(s, t) 删掉一条边之后所得的一条路径. 因此, 求第 k 短路径需要维护一个备选集(candidates), 因此我们需要构建一个优先队列.
一般地, 我们把优先队列初始化为只有 P(s, t) 的一个队列. 求 s 到 t 的第 k 短路径, 就是进行 k 次如下的迭代: 从优先队列里弹出最优的结果, 作为第 k 短路径; 之后把这个新的结果通过删边操作得到的"准次短路径"插入这个优先队列中.
我们简单提一下这个算法的一个重要优化. 对于这个优先队列, 我们在记录每一个最短路径的同时, 还需要记录该路径所删掉的边的集合. 在我们拿到第 k 短路径之后准备依次删边求新的"准次短路径"的时候, 如果删完边之后与优先队列中某个删掉边的集合重复了, 那我们就直接放弃它, 不再重新求一遍最短路径.
对于存在负权边的图, 我们先用 SPFA 求出一条最短路径 P(s, t), 然后枚举 P(s, t) 中的每一条边, 求出很多条删边后的最短路径. 这些路径中最短的即为所求.
对于不存在负权边的图, 我们先用 Dijkstra 算法求出一条最短路径 P(s, t), 然后枚举 P(s, t) 的每一条边 E(u, v), 求出不包含 E(u, v) 也不包含 P(s, u) 上任意一个节点的 u 到 t 的最短路径 Q(u, t), 把 P(s, u) + Q(u, t) 作为删边后的最短路径. 这些路径中最短的即为所求.
这样我们就解决了 Problem 2.2. 那么, 我们如何利用这个思路去求第 k 短路径呢? 我们先提出一个普适的算法.
前面我们提到, P(s, t) 删掉每一条边都可以求出一个"准次短路径", 我们把所有的"准次短路径" 添加到一个备选集(candidates)里面. 在求次短路径的时候, 我们我们从备选集里弹出了一个最优值, Q(s, t). 那么, 第三短路径会是一个怎样的构造呢? 我们知道, 它有可能仍然在备选集里, 它也有可能是 Q(s, t) 删掉一条边之后所得的一条路径. 因此, 求第 k 短路径需要维护一个备选集(candidates), 因此我们需要构建一个优先队列.
一般地, 我们把优先队列初始化为只有 P(s, t) 的一个队列. 求 s 到 t 的第 k 短路径, 就是进行 k 次如下的迭代: 从优先队列里弹出最优的结果, 作为第 k 短路径; 之后把这个新的结果通过删边操作得到的"准次短路径"插入这个优先队列中.
我们简单提一下这个算法的一个重要优化. 对于这个优先队列, 我们在记录每一个最短路径的同时, 还需要记录该路径所删掉的边的集合. 在我们拿到第 k 短路径之后准备依次删边求新的"准次短路径"的时候, 如果删完边之后与优先队列中某个删掉边的集合重复了, 那我们就直接放弃它, 不再重新求一遍最短路径.
这个剪枝类似于另外一个问题. 给定两组各 k 个排好序的数, 求它们的和的第 k 大的数.
假定a(i, j) 是第一组中第 i 大的数与第二组中第 j 大的数的和. 显然 a(1, 1) 会是最大的数, 去掉它之后我们留下了两个备选, a(1, 2) 和 a(2, 1). 那么, 每次拿走一个第 k 大的数之后都会增添两个备选吗? 显然不是的. 如果我们第二次和第三次拿走了 a(1, 2) 和 a(2, 1) 的话, 我们无需向优先队列里添加两次 a(2, 2).
我们所使用的优化和这个问题同理.
到这里为止, 我们就把求第 k 短路径的算法完全构建起来了. 利用每一个第 x 短路径可以生成第 x+1 短路径的备选, 我们通过一个优先队列来维护这些备选, 直至找到我们所需的最短路径.
k最优迪科斯彻算法(k-best dijkstra's algorithm)
最后我们介绍一种更高效的求正权图第 k 短路径的算法, 以补全对 problem 2.1 的回答.
先用另一个视角回顾一下 Dijkstra 算法. 我们做一次 Dijkstra 算法的过程, 就是扩展子图 G' 的过程. 考虑在扩展子图的时候维护一个队列 Q, 那么原始的 Dijkstra 算法中, 我们会在初始的时候把 s 放进队列, 第一步把 s 弹出, 把所有 s 的邻边放进这个队列; 之后, 我们每次都弹出一个节点, 并把这个节点更新掉的节点放进这个队列. 由于曾经被这个队列弹出的节点不会在被更新, 因此这个队列只是走遍了所有的节点而已.
我们假设现在有一个节点 u, 该节点曾作为备选(candidate) 出现在了这个队列中, 之后它被弹出了. 现在队列弹出了一个新的节点 v, 那么 v 会用一个更长的路径上限去更新 P(s, u), 从而更新失败. 现在我们思考一个问题, P(s, u) 的第二短路径从何而来呢? 通过上面的分析我们可以知道, 这个第二短路径是某个 v 来更新 P(s, u) 所用的值. 虽然这个值比我们已经得到的 P(s, u) 稍大, 但是它们中的最小值一定是 s 到 u 的第二短路径.
我们现在规定已经被弹出的节点也可以被放进队列里来, 而且节点被队列弹出之后我们就把它所记录的一个贪心得到的最短路径抹掉, 即记录在别的地方, 并用反向有界性初始化成一个极大值. 那么, 我们可以知道, 当所有的点恰好被这个队列弹出 k 次的时候, 我们就得到了 s 到所有点的前 k 短路径. 其时间复杂度为 k 乘以 Dijkstra 算法的时间复杂度.
这个算法叫做 k-best Dijkstra's algorithm, 我们把它叫做 K-最优迪科斯彻算法.
先用另一个视角回顾一下 Dijkstra 算法. 我们做一次 Dijkstra 算法的过程, 就是扩展子图 G' 的过程. 考虑在扩展子图的时候维护一个队列 Q, 那么原始的 Dijkstra 算法中, 我们会在初始的时候把 s 放进队列, 第一步把 s 弹出, 把所有 s 的邻边放进这个队列; 之后, 我们每次都弹出一个节点, 并把这个节点更新掉的节点放进这个队列. 由于曾经被这个队列弹出的节点不会在被更新, 因此这个队列只是走遍了所有的节点而已.
我们假设现在有一个节点 u, 该节点曾作为备选(candidate) 出现在了这个队列中, 之后它被弹出了. 现在队列弹出了一个新的节点 v, 那么 v 会用一个更长的路径上限去更新 P(s, u), 从而更新失败. 现在我们思考一个问题, P(s, u) 的第二短路径从何而来呢? 通过上面的分析我们可以知道, 这个第二短路径是某个 v 来更新 P(s, u) 所用的值. 虽然这个值比我们已经得到的 P(s, u) 稍大, 但是它们中的最小值一定是 s 到 u 的第二短路径.
我们现在规定已经被弹出的节点也可以被放进队列里来, 而且节点被队列弹出之后我们就把它所记录的一个贪心得到的最短路径抹掉, 即记录在别的地方, 并用反向有界性初始化成一个极大值. 那么, 我们可以知道, 当所有的点恰好被这个队列弹出 k 次的时候, 我们就得到了 s 到所有点的前 k 短路径. 其时间复杂度为 k 乘以 Dijkstra 算法的时间复杂度.
这个算法叫做 k-best Dijkstra's algorithm, 我们把它叫做 K-最优迪科斯彻算法.
根据黄亮大神在2005年的一篇未发表的文章<K-best knuth algorithm>提到, 这个 k-best Dijkstra algorithm 疑似起源于20世纪60年代的一个民间传说. (Dijkstra本人把 Dijkstra's algorithm 发表于 1959 年).
Mohri 和 Riley 于2002年发表了一篇文章<An Efficient Algorithm for the N-Best-Strings Problem>, 这篇文章的.ps版本可以在Mohri大神的主页上找到. 该文记载了这个算法, 但是没有把它命名为 k-best dijkstra's algorithm. 本文沿用了黄亮大神的命名.
有兴趣的读者可以参考一下.
K-最优 Dijkstra 算法允许一个节点弹出 k 次, 并且每次弹出这个节点的时候要抹掉该点当前的最优值. 因而我们在维护优先队列的同时, 需要维护两个表. 第一个表记录每一个节点被弹出的次数, 用来控制每个节点最后恰好只弹出 k 次; 第二个表用来记录 s 到所有点的前 k 短距离, 每次弹出节点的时候要在这里记录之后方可抹掉.
现在 k 最优 Dijkstra 算法已经描述完毕.
k 最优 Dijkstra 算法的本质是反复运用贪心策略. 注意它和 Dijkstra 算法的适用范围相同, 都只能适用在正权图上. 而它相比前面所述的普适算法, 不仅时间代价小了很多, 而且可以求出一个点到所有点的前 k 短路径. 我们利用之前的普适算法和这个算法, 来给出一个 problem 1.1 的完整解答.
Answer 1.1
一般地, 如果该图存在负权的边, 那么我们就采用上述的前 k 短路径的普适算法来求解. 我们使用 SPFA 算法来做单次的最短路径, 并且用上述的删边方法来维护一个优先队列. 该队列弹出的前 k 个结果, 就是 s 到 t 的前 k 短路径.
特殊地, 如果该图是一个正权图, 那么我们采用 k 最优 Dijkstra 算法即可得到 s 到所有点的最短路径.
完.
现在 k 最优 Dijkstra 算法已经描述完毕.
k 最优 Dijkstra 算法的本质是反复运用贪心策略. 注意它和 Dijkstra 算法的适用范围相同, 都只能适用在正权图上. 而它相比前面所述的普适算法, 不仅时间代价小了很多, 而且可以求出一个点到所有点的前 k 短路径. 我们利用之前的普适算法和这个算法, 来给出一个 problem 1.1 的完整解答.
Answer 1.1
一般地, 如果该图存在负权的边, 那么我们就采用上述的前 k 短路径的普适算法来求解. 我们使用 SPFA 算法来做单次的最短路径, 并且用上述的删边方法来维护一个优先队列. 该队列弹出的前 k 个结果, 就是 s 到 t 的前 k 短路径.
特殊地, 如果该图是一个正权图, 那么我们采用 k 最优 Dijkstra 算法即可得到 s 到所有点的最短路径.
完.
RSS Feed
