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?。。?/p>

因為每次松弛后，只有與n松馳后的點相關的邊才會變，所以利用先進先出的隊列，這就是SPFA的優(yōu)化原理，雖然快了一丟丟，但是還是比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的優(yōu)劣比較

Dijkstra:效率高，實用性強，但不能跑負邊權
SPFA:時間復雜度為O(玄學),但能跑負權

Step 2:負環(huán)

Step 2 - 1:碰到負環(huán)怎么辦？

定義：在圖中有一個環(huán)，權值和為負數(shù)。

影響：如果有負環(huán)，最短路會無限變小，會死循環(huán)。

如圖：

對于圖中的負環(huán)，每跑一趟，邊權和就會減去 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!!!

但是，這種方法僅適用于構成環(huán)的點數(shù)較少時。

1.從邊的角度出發(fā)：對于有n個點的圖，任意最短路中，最多包含n-1條邊，統(tǒng)計s~i的邊數(shù)即可。 #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;
}