K短路问题
K短路问题
K短路问题是给定一副有向图，要求找到从s到t的权值和最小的k条路径。
k短路的最简单的解决方法是直接用Dijkstra算法，优先队列中存储的是(顶点，距离)这样的二元信息，在找到终点后并不结束，而是继续找下去，直到终点出现k次为止。
上面的算法显然是对的，但是时间复杂度非常差（实际我都不知道这个算法的时间复杂度的上界）。
一种有效的优化方案是引入A*启发式算法，具体做法是首先我们找到从所有顶点到t的最小距离dt(i)，这里可以将边翻转后以t为起点跑dijkstra算法。之后对于每个二元信息(u,d)，其具体的用于比较的权重为d+dt(u)。加入这个优化可以大幅减少需要处理的状态，其时间复杂度为O(kElog2kE)。
实际上还有一种更加高效的做法，叫做Eppstein算法，它的时间复杂度为O(Elog2E+klog2k)，论文地址。下面简单描述一下做法。
具体的思路是我们先找到以t为根的任意一颗最短路树T1。那么从s到t的k短路中一定是包含两类边，一类边是树边，一类是非树边。我们可以枚举这些非树边。对于非树边e=(u,v,c)，记δ(e)=dt(v)+c−dt(u)。我们发现如果某条k短路上的非树边为e1,e2,…,el，那么这条路径的权重dt(s)+∑li=1δ(ei)。
记录S(u)为非树边的一个子集，其中边的起点为T1中u到t路径上的某个顶点。之后我们以s为起点建立另外一株树T2，在这株树上，原来的第k短路中出现的非树边，对应T2中从根出发的第k短路径上的边，而后者我们可以用贪心算法求解，时间复杂度为O(klog2k)。
这里比较难的点是维护S，这里可以直接用持久化可并堆来实现。时间复杂度为O(Elog2E)。
因此总的时间复杂度为O(Elog2E+klog2k)。
提供一道题目。