基于各种基础数据结构的SPFA和各种优化

一、基于各种数据结构的SPFA

以下各个数据均为不卡SPFA的最短路模板：P3371 【模板】单源最短路径（弱化版）的测试时间

1、STL队列：用时: 1106ms / 内存: 8496KB

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<algorithm>
 7 #define inf 336860180
 8 using namespace std;
 9 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001]; 
10 bool vis[500001];
11 void add(int a,int b,int c)
12 {
13     v[++cnt]=b;
14     w[cnt]=c;
15     nxt[cnt]=head[a];
16     head[a]=cnt;
17 }
18 void read()
19 {
20     cin>>n>>m>>s;
21     for(int i=1;i<=m;i++)
22     {
23         cin>>x>>y>>z;
24         add(x,y,z);
25     }
26 } 
27 void spfa(int s)
28 {
29     memset(dist,20,sizeof(dist));
30     queue<int>q;
31     q.push(s);
32     vis[s]=1;
33     dist[s]=0;
34     while(!q.empty())
35     {
36         int t=q.front();
37         q.pop();
38         vis[t]=0;
39         for(int i=head[t];i;i=nxt[i])
40         {
41             int y=v[i];
42             if(dist[y]>dist[t]+w[i])
43             {
44                 dist[y]=dist[t]+w[i];
45                 if(!vis[y])
46                 {
47                     q.push(y);
48                     vis[y]=1;
49                 }
50             }
51         }
52     }
53 }
54 void pr()
55 {
56     for(int i=1;i<=n;i++)
57     {
58         if(dist[i]!=inf)cout<<dist[i];
59         else cout<<"2147483647";
60         cout<<" ";
61     } 
62 }
63 int main()
64 {
65     read();
66     spfa(s);
67     pr();
68     return 0;
69 }
View Code

2、STL栈：用时: 4257ms / 内存: 8536KB（#2，#9，#10TLE）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<stack>
 7 #include<algorithm>
 8 #define inf 336860180
 9 using namespace std;
10 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001]; 
11 bool vis[500001];
12 void add(int a,int b,int c)
13 {
14     v[++cnt]=b;
15     w[cnt]=c;
16     nxt[cnt]=head[a];
17     head[a]=cnt;
18 }
19 void read()
20 {
21     cin>>n>>m>>s;
22     for(int i=1;i<=m;i++)
23     {
24         cin>>x>>y>>z;
25         add(x,y,z);
26     }
27 } 
28 void spfa(int s)
29 {
30     memset(dist,20,sizeof(dist));
31     stack<int>q;
32     q.push(s);
33     vis[s]=1;
34     dist[s]=0;
35     while(!q.empty())
36     {
37         int t=q.top();
38         q.pop();
39         vis[t]=0;
40         for(int i=head[t];i;i=nxt[i])
41         {
42             int y=v[i];
43             if(dist[y]>dist[t]+w[i])
44             {
45                 dist[y]=dist[t]+w[i];
46                 if(!vis[y])
47                 {
48                     q.push(y);
49                     vis[y]=1;
50                 }
51             }
52         }
53     }
54 }
55 void pr()
56 {
57     for(int i=1;i<=n;i++)
58     {
59         if(dist[i]!=inf)cout<<dist[i];
60         else cout<<"2147483647";
61         cout<<" ";
62     } 
63 }
64 int main()
65 {
66     read();
67     spfa(s);
68     pr();
69     return 0;
70 }
View Code

3、模拟栈：用时: 4242ms / 内存: 8508KB（#2，#9，#10TLE）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<stack>
 7 #include<algorithm>
 8 #define inf 336860180
 9 using namespace std;
