SPFA
適用范圍：
給定的圖存在負權邊辽俗，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復雜度又過高篡诽，SPFA算法便派上用場了崖飘。 我們約定有向加權圖G不存在負權回路，即最短路徑一定存在杈女。
期望的時間復雜度O(ke)朱浴， 其中k為所有頂點進隊的平均次數(shù)，可以證明k一般小于等于2达椰。
判斷有無負環(huán)：
如果某個點進入隊列的次數(shù)超過N次則存在負環(huán)
procedure Shortest-Path-Faster-Algorithm(G, s)
1 for each vertex v ≠ s in V(G)
2 d(v) := ∞
3 d(s) := 0
4 offer s into Q
5 while Q is not empty
6 u := poll Q
7 for each edge (u, v) in E(G)
8 if d(u) + w(u, v) < d(v) then
9 d(v) := d(u) + w(u, v)
10 if v is not in Q then
11 offer v into Q
P3371 【模板】單源最短路徑
題意:
求出起點到每個點的最短路徑
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x7fffffff;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inque[MAXN];//判斷是否在隊列中
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
void spfa_bfs(int st)
{
memset(inque,0,sizeof(inque));
dis[st]=0;
queue<int> que;
que.push(st);
int u,v,i;
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inque[v])
{
que.push(v);
inque[v]=1;
}
}
}
}
}
int main()
{
int n,m,st,u,v,val;
scanf("%d%d%d",&n,&m,&st);
fill(dis+1,dis+1+n,INF);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,val);
}
spfa_bfs(st);
bool start=true;
for(int i=1;i<=n;i++)
{
if(!start) printf(" ");
printf("%d",dis[i]);
start=false;
}
printf("\n");
}
Wormholes
題意:
圖是連通的,判斷負環(huán)
題解:
任選一個起點進行spfa
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inque[MAXN];
int queNum[MAXN];//入隊次數(shù)
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_bfs(int st,int n)
{
memset(inque,0,sizeof(inque));
memset(dis,INF,sizeof(dis));
memset(queNum,0,sizeof(queNum));
dis[st]=0;
queue<int> que;
que.push(st);
queNum[st]++;
int u,v,i;
while(!que.empty())
{
u=que.front();que.pop();
inque[u]=0;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inque[v])
{
que.push(v);
queNum[v]++;
if(queNum[v]>n) return true;//有負環(huán)
inque[v]=1;
}
}
}
}
return false;
}
int main()
{
int n,m,k,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,val);
addEdge(v,u,val);
}
for(int i=0;i<k;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,-val);
}
if(spfa_bfs(1,n)) printf("YES\n");
else printf("NO\n");
}
}
其實,spfa可以寫成DFS的形式,只不過是把隊列換成了棧!同時,用bfs形式的spfa來判斷負環(huán)會很慢,因為對于有負環(huán)的情況我們必須在某個點入隊n次后才能判斷出來翰蠢，如果n很大,那會非常耗時,而用DFS可以改善,因為DFS不會重復將一個點入棧,而是將下一個點入棧
看一看判負環(huán)的方法:
- 1、在spfa同時記錄當前節(jié)點是否在棧中
- 2啰劲、如果某節(jié)點可被當前節(jié)點松弛
- 該節(jié)點還在棧中梁沧，說明松弛路徑出現(xiàn)環(huán)，退出
- 否則以該節(jié)點為當前點進行深搜spfa操作
但是,如果明確知道圖中沒有負環(huán),只是求最短路徑,還是要用BFS的spfa,DFS棧太深跑得比較慢!
這里先給出spfa_dfs求最短路的代碼(其實已經(jīng)可以判負環(huán)了)
暢通工程續(xù)
題意:
給出起點終點,求最短路
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x7fffffff;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],instack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
instack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!instack[v])
{
if(spfa_dfs(v)) return true;//有負環(huán)
}
else return true;//有負環(huán)
}
}
instack[u]=0;
return false;
}
int main()
{
int n,m,st,ed,u,v,val;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,val);
addEdge(v,u,val);
}
fill(dis,dis+n,INF);
memset(instack,0,sizeof(instack));
scanf("%d%d",&st,&ed);
dis[st]=0;
spfa_dfs(st);
if(dis[ed]==INF) printf("-1\n");
else printf("%d\n",dis[ed]);
}
}
Wormholes
題意:
圖是連通的,判斷負環(huán)
題解:
任選一個起點進行spfa
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=10010;
const int MAXE=500010;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
if(spfa_dfs(v)) return true;//有負環(huán)
}
else return true;//有負環(huán)
}
}
inStack[u]=0;
return false;
}
int main()
{
int n,m,k,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,val);
addEdge(v,u,val);
}
for(int i=0;i<k;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,-val);
}
memset(inStack,0,sizeof(inStack));
fill(dis+1,dis+1+n,INF);
dis[1]=0;
if(spfa_dfs(1)) printf("YES\n");
else printf("NO\n");
}
}
其實,如果只是判斷負環(huán),而不要求求最短路徑,dfs的spfa還有一個優(yōu)化的地方!
首先,如果存在負環(huán),那么肯定有某條邊是負數(shù)的,如果我們一開始就從負數(shù)邊進行spfa_dfs的話,那么肯定很快可以找到這個負環(huán),而且一旦找到負環(huán)就退出,這樣子會快很多!
那么一開始怎么找到負數(shù)邊呢??
我們先看spfa_dfs中,現(xiàn)在進行第一次dfs拓展,要使得第一次選中負邊,假設我們把dis數(shù)組初始化為0,進行拓展時,dis[u]=0,dis[v]=0,要使得dis[v]>dis[u]+edge[i].val,那么邊必定是負的,然后就對負邊進行擴展了蝇裤。
也就是說廷支，dis數(shù)組初始化為0。這樣處理后栓辜，第一次拓展只會拓展到與起點相連邊權為負的邊恋拍。
當然，求判負環(huán)＋求最短路時不能這樣初始化dis數(shù)組,因為有可能存在權重為負的路徑且不存在負環(huán),那么這樣的最短路是合理的,所以還是老老實實把dis數(shù)組初始化為∞藕甩。
P3385 【模板】負環(huán)
題意:
給一個圖,判斷是否有負環(huán)施敢。注意,圖不一定是聯(lián)通的,所以要通過多次不同起點單源最短判負環(huán)。(spfa_bfs會超時,spfa_dfs的dis數(shù)組不初始化為0也會超時)
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=200010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
if(spfa_dfs(v)) return true;//有負環(huán)
}
else return true;//有負環(huán)
}
}
inStack[u]=0;
return false;
}
int main()
{
int n,m,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,val);
if(val>=0) addEdge(v,u,val);
}
memset(inStack,0,sizeof(inStack));
memset(dis,0,sizeof(dis));
bool flag=false;
for(int i=1;i<=n;i++)
{
if(spfa_dfs(i))
{
flag=true;
break;
}
}
if(flag) printf("YE5\n");
else printf("N0\n");
}
}
另外,再給出一個用全局變量flag的dfs吧,其實和上面一樣的
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=200010;
const int MAXE=200010*2;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
};
Node edge[MAXE];
int cnt,head[MAXN];
int dis[MAXN],inStack[MAXN];//判斷是否在棧中
void addEdge(int u,int v,int val)
{
edge[cnt].to=v;edge[cnt].val=val;
edge[cnt].next=head[u];head[u]=cnt++;
}
bool flag;
void spfa_dfs(int u)
{
inStack[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].val)
{
dis[v]=dis[u]+edge[i].val;
if(!inStack[v])
{
spfa_dfs(v);
if(flag) return;//有負環(huán)
}
else
{
flag=true;
return;//有負環(huán)
}
}
}
inStack[u]=0;
}
int main()
{
int n,m,u,v,val,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
cnt=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
addEdge(u,v,val);
if(val>=0) addEdge(v,u,val);
}
memset(inStack,0,sizeof(inStack));
memset(dis,0,sizeof(dis));
flag=false;
for(int i=1;i<=n;i++)
{
spfa_dfs(i);
if(flag) break;
}
if(flag) printf("YE5\n");
else printf("N0\n");
}
}
