隐藏
使用可持久化可并堆解决$k$短路问题 | Bill Yang's Blog
0%

使用可持久化可并堆解决$k$短路问题

$k$短路问题

$k$短路是一类经典问题,问题描述为:

给出一张任意图,询问图中$s\rightarrow t$的任意路径中长度第$k$小的。
其中路径的长度定义为构成路径的边的权值和。

经典$A^*$算法

$k$短路可以使用$A^*$算法解决,算法思想极为简单。

首先使用dijkstraSPFA算法求出原图以$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
72
int 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)$为两点间最短路径长度。

转化问题

首先使用dijkstraSPFA算法求出原图以$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$短路。

  1. 从当前状态扩展到的下一状态合法。
  2. 扩展的阶段一定满足答案从小到大递增。

考虑,若当前状态有一条合法路径$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
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
const int maxn=1005;

struct Tree {
Tree *ls,*rs;
int dist;
int val,back;
Tree(int d=0,int v=0,int b=0):dist(d),val(v),back(b) {
ls=rs=NULL;
}
};

struct Left_Side_Tree {
Tree* merge(Tree *x,Tree *y) {
if(!x||!y)return x?x:y;
if(x->val>y->val)swap(x,y);
Tree *New=new Tree;
*New=*x;
New->rs=merge(New->rs,y);
if(!New->ls||New->rs->dist>New->ls->dist)swap(New->ls,New->rs);
if(New->rs)New->dist=New->rs->dist+1;
return New;
}
Tree* push(Tree *x,int v,int b) {
Tree *New=new Tree(0,v,b);
return merge(x,New);
}
} heap;

Tree *root[maxn];

struct Edge {
int from,to,dist;
};

int n,m,s,t,k,father[maxn],father_e[maxn],dist[maxn];
bool vst[maxn];
vector<Edge> edges,fedges;
vector<int> G[maxn],fG[maxn];

void AddEdge(int x,int y,int v) {
edges.push_back((Edge) {x,y,v});
G[x].push_back(edges.size()-1);
fedges.push_back((Edge) {y,x,v});
fG[y].push_back(fedges.size()-1);
}

#define pii pair<int,int>
#define mp make_pair

void Dijkstra() {
for(int i=1; i<=n; i++)dist[i]=INT_MAX/2,vst[i]=0;
dist[t]=0;
father_e[t]=-1;
priority_queue<pii,vector<pii>,greater<pii> > Q;
Q.push(mp(0,t));
while(!Q.empty()) {
int Now=Q.top().second;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(int id:fG[Now]) {
Edge& e=fedges[id];
int Next=e.to;
if(dist[Next]>dist[Now]+e.dist) {
dist[Next]=dist[Now]+e.dist;
father[Next]=Now;
father_e[Next]=id; //重边!!!
Q.push(mp(dist[Next],Next));
}
}
}
}

void Dfs(int Now) {
if(father[Now])root[Now]=root[father[Now]];
for(int id:G[Now]) {
if(id==father_e[Now])continue;
Edge& e=edges[id];
int Next=e.to;
root[Now]=heap.push(root[Now],e.dist+dist[Next]-dist[Now],Next);
}
for(int id:fG[Now]) {
Edge& e=fedges[id];
int Next=e.to;
if(id==father_e[Next])Dfs(Next);
}
}

#undef pii
#define pii pair<int,Tree *>

int solve() {
Dijkstra();
if(dist[t]==INT_MAX/2)return -1;
k--;
if(!k)return dist[t];
Dfs(t);
priority_queue<pii,vector<pii>,greater<pii> > Q;
if(root[s])Q.push(mp(dist[s]+root[s]->val,root[s]));
while(!Q.empty()) {
pii Now=Q.top();
int len=Now.first;
Tree *rt=Now.second;
Q.pop();
k--;
if(!k)retur len;
Tree *next=root[rt->back],*ls=rt->ls,*rs=rt->rs;
if(next)Q.push(mp(len+next->val,next));
if(ls)Q.push(mp(len+ls->val-rt->val,ls));
if(rs)Q.push(mp(len+rs->val-rt->val,rs));
}
return -1;
}
姥爷们赏瓶冰阔落吧~