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

发表于 | 分类于 ， | 热度 ℃
字数统计: 895 | 阅读时长 ≈ 5

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 ;
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！