【单源最短路】SPFA及其优化

SPFA及其优化

一、SPFA

 单源最短路径,不多解释。

二、优化

 1.SLF优化

SLF叫做Small Label First 策略。

比较当前点和队首元素,如果小于队首,则插入队首,否则加入队尾。

2.LLL优化(慎用)

LLL叫做Large Label Last 策略。

设队首元素为i,每次弹出时进行判断,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。

三、实现

题目以POJ的3259-Wormholes为例。

http://poj.org/problem?id=3259

1.无优化 

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 struct Node{
 9     int to,value;
10 };
11 int N,M,W;
12 vector<Node>G[1000];
13 int dis[1000],times[1000];
14 bool vis[1000];
15 bool SPFA(int u){
16     queue<int>Q;
17     memset(dis,0x3f,sizeof(dis));
18     memset(vis,false,sizeof(vis));
19     
20     Q.push(u);
21     dis[u]=0;
22     times[u]++;
23     while(!Q.empty()){
24         int tmp=Q.front();Q.pop();
25         int sz=G[tmp].size();
26         for(int i=0;i<sz;i++){
27             int to=G[tmp][i].to,value=G[tmp][i].value;
28             if(dis[to]>dis[tmp]+value){
29                 dis[to]=dis[tmp]+value;
30                 if(!vis[to]){
31                     Q.push(to);
32                     vis[to]=true;
33                     times[to]++;
34                     if(times[to]>N)return true;
35                 }
36             }
37         }
38         vis[tmp]=false;
39     }
40     return false;
41 }
42 int main(){
43     Node node;
44     int T;scanf("%d",&T);
45     while(T--){
46         memset(times,0,sizeof(times));
47         for(int i=1;i<1000;i++)G[i].clear();
48         
49         scanf("%d%d%d",&N,&M,&W);
50         for(int i=1;i<=M;i++){
51             int u;scanf("%d%d%d",&u,&node.to,&node.value);
52             G[u].push_back(node);
53             swap(u,node.to);
54             G[u].push_back(node);
55         }
56         for(int i=1;i<=W;i++){
57             int u;scanf("%d%d%d",&u,&node.to,&node.value);
58             node.value=-node.value;
59             G[u].push_back(node);
60         }
61         bool flag=SPFA(1);
62         if(flag)printf("YES\n");
63         else printf("NO\n");
64     }
65     
66     return 0;
67 }

跑了144ms

2、SLF优化

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 #include<deque>
 8 using namespace std;
 9 struct Node{
10     int to,value;
11 };
12 int N,M,W;
13 vector<Node>G[1000];
14 int dis[1000],times[1000];
15 bool vis[1000];
16 bool SPFA(int u){
17     //queue<int>Q;
18     deque<int>Q;
19     memset(dis,0x3f,sizeof(dis));
20     memset(vis,false,sizeof(vis));
21     
22     //Q.push(u);
23     Q.push_back(u);
24     dis[u]=0;
25     times[u]++;
26     while(!Q.empty()){
27         int tmp=Q.front();//Q.pop();
28         Q.pop_front();
29         int sz=G[tmp].size();
30         for(int i=0;i<sz;i++){
31             int to=G[tmp][i].to,value=G[tmp][i].value;
32             if(dis[to]>dis[tmp]+value){
33                 dis[to]=dis[tmp]+value;
34                 if(!vis[to]){
35                     //Q.push(to);
36                     if(Q.empty()||dis[to]>dis[Q.front()])
37                         Q.push_back(to);
38                     else
39                         Q.push_front(to);
40                     
41                     vis[to]=true;
42                     times[to]++;
43                     if(times[to]>N)return true;
44                 }
45             }
46         }
47         vis[tmp]=false;
48     }
49     return false;
50 }
51 int main(){
52     Node node;
53     int T;scanf("%d",&T);
54     while(T--){
55         memset(times,0,sizeof(times));
56         for(int i=1;i<1000;i++)G[i].clear();
57         
58         scanf("%d%d%d",&N,&M,&W);
59         for(int i=1;i<=M;i++){
60             int u;scanf("%d%d%d",&u,&node.to,&node.value);
61             G[u].push_back(node);
62             swap(u,node.to);
63             G[u].push_back(node);
64         }
65         for(int i=1;i<=W;i++){
66             int u;scanf("%d%d%d",&u,&node.to,&node.value);
67             node.value=-node.value;
68             G[u].push_back(node);
69         }
70         bool flag=SPFA(1);
71         if(flag)printf("YES\n");
72         else printf("NO\n");
73     }
74     
75     return 0;
76 }

这是加了优化的代码,速度提高了。

注释是无优化的,可以对照着看。

3、LLL优化

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 #include<deque>
 8 using namespace std;
 9 struct Node{
10     int to,value;
11 };
12 int N,M,W;
13 vector<Node>G[1000];
14 int dis[1000],times[1000];
15 bool vis[1000];
16 
17 //
18 int tot,sum;
19 int pre[1000];
20 bool SPFA(int u){
21     //queue<int>Q;
22     deque<int>Q;
23     memset(dis,0x3f,sizeof(dis));
24     memset(vis,false,sizeof(vis));
25     memset(pre,0,sizeof(pre));
26     
27     //Q.push(u);
28     Q.push_back(u);
29     dis[u]=0;
30     times[u]++;
31     //
32     pre[u]=-1;tot=1;sum=0;
33     while(!Q.empty()){
34         int tmp=Q.front();//Q.pop();
35         Q.pop_front();
36         int sz=G[tmp].size();
37         //
38         tot--;sum-=dis[tmp];
39         for(int i=0;i<sz;i++){
40             int to=G[tmp][i].to,value=G[tmp][i].value;
41             if(dis[to]>dis[tmp]+value){
42                 dis[to]=dis[tmp]+value;
43                 //
44                 pre[to]=tmp;
45                 if(!vis[to]){
46                     //Q.push(to);
47                     if(Q.empty()||dis[to]>dis[Q.front()]||dis[to]*tot<=sum)
48                         Q.push_back(to);
49                     else 
50                         Q.push_front(to);
51                     //
52                     tot++;sum+=dis[to];
53                     
54                     vis[to]=true;
55                     times[to]++;
56                     if(times[to]>N)return true;
57                 }
58             }
59         }
60         vis[tmp]=false;
61     }
62     return false;
63 }
64 int main(){
65     Node node;
66     int T;scanf("%d",&T);
67     while(T--){
68         memset(times,0,sizeof(times));
69         for(int i=1;i<1000;i++)G[i].clear();
70         
71         scanf("%d%d%d",&N,&M,&W);
72         for(int i=1;i<=M;i++){
73             int u;scanf("%d%d%d",&u,&node.to,&node.value);
74             G[u].push_back(node);
75             swap(u,node.to);
76             G[u].push_back(node);
77         }
78         for(int i=1;i<=W;i++){
79             int u;scanf("%d%d%d",&u,&node.to,&node.value);
80             node.value=-node.value;
81             G[u].push_back(node);
82         }
83         bool flag=SPFA(1);
84         if(flag)printf("YES\n");
85         else printf("NO\n");
86     }
87     
88     return 0;
89 }

速度反而下降,可能是因为LLL不稳定,容易被卡。(注:仅一家之谈)

 

最后:感谢

star_eternal的博客