单源最短路_spfa
2017-08-15 本文已影响0人
Gitfan
SPFA
适用范围：
给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路，即最短路径一定存在。
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。
判断有无负环：
如果某个点进入队列的次数超过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
题意:
图是连通的,判断负环
题解:
任选一个起点进行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];//入队次数
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;//有负环
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来判断负环会很慢,因为对于有负环的情况我们必须在某个点入队n次后才能判断出来，如果n很大,那会非常耗时,而用DFS可以改善,因为DFS不会重复将一个点入栈,而是将下一个点入栈
看一看判负环的方法:
- 1、在spfa同时记录当前节点是否在栈中
- 2、如果某节点可被当前节点松弛
- 该节点还在栈中，说明松弛路径出现环，退出
- 否则以该节点为当前点进行深搜spfa操作
但是,如果明确知道图中没有负环,只是求最短路径,还是要用BFS的spfa,DFS栈太深跑得比较慢!
这里先给出spfa_dfs求最短路的代码(其实已经可以判负环了)
畅通工程续
题意:
给出起点终点,求最短路
#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;//有负环
}
else return true;//有负环
}
}
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
题意:
图是连通的,判断负环
题解:
任选一个起点进行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;//有负环
}
else return true;//有负环
}
}
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");
}
}
其实,如果只是判断负环,而不要求求最短路径,dfs的spfa还有一个优化的地方!
首先,如果存在负环,那么肯定有某条边是负数的,如果我们一开始就从负数边进行spfa_dfs的话,那么肯定很快可以找到这个负环,而且一旦找到负环就退出,这样子会快很多!
那么一开始怎么找到负数边呢??
我们先看spfa_dfs中,现在进行第一次dfs拓展,要使得第一次选中负边,假设我们把dis数组初始化为0,进行拓展时,dis[u]=0,dis[v]=0,要使得dis[v]>dis[u]+edge[i].val,那么边必定是负的,然后就对负边进行扩展了。
也就是说，dis数组初始化为0。这样处理后，第一次拓展只会拓展到与起点相连边权为负的边。
当然，求判负环＋求最短路时不能这样初始化dis数组,因为有可能存在权重为负的路径且不存在负环,那么这样的最短路是合理的,所以还是老老实实把dis数组初始化为∞。
P3385 【模板】负环
题意:
给一个图,判断是否有负环。注意,图不一定是联通的,所以要通过多次不同起点单源最短判负环。(spfa_bfs会超时,spfa_dfs的dis数组不初始化为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;//有负环
}
else return true;//有负环
}
}
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;//有负环
}
else
{
flag=true;
return;//有负环
}
}
}
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");
}
}