10 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],stk[500001],top; 
11 bool vis[500001];
12 void add(int a,int b,int c)
13 {
14     v[++cnt]=b;
15     w[cnt]=c;
16     nxt[cnt]=head[a];
17     head[a]=cnt;
18 }
19 void read()
20 {
21     cin>>n>>m>>s;
22     for(int i=1;i<=m;i++)
23     {
24         cin>>x>>y>>z;
25         add(x,y,z);
26     }
27 } 
28 void spfa(int s)
29 {
30     memset(dist,20,sizeof(dist));
31     top=1;
32     stk[top]=s;
33     vis[s]=1;
34     dist[s]=0;
35     while(top>0)
36     {
37         int t=stk[top];
38         top--;
39         vis[t]=0;
40         for(int i=head[t];i;i=nxt[i])
41         {
42             int y=v[i];
43             if(dist[y]>dist[t]+w[i])
44             {
45                 dist[y]=dist[t]+w[i];
46                 if(!vis[y])
47                 {
48                     stk[++top]=y;
49                     vis[y]=1;
50                 }
51             }
52         }
53     }
54 }
55 void pr()
56 {
57     for(int i=1;i<=n;i++)
58     {
59         if(dist[i]!=inf)cout<<dist[i];
60         else cout<<"2147483647";
61         cout<<" ";
62     } 
63 }
64 int main()
65 {
66     read();
67     spfa(s);
68     pr();
69     return 0;
70 }
View Code

4、STL优先队列：用时: 1377ms / 内存: 8612KB

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<stack>
 7 #include<algorithm>
 8 #define inf 336860180
 9 using namespace std;
10 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],stk[500001],top; 
11 bool vis[500001];
12 void add(int a,int b,int c)
13 {
14     v[++cnt]=b;
15     w[cnt]=c;
16     nxt[cnt]=head[a];
17     head[a]=cnt;
18 }
19 void read()
20 {
21     cin>>n>>m>>s;
22     for(int i=1;i<=m;i++)
23     {
24         cin>>x>>y>>z;
25         add(x,y,z);
26     }
27 } 
28 void spfa(int s)
29 {
30     memset(dist,20,sizeof(dist));
31     priority_queue<int>q;
32     q.push(s);
33     vis[s]=1;
34     dist[s]=0;
35     while(!q.empty())
36     {
37         int t=q.top();
38         q.pop();
39         vis[t]=0;
40         for(int i=head[t];i;i=nxt[i])
41         {
42             int y=v[i];
43             if(dist[y]>dist[t]+w[i])
44             {
45                 dist[y]=dist[t]+w[i];
46                 if(!vis[y])
47                 {
48                     q.push(y);
49                     vis[y]=1;
50                 }
51             }
52         }
53     }
54 }
55 void pr()
56 {
57     for(int i=1;i<=n;i++)
58     {
59         if(dist[i]!=inf)cout<<dist[i];
60         else cout<<"2147483647";
61         cout<<" ";
62     } 
63 }
64 int main()
65 {
66     read();
67     spfa(s);
68     pr();
69     return 0;
70 }
View Code

时间总的来说是这个样子的：STL栈>模拟栈>STL优先队列>STL队列

二、SPFA的优化

SPFA目前常见的优化有3种，分别是：SLF优化，LLL优化，随机优化。

1、SLF优化：

SLF优化采取的策略是开一个双端队列，如果即将入队节点大于队首值就插入前端，否则插入后端。是最常见的也是最好用的SPFA优化方法

用时: 1100ms / 内存: 8512KB

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<algorithm>
 7 #define inf 336860180
 8 using namespace std;
 9 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],sum; 
10 bool vis[500001];
11 void add(int a,int b,int c)
12 {
13     v[++cnt]=b;
14     w[cnt]=c;
15     nxt[cnt]=head[a];
16     head[a]=cnt;
17 }
18 void read()
19 {
20     cin>>n>>m>>s;
21     for(int i=1;i<=m;i++)
22     {
23         cin>>x>>y>>z;
24         add(x,y,z);
25     }
26 } 
27 void spfa(int s)
28 {
29     memset(dist,20,sizeof(dist));
30     deque<int>q;
31     q.push_back(s);
32     vis[s]=1;
33     dist[s]=0;
34     while(!q.empty())
35     {
36         int t=q.front();
37         q.pop_front();
38         vis[t]=0;
39         for(int i=head[t];i;i=nxt[i])
40         {
41             int y=v[i];
42             if(dist[y]>dist[t]+w[i])
43             {
44                 dist[y]=dist[t]+w[i];
45                 if(!vis[y])
46                 {
47                     if(dist[y]<=dist[q.front()])q.push_front(y);
48                     else q.push_back(y);
49                     vis[y]=1;
50                 }
51             }
52         }
53     }
54 }
55 void pr()
56 {
57     for(int i=1;i<=n;i++)
58     {
59         if(dist[i]!=inf)cout<<dist[i];
60         else cout<<"2147483647";
61         cout<<" ";
62     } 
63 }
64 int main()
65 {
66     read();
67     spfa(s);
68     pr();
69     return 0;
70 }
View Code

