K短路问题
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}^l\delta(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)$。
提供一道题目。