K短路问题

Published: by Creative Commons Licence

  • Tags:

K短路问题

K短路问题是给定一副有向图,要求找到从$s$到$t$的权值和最小的k条路径。

k短路的最简单的解决方法是直接用Dijkstra算法,优先队列中存储的是(顶点,距离)这样的二元信息,在找到终点后并不结束,而是继续找下去,直到终点出现k次为止。

上面的算法显然是对的,但是时间复杂度非常差(实际我都不知道这个算法的时间复杂度的上界)。

一种有效的优化方案是引入A*启发式算法,具体做法是首先我们找到从所有顶点到$t$的最小距离$d_t(i)$,这里可以将边翻转后以$t$为起点跑dijkstra算法。之后对于每个二元信息$(u,d)$,其具体的用于比较的权重为$d+d_t(u)$。加入这个优化可以大幅减少需要处理的状态,其时间复杂度为$O(kE\log_2kE)$。

实际上还有一种更加高效的做法,叫做Eppstein算法,它的时间复杂度为$O(E\log_2E+k\log_2k)$,论文地址。下面简单描述一下做法。

具体的思路是我们先找到以$t$为根的任意一颗最短路树$T_1$。那么从$s$到$t$的k短路中一定是包含两类边,一类边是树边,一类是非树边。我们可以枚举这些非树边。对于非树边$e=(u,v,c)$,记$delta(e)=d_t(v)+c-d_t(u)$。我们发现如果某条k短路上的非树边为$e_1,e_2,\ldots,e_l$,那么这条路径的权重$d_t(s)+\sum_{i=1}^ldelta(e_i)$。

记录$S(u)$为非树边的一个子集,其中边的起点为$T_1$中$u$到$t$路径上的某个顶点。之后我们以$s$为起点建立另外一株树$T_2$,在这株树上,原来的第k短路中出现的非树边,对应$T_2$中从根出发的第k短路径上的边,而后者我们可以用贪心算法求解,时间复杂度为$O(k\log_2k)$。

这里比较难的点是维护$S$,这里可以直接用持久化可并堆来实现。时间复杂度为$O(E\log_2E)$。

因此总的时间复杂度为$O(E\log_2E+k\log_2k)$。

提供一道题目