SPFA学习

长沙7喜 2021-07-06

展开全文

作者：胡东麒
ID：国服墨子
学校：长沙市砂子塘小学六年级
博客地址：https://www./blog/359614/

Step 1:基本的SPFA最短路

Step 1 - 1:什么是SPFA？

前身：bellman-ford

同Dijkstra,是一种单源最短路径算法，不同的是以边为研究对象，时间复杂度为O(n*m),但是它能跑负边权，每一轮将每一条边跑一边，能松弛就松弛，所以最多n-1轮，每轮m次，然后。。。就T了：

for(int i=1;i<n;i++)
for(int j=head[i];j;j=e[j].nxt)
if(dis[i]+e[j].w<dis[e[j].to])
dis[e[j].to]=dis[i]+e[j].w;

但是，太太太太慢了，一言不合就TLE，QAQ

在完全图的情况下，bellman-ford甚至速度跟Floyd速度差不多。。。

那么。。。

隆重登场：SPFA！！！

因为每次松弛后，只有与n松驰后的点相关的边才会变，所以利用先进先出的队列，这就是SPFA的优化原理，虽然快了一丢丢，但是还是比Dijkstra慢，但是人家能跑负边权嘛对吧hhh

长得贼像Dijkstra的，比bellman-ford长N倍的代码隆重登场！！！

#include<bits/stdc++.h>
#define N 10000005
using namespace std;
int n,m,s,tot,head[N];
struct edge{
int to,w,nxt;
}e[N];
void add(int u,int v,int w){
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
bool vis[N];
int dis[N];
void SPFA(int s){
queue<int>q;
for(int i=1;i<=n;i++){
  dis[i]=1e9;
}
dis[s]=0;
q.push(s);
vis[s]=1;
int cur;
while(!q.empty()){
  cur=q.front();
  q.pop();
  vis[cur]=0;
  for(int i=head[cur];i!=0;i=e[i].nxt){
   int v=e[i].to;
   if(dis[v]>dis[cur]+e[i].w){
    dis[v]=dis[cur]+e[i].w;
    if(!vis[v]){
     vis[v]=1;
     q.push(v);
    }
   }
  }
}
return;
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
  int u,v,w;
  cin>>u>>v>>w;
  add(u,v,w);
}
SPFA(s);
for(int i=1;i<=n;i++){
  cout<<dis[i]<<' ';
}
return 0;
}

Step 1 - 2 :Dijkstra与SPFA的优劣比较

Dijkstra:效率高，实用性强，但不能跑负边权
SPFA:时间复杂度为O(玄学),但能跑负权

Step 2:负环

Step 2 - 1:碰到负环怎么办？

定义：在图中有一个环，权值和为负数。

影响：如果有负环，最短路会无限变小，会死循环。

如图：

对于图中的负环，每跑一趟，边权和就会减去 9 ，所以不会停止。

判断：

1.从点判断，每个点最多被松弛n-1次，直接上cnt[XXX]即可； #include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,s,tot,head[N],cnt[N];
struct edge{
int to,w,nxt;
}e[N];
void add(int u,int v,int w){
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
bool vis[N];
int dis[N];
bool SPFA(int s){
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
queue<int>q;
for(int i=1;i<=n;i++){
  dis[i]=1e9;
}
dis[s]=0;
q.push(s);
vis[s]=1;
int cur;
while(!q.empty()){
  cur=q.front();
  q.pop();
  vis[cur]=0;
  for(int i=head[cur];i!=0;i=e[i].nxt){
   int v=e[i].to;
   if(dis[v]>dis[cur]+e[i].w){
    dis[v]=dis[cur]+e[i].w;
    if(!vis[v]){
     vis[v]=1;
     cnt[v]++;
     if(cnt[v]==n)return false;
     q.push(v);
    }
   }
  }
}
return 1;
}
int t;
int main(){
cin>>t;
while(t--){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
   int u,v,w;
   cin>>u>>v>>w;
   if(w>=0){
    add(u,v,w);add(v,u,w);
   }else add(u,v,w);
  }
  if(SPFA(1)==1){cout<<'NO'<<'\n';}else{cout<<'Yes';cout<<'\n';}
}
return 0;
}

然后。。。

AC!!!

但是，这种方法仅适用于构成环的点数较少时。

1.从边的角度出发：对于有n个点的图，任意最短路中，最多包含n-1条边，统计s~i的边数即可。 #include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m,s,tot,head[N],cnt[N];
struct edge{
int to,w,nxt;
}e[N];
void add(int u,int v,int w){
tot++;
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
return;
}
bool vis[N];
int dis[N];
bool SPFA(int s){
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
memset(dis,0x3f,sizeof(dis));
queue<int>q;
dis[s]=0;
q.push(s);
vis[s]=1;
int cur;
while(!q.empty()){
  cur=q.front();
  q.pop();
  vis[cur]=0;
  for(int i=head[cur];i!=0;i=e[i].nxt){
   int v=e[i].to;
   if(dis[v]>dis[cur]+e[i].w){
    dis[v]=dis[cur]+e[i].w;
    cnt[v]=cnt[cur]+1;
    if(cnt[v]==n)return false;
    if(!vis[v]){
     vis[v]=1;
     q.push(v);
    }
   }
  }
}
return 1;
}
int t;
int main(){
cin>>t;
while(t--){
  tot=0;
  memset(head,0,sizeof(head));
  cin>>n>>m;
  for(int i=1;i<=m;i++){
   int u,v,w;
   cin>>u>>v>>w;
   if(w>=0){
    add(u,v,w);add(v,u,w);
   }else add(u,v,w);
  }
  if(SPFA(1)==1){cout<<'NO'<<'\n';}else{ cout<<'YES';cout<<'\n';}
}
return 0;
}