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

相关文章