SPFA算法的判负环问题(BFS与DFS实现)

时间:2021-02-11 20:08:42

经过笔者的多次实践(失败),在此温馨提示:用SPFA判负环时一定要特别小心!

首先SPFA有BFS和DFS两种实现方式,两者的判负环方式也是不同的。

      BFS是用一个num数组,num[x]表示从1到x的最短路径包含的边数,当执行松弛操作d[y]=d[x]+w时,同样更新num[y]=num[x]+1,若此时发现num[y]>=n,则图中有负环(显然,n个点n条不重的边,必定又环)。DFS则是换了一种思路:把d数组的初值置为0,这样就能保证走过的路径和一直为负,排除了大量无关路径。但是这样判断的是是否有经过起始点的负环,因此要判断整个图中是否有负环的话,得把n个点全跑一遍。看起来是简单,但有以下注意事项:

  1. 如果只是判负环,使用DFS比BFS一般要快得多。
  2. DFS判断负环时,dis数组初值应该都设为0。
  3. 不要指望DFS在判断负环的同时还能求最短路了。
  4. 用DFS判断负环,不能只把一个点作为源点跑一次,而要把1-n每个都作为源点跑一遍SPFA,才能保证结果的正确。
  5. 还有一种比较玄学的判负环方式,就是正常地跑BFS的SPFA,如果扩展了MAXN次还没出结果,就判定有负环(MAXN为根据题目规模自拟的常量),原理简单易懂:跑了这么久还没出结果,当然是有负环咯~~NB的是经实测正确率还相当高!当然相当高还是牺牲了算法的正确性的,因此不到万不得已之时不建议使用(玄学你懂的)。

BFS判负环(部分):

 bool SPFA(){
queue<int> q;
for(int i=;i<=n;++i) d[i]=INF;
memset(num,,sizeof num);
while(!q.empty()){
int h=q.front();q.pop();
vis[h]=false;
for(int p=G.tail[h];p;p=G.e[p].last){
int &v=G.e[p].v,&w=G.e[p].w;
if(d[v]>d[h]+w){
d[v]=d[h]+w;
num[v]=num[h]+;
if(num[v]>=n) return true;
if(!vis[v])
q.push(v),vis[v]=true;
}
}
}
return false;
}

BFS判负环的另一种方式是用num[x]记录x入队的次数,如过某个num[x]>=n则判定有负环。但这种方法一般不如上面介绍的快,例如在n个结点构成一个负环的图中(这也是一种常见的卡的图),上面的方法只需绕环一次即可判定负环,而这种方法则需绕环n次。

DFS判负环(部分):

 bool SPFA(int x){
vis[x]=true;
for(int p=G.tail[x];p;p=G.e[p].last){
int &v=G.e[p].v,&w=G.e[p].w; if(d[v]>d[x]+w){
d[v]=d[x]+w;
if(vis[v]){vis[x]=false;return true;}
if(SPFA(v)){vis[x]=false;return true;}
}
}
return vis[x]=false;
}
bool check(){
memset(d,,sizeof d);
for(int i=;i<=n;++i) if(SPFA(i)) return true;
return false;
}

  为什么第7和第8行要写个vis[x]=false?因为我们没有执行第11行,如果不写的话就无法把vis数组置0了,这样我们每次SPFA都得memset(vis,0,sizeof vis),很麻烦。

来一道很模板的例题:https://loj.ac/problem/10086

SPFA算法的判负环问题(BFS与DFS实现)

如此猖狂的出题人怎么可以忍???此题的特点是先判负环,若无负环求单源最短路。一开始我是小看这道题了,想用一次SPFA_DFS解决问题,结果有一个测试点负环没判到,还有一个点T了(说好的不必为超时担心呢=-=)。果然鱼和熊掌不可兼得,修改策略:先用SPFA_DFS判负环,如果没有再用正常的SPFA_BFS求最短路,就可以A了。

     要注意vis数组对于DFS和BFS的SPFA意义是不太一样的,判断负环与求最短路时对dis数组的初始化赋值也不一样。

     本蒟蒻建议:用DFS判负环,用BFS求最小路。

2018-08-18