$k$短路问题
$k$短路是一类经典问题，问题描述为：
给出一张任意图，询问图中$s\rightarrow t$的任意路径中长度第$k$小的。
其中路径的长度定义为构成路径的边的权值和。
经典$A^*$算法
$k$短路可以使用$A^*$算法解决，算法思想极为简单。
首先使用dijkstra或SPFA算法求出原图以$t$为根的最短路树。
以到达终点的最短路作为估价函数$h$，以已经经过的路径长度作为$g$，使用$f=g+h$作为估价用小根堆维护。
实现起来也很简单，介于本文题目，此处不详述，下面给出主要代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72int n;
struct Edge {
int from,to,dist;
};
struct SPFA {
int m;
vector<Edge> edges[maxn];
int dist[maxn],inque[maxn];
void AddEdge(int from,int to,int dist) {
edges[from].push_back((Edge) {from,to,dist});
}
void main(int s) {
for(int i=1; i<=n; i++)dist[i]=INT_MAX/2;
queue<int>Q;
Q.push(s);
dist[s]=0;
inque[s]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
inque[Now]=0;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(dist[Next]>dist[Now]+e.dist) {
dist[Next]=dist[Now]+e.dist;
if(!inque[Next]) {
inque[Next]=1;
Q.push(Next);
}
}
}
}
}
} spfa;
vector<Edge> edges[maxn];
void AddEdge(int from,int to,int dist) {
edges[from].push_back((Edge) {from,to,dist});
}
struct HeapNode {
int f,g,u;
bool operator < (const HeapNode& b) const {
return f>b.f;
}
};
int m,s,t,k,cnt=0;
int Astar() { //A* k短路
if(spfa.dist[s]==INT_MAX/2)return -1;
priority_queue<HeapNode>Q;
Q.push((HeapNode) {
spfa.dist[s],0,s
});
while(!Q.empty()) {
HeapNode Now=Q.top();
Q.pop();
if(Now.u==t)cnt++;
if(cnt==k)return Now.g;
for(Edge& e:edges[Now.u]) {
int Next=e.to;
Q.push((HeapNode) {
Now.g+e.dist+spfa.dist[Next],Now.g+e.dist,Next
});
}
}
return -1;
}
可持久化可并堆
一些记号
在后文中，将会采用以下记号，其意义如下。
- 原图为$G(V,E)$，其中$V$为点集，$E$为边集。
- 所求问题的起点为$s$，终点为$t$。
- 对于有向边$e(u\rightarrow v)$，记$head(e)$为$u$，$tail(e)$为$v$，该有向边的长度为$len(e)$。
- 对于路径$p$，记$len(p)$为路径长度。
- 对于两点$u,v\in V$，记$dist(u,v)$为两点间最短路径长度。
转化问题
首先使用dijkstra或SPFA算法求出原图以$t$为根的任意一棵最短路径树，记为$T$。
对于一条$E$中的边$e$，记$\delta(e)=len(e)+dist(tail(e),t)-dist(head(e),t)$。
形象地理解$\delta(e)$的含义为加入这条边后对$s\rightarrow t$路径长度所引起的变化。
显然对于$e\in E$，有$\delta(e)\ge0$，对于$e\in T$，有$\delta(e)=0$。
对于一条$s\rightarrow t$的路径$p$，记$side(p)$为$e\in(E\backslash T)\bigcap p$组成的有序集合，顺序为从$s\rightarrow t$所经过的顺序。
形象地理解$side(p)$的含义为从路径$p$上非树边组成的集合。
显然$len(p)=dist(s,t)+\sum\limits_{e\in side(p)}\delta(e)=dist(s,t)+\sum\limits_{e\in p}\delta(e)$。
对于一条合法的$side(p)$其中相邻的两条边$e,f$（$e$的顺序比$f$小），有$head(f)=tail(e)$或$head(f)$是$tail(e)$在$T$的祖先。
可以得到：一个合法的$side(p)$与原图中的一条路径一一对应。
证明不难，留给读者思考。
由于$dist(s,t)$是定值，现在问题转化为求前$k$小的$\sum\limits_{e\in p}\delta(e)$。
算法步骤
考虑，使用一个小根堆维护路径$p$，并通过路径$p$得到其长度$len(p)$更新答案。
根据求$k$大的套路，我们只需要状态的扩展满足以下两点要求，就可以保证堆所弹出的第$k$条路径即为$k$短路。
- 从当前状态扩展到的下一状态合法。
- 扩展的阶段一定满足答案从小到大递增。
考虑，若当前状态有一条合法路径$p$，如图所示：
我们可以通过选择一条$head(e)$在当前路径的最后一条非树边后的非树边更新当前的$p$与$side(p)$集合。
现在这条非树边$e$是新的最后一条非树边，故$tail(e)\rightarrow t$是树上的路径。
现在满足了第一个条件，状态合法。
考虑，我们每次扩展状态时考虑两种转移：
- 在最后一条非树边后接一条$\delta(e)$最小的非树边
- 将当前的最后一条非树边去掉，用一个$\delta(e)$稍大的非树边替换。
这样我们可以保证扩展的阶段从小到大递增，故满足第二个条件。
因此算法步骤为：
- 通过最短路算法构造出$T$。
- 用最短路计算并更新答案。
- 选出一条$head(e)$在$s$到$t$的最短路径上的非树边$e$，入堆。
- 从堆顶弹出一条路径，计算并更新答案。
- 在当前路径最后一条非树边后添加一条非树边。
- 弹出最后一条非树边，使用一条稍大的非树边替换其。
实现方法
目前我们的瓶颈在于如何快速的找到$head(e)$在$x\rightarrow t$的最短路上的边，并且能够找到其中$\delta(e)$最小的一条边$e$，并且能够在弹出最小后找到次小。
不难想到，堆可以完成问题所需的询问操作。
但，若对于所有$x$，需要在堆中加入$head(e)$在$x\rightarrow t$最短路上的所有$e$，时间效率极低。
不妨考虑使用可持久化可并堆来解决这个问题。
每一个结点$x$的堆从其$T$的父亲$father(x)$处继承父亲的堆，并在父亲堆的基础上加入$head(e)=x$的所有非树边。
这样便可以很快的预处理出所需用到的堆，问题解决。
关于环
初学者可能觉得这个算法只能解决DAG上的$k$短路问题，因为若有环可以重复选某一条非树边来更新$k$短，其实不然。
我们发现，若构成环，如图：
令人惊讶的是，这样的$side(p)$序列竟然仍然满足一一对应关系，图中即为的$side(p)$序列所对应的$p$为：$s\rightarrow v\rightarrow a\rightarrow u\rightarrow v\rightarrow b\rightarrow u\rightarrow t$。
并且在加入这条非树边后，问题又回到了最后一个点在$v$的情况。
因此，环也能被考虑到，本算法的应用范围扩展到任意图的任意$k$短路径。
时间复杂度
这是一个优秀的多项式算法，比非多项式算法$A^*$不知道高到哪里去了。
然而在具体实现时，因为常数原因，当$k$很小时，可并堆速度会慢一些。只有当$k$较大，才能体现出本算法的优越性。
代码
1 | const int maxn=1005; |
