k 短路
问题描述
给定一个有 n 个结点,m 条边的有向图,求从 s 到 t 的所有不同路径中的第 k 短路径的长度。
A*算法
A*算法定义了一个对当前状态 x 的估价函数 f(x)=g(x)+h(x) ,其中 g(x) 为从初始状态到达当前状态的实际代价,h(x) 为从当前状态到达目标状态的最佳路径的估计代价。每次取出 f(x) 最优的状态 x ,扩展其所有子状态,可以用 优先队列 来维护这个值。
在求解 k 短路问题时,令 h(x) 为从当前结点到达终点 t 的最短路径长度。可以通过在反向图上对结点 t 跑单源最短路预处理出对每个结点的这个值。
由于设计的距离函数和估价函数,对于每个状态需要记录两个值,为当前到达的结点 x 和已经走过的距离 g(x) ,将这种状态记为 (x,g(x)) 。
开始我们将初始状态 (s,0) 加入优先队列。每次我们取出估价函数 f(x)=g(x)+h(x) 最小的一个状态,枚举该状态到达的结点 x 的所有出边,将对应的子状态加入优先队列。当我们访问到一个结点第 k 次时,对应的状态的 g(x) 就是从 x 到该结点的第 k 短路。
优化:由于只需要求出从初始结点到目标结点的第 k 短路,所以已经取出的状态到达一个结点的次数大于 k 次时,可以不扩展其子状态。因为之前 k 次已经形成了 k 条合法路径,当前状态不会影响到最后的答案。
当图的形态是一个 n 元环的时候,该算法最坏是 O(nk\log n) 的。但是这种算法可以在相同的复杂度内求出从起始点 s 到每个结点的前 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 #include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std ;
const int maxn = 5010 ;
const int maxm = 400010 ;
const int inf = 2e9 ;
int n , m , s , t , k , u , v , ww , H [ maxn ], cnt [ maxn ];
int cur , h [ maxn ], nxt [ maxm ], p [ maxm ], w [ maxm ];
int cur1 , h1 [ maxn ], nxt1 [ maxm ], p1 [ maxm ], w1 [ maxm ];
bool tf [ maxn ];
void add_edge ( int x , int y , double z ) {
cur ++ ;
nxt [ cur ] = h [ x ];
h [ x ] = cur ;
p [ cur ] = y ;
w [ cur ] = z ;
}
void add_edge1 ( int x , int y , double z ) {
cur1 ++ ;
nxt1 [ cur1 ] = h1 [ x ];
h1 [ x ] = cur1 ;
p1 [ cur1 ] = y ;
w1 [ cur1 ] = z ;
}
struct node {
int x , v ;
bool operator < ( node a ) const { return v + H [ x ] > a . v + H [ a . x ]; }
};
priority_queue < node > q ;
struct node2 {
int x , v ;
bool operator < ( node2 a ) const { return v > a . v ; }
} x ;
priority_queue < node2 > Q ;
int main () {
scanf ( "%d%d%d%d%d" , & n , & m , & s , & t , & k );
while ( m -- ) {
scanf ( "%d%d%d" , & u , & v , & ww );
add_edge ( u , v , ww );
add_edge1 ( v , u , ww );
}
for ( int i = 1 ; i <= n ; i ++ ) H [ i ] = inf ;
Q . push ({ t , 0 });
while ( ! Q . empty ()) {
x = Q . top ();
Q . pop ();
if ( tf [ x . x ]) continue ;
tf [ x . x ] = true ;
H [ x . x ] = x . v ;
for ( int j = h1 [ x . x ]; j ; j = nxt1 [ j ]) Q . push ({ p1 [ j ], x . v + w1 [ j ]});
}
q . push ({ s , 0 });
while ( ! q . empty ()) {
node x = q . top ();
q . pop ();
cnt [ x . x ] ++ ;
if ( x . x == t && cnt [ x . x ] == k ) {
printf ( "%d \n " , x . v );
return 0 ;
}
if ( cnt [ x . x ] > k ) continue ;
for ( int j = h [ x . x ]; j ; j = nxt [ j ]) q . push ({ p [ j ], x . v + w [ j ]});
}
printf ( "-1 \n " );
return 0 ;
}
可持久化可并堆优化 k 短路算法
最短路树与任意路径的关系与性质
在反向图上从 t 开始跑最短路,设在原图上结点 x 到 t 的最短路长度为 dist_x ,建出 任意 一棵以 t 为根的最短路树 T 。
所谓最短路径树,就是满足从树上的每个结点 x 到根节点 t 的简单路径都是 x 到 t 的 其中 一条最短路径。
设一条从 s 到 t 的路径经过的边集为 P ,去掉 P 中与 T 的交集得到 P' 。
P' 有如下性质:
对于一条不在 T 上的边 e ,其为从 u 到 v 的一条边,边权为 w ,定义其代价 \Delta e=dist_v+w-dist_u ,即为选择该边后路径长度的增加量。则路径 P 的长度 L_P=dist_s+\sum_{e\in P'} \Delta e 。
将 P 和 P' 中的所有边按照从 s 到 t 所经过的顺序依次排列,则对于 P' 中相邻的两条边 e_1,e_2 ,有 u_{e_2} 与 v_{e_1} 相等或为其在 T 上的祖先。因为在 P 中 e_1,e_2 直接相连或中间都为树边。
对于一个确定存在的 P' ,有且仅有一个 S ,使得 S'=P' 。因为由于性质 2 ,P' 中相邻的两条边的起点和终点之间在 T 上只有一条路径。
问题转化
性质 1 告诉我们知道集合 P' 后,如何求出 L_P 的值。
性质 2 告诉我们所有 P' 一定满足的条件,所有满足这个条件的边集 P' 都是合法的,也就告诉我们生成 P' 的方法。
性质 3 告诉我们对于每个合法的 P' 有且仅有一个边集 P 与之对应。
那么问题转化为:求 L_P 的值第 k 小的满足性质 2 的集合 P' 。
算法描述
由于性质 2 ,我们可以记录按照从 s 到 t 的顺序排列的最后一条边和 L_P 的值,来表示一个边集 P' 。
我们用一个小根堆来维护这样的边集 P' 。
初始我们将起点为 1 或 1 在 T 上的祖先的所有的边中 \Delta e 最小的一条边加入小根堆。
每次取出堆顶的一个边集 S ,有两种方法可以生成可能的新边集:
替换 S 中的最后一条边为满足相同条件的 \Delta e 更大的边。
在最后一条边后接上一条边,设 x 为 S 中最后一条边的终点,由性质 2 可得这条边需要满足其起点为 x 或 x 在 T 上的祖先。
将生成的新边集也加入小根堆。重复以上操作 k-1 次后求出的就是从 s 到 t 的第 k 短路。
对于每个结点 x ,我们将以其为起点的边的 \Delta e 建成一个小根堆。为了方便查找一个结点 x 与 x 在 T 上的祖先在小根堆上的信息,我们将这些信息合并在一个编号为 x 的小根堆上。回顾以上生成新边集的方法,我们发现只要我们把紧接着可能的下一个边集加入小根堆,并保证这种生成方法可以覆盖所有可能的边集即可。记录最后选择的一条边在堆上对应的结点 t ,有更优的方法生成新的边集:
替换 S 中的最后一条边为 t 在堆上的左右儿子对应的边。
在最后一条边后接上一条新的边,设 x 为 S 中最后一条边的终点,则接上编号为 x 的小根堆的堆顶结点对应的边。
用这种方法,每次生成新的边集只会扩展出最多三个结点,小根堆中的结点总数是 O(n+k) 。
所以此算法的瓶颈在合并一个结点与其在 T 上的祖先的信息,如果使用朴素的二叉堆,时间复杂度为 O(nm\log m) ,空间复杂度为 O(nm) ;如果使用可并堆,每次仍然需要复制堆中的全部结点,时间复杂度同样无法承受。
可持久化可并堆优化
在阅读本内容前,请先了解 可持久化可并堆 的相关知识。
使用可持久化可并堆优化合并一个结点与其在 T 上的祖先的信息,
每次将一个结点与其在 T 上的父亲合并,时间复杂度为 O((n+m)\log m+k\log k) ,空间复杂度为 O(m+n\log m+k) 。这样在求出一个结点对应的堆时,无需复制结点且之后其父亲结点对应的堆仍然可以正常访问。
注意的是,如上文所言,最终询问时不需要可并堆的合并操作。
询问时使用优先队列维护可并堆的根,对于可并堆堆顶的删除,直接将其左右儿子加入优先队列中,
就只需要 O(k) 而非 O(k\log m) 的空间。
参考实现
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127 #include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std ;
const int maxn = 200010 ;
int n , m , s , t , k , x , y , ww , cnt , fa [ maxn ];
struct Edge {
int cur , h [ maxn ], nxt [ maxn ], p [ maxn ], w [ maxn ];
void add_edge ( int x , int y , int z ) {
cur ++ ;
nxt [ cur ] = h [ x ];
h [ x ] = cur ;
p [ cur ] = y ;
w [ cur ] = z ;
}
} e1 , e2 ;
int dist [ maxn ];
bool tf [ maxn ], vis [ maxn ], ontree [ maxn ];
struct node {
int x , v ;
node * operator = ( node a ) {
x = a . x ;
v = a . v ;
return this ;
}
bool operator < ( node a ) const { return v > a . v ; }
} a ;
priority_queue < node > Q ;
void dfs ( int x ) {
vis [ x ] = true ;
for ( int j = e2 . h [ x ]; j ; j = e2 . nxt [ j ])
if ( ! vis [ e2 . p [ j ]])
if ( dist [ e2 . p [ j ]] == dist [ x ] + e2 . w [ j ])
fa [ e2 . p [ j ]] = x , ontree [ j ] = true , dfs ( e2 . p [ j ]);
}
struct LeftistTree {
int cnt , rt [ maxn ], lc [ maxn * 20 ], rc [ maxn * 20 ], dist [ maxn * 20 ];
node v [ maxn * 20 ];
LeftistTree () { dist [ 0 ] = -1 ; }
int newnode ( node w ) {
cnt ++ ;
v [ cnt ] = w ;
return cnt ;
}
int merge ( int x , int y ) {
if ( ! x || ! y ) return x + y ;
if ( v [ x ] < v [ y ]) swap ( x , y );
int p = ++ cnt ;
lc [ p ] = lc [ x ];
v [ p ] = v [ x ];
rc [ p ] = merge ( rc [ x ], y );
if ( dist [ lc [ p ]] < dist [ rc [ p ]]) swap ( lc [ p ], rc [ p ]);
dist [ p ] = dist [ rc [ p ]] + 1 ;
return p ;
}
} st ;
void dfs2 ( int x ) {
vis [ x ] = true ;
if ( fa [ x ]) st . rt [ x ] = st . merge ( st . rt [ x ], st . rt [ fa [ x ]]);
for ( int j = e2 . h [ x ]; j ; j = e2 . nxt [ j ])
if ( fa [ e2 . p [ j ]] == x && ! vis [ e2 . p [ j ]]) dfs2 ( e2 . p [ j ]);
}
int main () {
scanf ( "%d%d%d%d%d" , & n , & m , & s , & t , & k );
for ( int i = 1 ; i <= m ; i ++ )
scanf ( "%d%d%d" , & x , & y , & ww ), e1 . add_edge ( x , y , ww ), e2 . add_edge ( y , x , ww );
Q . push ({ t , 0 });
while ( ! Q . empty ()) {
a = Q . top ();
Q . pop ();
if ( tf [ a . x ]) continue ;
tf [ a . x ] = true ;
dist [ a . x ] = a . v ;
for ( int j = e2 . h [ a . x ]; j ; j = e2 . nxt [ j ]) Q . push ({ e2 . p [ j ], a . v + e2 . w [ j ]});
}
if ( k == 1 ) {
if ( tf [ s ])
printf ( "%d \n " , dist [ s ]);
else
printf ( "-1 \n " );
return 0 ;
}
dfs ( t );
for ( int i = 1 ; i <= n ; i ++ )
if ( tf [ i ])
for ( int j = e1 . h [ i ]; j ; j = e1 . nxt [ j ])
if ( ! ontree [ j ])
if ( tf [ e1 . p [ j ]])
st . rt [ i ] = st . merge (
st . rt [ i ],
st . newnode ({ e1 . p [ j ], dist [ e1 . p [ j ]] + e1 . w [ j ] - dist [ i ]}));
for ( int i = 1 ; i <= n ; i ++ ) vis [ i ] = false ;
dfs2 ( t );
if ( st . rt [ s ]) Q . push ({ st . rt [ s ], dist [ s ] + st . v [ st . rt [ s ]]. v });
while ( ! Q . empty ()) {
a = Q . top ();
Q . pop ();
cnt ++ ;
if ( cnt == k - 1 ) {
printf ( "%d \n " , a . v );
return 0 ;
}
if ( st . lc [ a . x ]) // 可并堆删除直接把左右儿子加入优先队列中
Q . push ({ st . lc [ a . x ], a . v - st . v [ a . x ]. v + st . v [ st . lc [ a . x ]]. v });
if ( st . rc [ a . x ])
Q . push ({ st . rc [ a . x ], a . v - st . v [ a . x ]. v + st . v [ st . rc [ a . x ]]. v });
x = st . rt [ st . v [ a . x ]. x ];
if ( x ) Q . push ({ x , a . v + st . v [ x ]. v });
}
printf ( "-1 \n " );
return 0 ;
}
习题
「SDOI2010」魔法猪学院
build 本页面最近更新: ,更新历史
edit 发现错误?想一起完善? 在 GitHub 上编辑此页!
people 本页面贡献者:OI-wiki
copyright 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用