spfa--大部分情况下最优秀的求最短路问题的算法

spfa是从bellman算法优化过来的

bellman算法是对每天边都进行松弛操作，但其中大部分松弛操作是没有意义的，

假如a->b权值w，只有a的前驱变化了，对a->b进行松弛才会有意义，

所以，如果对一个点松弛成功，则将他的其他边加入队列进行后续松弛，

spfa求最短路

#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=1e5+10; int n,m,dis[N],e[N],ne[N],w[N],idx,h[N]; bool st[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int spfa() { memset(dis,0x3f,sizeof(dis)); dis[1]=0; queue<int> q; q.push(1); st[1]=true; while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t]; i!=-1; i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; if(!st[j])q.push(j); st[j]=true; } } } if(dis[n]==0x3f3f3f3f)return -1; else return dis[n]; } int main() { cin>>n>>m; memset(h,-1,sizeof(h)); for(int i=0; i<m; i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } int t=spfa(); if(t==-1) cout<<"impossible"<<endl; else cout<<t<<endl; }

spfa算法还可以用来判断这个图中是否存在负环

开一个cnt数组记录这个顶点是有多少个顶点松弛过来的

如果存在负环，会一直松弛，无法找到最短路，cnt【】会大于等于n

#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N=1e5+10; int n,m,dis[N],e[N],ne[N],w[N],idx,h[N],cnt[N]; bool st[N]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { queue<int> q; for(int i=1; i<=n; i++) { q.push(i);//dis[]不需要初始化，因为判断负环跟求最短路没有关系 st[i]=true;//每个点都加入队列意思为每个点都是起点判断有无负环 //如果之加入1号点相当于求在1号点的路径上有无负环 } while(q.size()) { int t=q.front(); q.pop(); st[t]=false; for(int i=h[t]; i!=-1; i=ne[i]) { int j=e[i]; if(dis[j]>dis[t]+w[i]) { dis[j]=dis[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n)return true; if(!st[j]) { q.push(j); st[j]=true; } } } } return false; } int main() { cin>>n>>m; memset(h,-1,sizeof(h)); for(int i=0; i<m; i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } bool t=spfa(); if(t) cout<<"Yes"<<endl; else cout<<"No"<<endl; }