2、LLL优化：

LLL优化也是开一个双端队列，每次去队首看是否大于平均值，大于就插入队尾继续寻找。看起来高大上实际应用不多的SPFA优化

用时: 1114ms / 内存: 8500KB

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<queue>
 6 #include<algorithm>
 7 #define inf 336860180
 8 using namespace std;
 9 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],sum; 
10 bool vis[500001];
11 void add(int a,int b,int c)
12 {
13     v[++cnt]=b;
14     w[cnt]=c;
15     nxt[cnt]=head[a];
16     head[a]=cnt;
17 }
18 void read()
19 {
20     cin>>n>>m>>s;
21     for(int i=1;i<=m;i++)
22     {
23         cin>>x>>y>>z;
24         add(x,y,z);
25     }
26 } 
27 void spfa(int s)
28 {
29     memset(dist,20,sizeof(dist));
30     deque<int>q;
31     q.push_back(s);
32     vis[s]=1;
33     dist[s]=0;
34     while(!q.empty())
35     {
36         int t=q.front();
37         if(dist[t]*q.size()>sum)
38         {
39             q.pop_front();
40             q.push_back(t);
41             continue;
42         }
43         q.pop_front();
44         sum-=dist[t];
45         vis[t]=0;
46         for(int i=head[t];i;i=nxt[i])
47         {
48             int y=v[i];
49             if(dist[y]>dist[t]+w[i])
50             {
51                 dist[y]=dist[t]+w[i];
52                 if(!vis[y])
53                 {
54                     q.push_back(y);
55                     sum+=dist[y];
56                     vis[y]=1;
57                 }
58             }
59         }
60     }
61 }
62 void pr()
63 {
64     for(int i=1;i<=n;i++)
65     {
66         if(dist[i]!=inf)cout<<dist[i];
67         else cout<<"2147483647";
68         cout<<" ";
69     } 
70 }
71 int main()
72 {
73     read();
74     spfa(s);
75     pr();
76     return 0;
77 }
View Code

3、随机优化：

随机优化就是rand一下，为0插入队首，为1插入队尾，最不靠谱的优化。

用时: 1259ms / 内存: 8516KB

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<ctime>
 5 #include<cstring>
 6 #include<queue>
 7 #include<algorithm>
 8 #define inf 336860180
 9 using namespace std;
10 int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],sum; 
11 bool vis[500001];
12 void add(int a,int b,int c)
13 {
14     v[++cnt]=b;
15     w[cnt]=c;
16     nxt[cnt]=head[a];
17     head[a]=cnt;
18 }
19 void read()
20 {
21     cin>>n>>m>>s;
22     for(int i=1;i<=m;i++)
23     {
24         cin>>x>>y>>z;
25         add(x,y,z);
26     }
27 } 
28 void spfa(int s)
29 {
30     memset(dist,20,sizeof(dist));
31     deque<int>q;
32     q.push_back(s);
33     vis[s]=1;
34     dist[s]=0;
35     while(!q.empty())
36     {
37         int t=q.front();
38         q.pop_front();
39         vis[t]=0;
40         for(int i=head[t];i;i=nxt[i])
41         {
42             int y=v[i];
43             if(dist[y]>dist[t]+w[i])
44             {
45                 dist[y]=dist[t]+w[i];
46                 if(!vis[y])
47                 {
48                     if(rand()%2)q.push_front(y);
49                     else q.push_back(y);
50                     vis[y]=1;
51                 }
52             }
53         }
54     }
55 }
56 void pr()
57 {
58     for(int i=1;i<=n;i++)
59     {
60         if(dist[i]!=inf)cout<<dist[i];
61         else cout<<"2147483647";
62         cout<<" ";
63     } 
64 }
65 int main()
66 {
67     srand(time(NULL));
68     read();
69     spfa(s);
70     pr();
71     return 0;
72 }
View Code

优化后的时间排序：RAND>LLL>朴素>SLF

如果你喜欢我的文章就来个点赞收藏转发关注吧!!!

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/szmssf/p/11047202.html