[最短路]SPFA的SLF与LLL优化

SPFA是按照 FIFO 的原则更新距离的, 没有考虑到距离标号的作用。实现中 SPFA 有两个非常著名的优化: SLF 和 LLL。

SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j) < dist(i),则将j插入队首,否则插入队尾。

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
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <deque>
const int inf = 1 << 30 , maxn = 100000 + 11 , M = 200000 + 11 ;
using namespace std ;//1061109567
int n , m , head[maxn] , dis[maxn] , cnt , sum , tot ;
bool mark[maxn] ;
struct id
{
int nxt ,to , val ;
} edge[M] ;
deque < int > Q ;


inline void Init ( )
{
freopen( "NSOOJ#10719.in" , "r" , stdin ) ;
freopen( "NSOOJ#10719.out" , "w" , stdout ) ;
}

int read( )
{
char ch = getchar( ) ; int k = 1 , ret = 0 ;
while( ch < '0' || ch > '9' ) { if( ch == '-' ) k = -1 ; ch = getchar( ) ; }
while( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' , ch = getchar( ) ;
return k * ret ;
}

void add( int u , int v , int va )
{
edge[++cnt].nxt = head[u] , edge[cnt].to = v ;
edge[cnt].val = va , head[u] = cnt ;
}

void input( )
{
n = read() , m = read( ) ;
int u ,v , c ;
memset( head , -1 , sizeof(head)) ;
for( int x = 1 ; x <= m ; ++x )
{
u = read( ) , v = read( ) , c = read( ) ;
add( u ,v , c ) ;
}
}

void spfa( )
{
memset( dis , 127/2 , sizeof(dis) ) ;
dis[1] = 0 , mark[1] = true ;
Q.push_back( 1 ) ;
while( !Q.empty( ) )
{
int u = Q.front( ) ; Q.pop_front( ) ; mark[u] = false ;

for( int i = head[u] ; ~i ; i = edge[i].nxt )
{
int v = edge[i].to ;
if( dis[v] > dis[u] + edge[i].val )
{
dis[v] = dis[u] + edge[i].val ;
if( !mark[v] )
{
mark[v] = true ;
if( Q.empty( ) || dis[v] > dis[Q.front( )] ) Q.push_back( v ) ;
else Q.push_front( v ) ;

}

}
}
}
if( dis[n] == 1061109567 ) printf( "%d\n" , -1 ) ;
else printf( "%d\n" , dis[n] ) ;
}


int main( )
{
// Init( ) ;
input( ) ;
spfa( ) ;
// fclose( stdin ) ;
// fclose( stdout ) ;
return 0 ;
}

LLL:Large Label Last 策略,设队首元素为i,每次弹出时进行判断,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,每次出队时,若 d[i]>平均值,把 i 移到队列末尾,如此反复,直到找到某一i使得dist(i)<=x,则将i出队进行松弛操作。

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
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <deque>
const int inf = 1 << 30 , maxn = 100000 + 11 , M = 200000 + 11 ;
using namespace std ;//1061109567
int n , m , head[maxn] , dis[maxn] , cnt , sum , tot ;
bool mark[maxn] ;
struct id
{
int nxt ,to , val ;
} edge[M] ;
deque < int > Q ;


inline void Init ( )

{
freopen( "NSOOJ#10719.in" , "r" , stdin ) ;
freopen( "NSOOJ#10719.out" , "w" , stdout ) ;
}

int read( )
{
char ch = getchar( ) ; int k = 1 , ret = 0 ;
while( ch < '0' || ch > '9' ) { if( ch == '-' ) k = -1 ; ch = getchar( ) ; }
while( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' , ch = getchar( ) ;
return k * ret ;
}

void add( int u , int v , int va )
{
edge[++cnt].nxt = head[u] , edge[cnt].to = v ;
edge[cnt].val = va , head[u] = cnt ;
}

void input( )
{
n = read() , m = read( ) ;
int u ,v , c ;
memset( head , -1 , sizeof(head)) ;
for( int x = 1 ; x <= m ; ++x )
{
u = read( ) , v = read( ) , c = read( ) ;
add( u ,v , c ) ;
}
}

void spfa( )
{
memset( dis , 127/2 , sizeof(dis) ) ;
dis[1] = 0 , mark[1] = true ;
Q.push_back( 1 ) ; tot = 0 ;
while( !Q.empty( ) )
{
int u = Q.front( ) ;
Q.pop_front( ) ;
if( dis[u] * tot > sum )
{
Q.push_back( u ) ;
continue;
}
mark[u] = false ;
tot-- ; sum -= dis[u] ;
for( int i = head[u] ; ~i ; i = edge[i].nxt )
{
int v = edge[i].to ;
if( dis[v] > dis[u] + edge[i].val )
{
dis[v] = dis[u] + edge[i].val ;
if( !mark[v] )
{
mark[v] = true ;
if( Q.empty( ) || dis[v] * tot > sum ) Q.push_back( v ) ;
else Q.push_front( v ) ;
tot++ ; sum += dis[v] ;
}

}
}
}
if( dis[n] == 1061109567 ) printf( "%d\n" , -1 ) ;
else printf( "%d\n" , dis[n] ) ;
}


int main( )
{
// Init( ) ;
input( ) ;
spfa( ) ;
// fclose( stdin ) ;
// fclose( stdout ) ;
return 0 ;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!