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

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

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

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

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001]; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));queue<int>q;q.push(s);vis[s]=1;dist[s]=0;while(!q.empty()){int t=q.front();q.pop();vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){q.push(y);vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {read();spfa(s);pr();return 0; }

　　

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

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<stack> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001]; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));stack<int>q;q.push(s);vis[s]=1;dist[s]=0;while(!q.empty()){int t=q.top();q.pop();vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){q.push(y);vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {read();spfa(s);pr();return 0; }

　　

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

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<stack> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],stk[500001],top; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));top=1;stk[top]=s;vis[s]=1;dist[s]=0;while(top>0){int t=stk[top];top--;vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){stk[++top]=y;vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {read();spfa(s);pr();return 0; }

　　

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

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<stack> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],stk[500001],top; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));priority_queue<int>q;q.push(s);vis[s]=1;dist[s]=0;while(!q.empty()){int t=q.top();q.pop();vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){q.push(y);vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {read();spfa(s);pr();return 0; }

　　

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

二、SPFA的优化

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

1、SLF优化：

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

用时: 1100ms / 内存: 8512KB

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],sum; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));deque<int>q;q.push_back(s);vis[s]=1;dist[s]=0;while(!q.empty()){int t=q.front();q.pop_front();vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){if(dist[y]<=dist[q.front()])q.push_front(y);else q.push_back(y);vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {read();spfa(s);pr();return 0; }

　　

2、LLL优化：

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

用时: 1114ms / 内存: 8500KB

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],sum; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));deque<int>q;q.push_back(s);vis[s]=1;dist[s]=0;while(!q.empty()){int t=q.front();if(dist[t]*q.size()>sum){q.pop_front();q.push_back(t);continue;}q.pop_front();sum-=dist[t];vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){q.push_back(y);sum+=dist[y];vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {read();spfa(s);pr();return 0; }

　　

3、随机优化：

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

用时: 1259ms / 内存: 8516KB

 

#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<cstring> #include<queue> #include<algorithm> #define inf 336860180 using namespace std; int n,m,s,x,y,z,v[500001],w[500001],head[500001],nxt[500001],cnt,maxx,dist[500001],sum; bool vis[500001]; void add(int a,int b,int c) {v[++cnt]=b;w[cnt]=c;nxt[cnt]=head[a];head[a]=cnt; } void read() {cin>>n>>m>>s;for(int i=1;i<=m;i++){cin>>x>>y>>z;add(x,y,z);} } void spfa(int s) {memset(dist,20,sizeof(dist));deque<int>q;q.push_back(s);vis[s]=1;dist[s]=0;while(!q.empty()){int t=q.front();q.pop_front();vis[t]=0;for(int i=head[t];i;i=nxt[i]){int y=v[i];if(dist[y]>dist[t]+w[i]){dist[y]=dist[t]+w[i];if(!vis[y]){if(rand()%2)q.push_front(y);else q.push_back(y);vis[y]=1;}}}} } void pr() {for(int i=1;i<=n;i++){if(dist[i]!=inf)cout<<dist[i];else cout<<"2147483647";cout<<" ";} } int main() {srand(time(NULL));read();spfa(s);pr();return 0; }

　　

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

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

转载于:https://www.cnblogs.com/szmssf/p/11047202.html

总结

以上是生活随笔为你收集整理的基于各种基础数据结构的SPFA和各种优化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。