题目描述

spfa判断负环

JAVA 代码

/*
首先要将所有的点加入到队列中，
因为负环可能存在在所有的路径上，
然后使用一个cnt数组记录当前点到1号点的最短路径的长度，
如果cnt[u]>=n,说明这条路径上至少有n+1个点，
也就是存在负环，返回true

转载：https://www.acwing.com/activity/content/code/content/176557/
*/

//使用spfa判断负环的时间复杂度为O(n∗mn∗m)

import java.util.*;
import java.io.*;

class Main{
    static int N = 10010, n,m,idx;
    static int[] h = new int[N], e =new int[N], ne=new int[N];
    static int[] d = new int[N], cnt =new int[N], w= new int[N];
    static boolean[] st = new boolean[N];


    static void add(int a,int b,int c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean spfa(){

        //说明, 这里没有d[] 初始化.
        //因为这里是判断负环.为初始化int[] 全局变量全为0;
        //如果有负环,则会为负数,比0小. 所以不用初始化.

        //声明一个队列，用于存放更新过的节点
        Queue<Integer> q = new LinkedList<Integer>();

        //将所有点加入到队列中, 因为负环可能在任意点到任意点的位置.
        for(int i=1; i<=n; i++){
            q.offer(i);
            st[i] = true;
        }
        while(!q.isEmpty()){
            int t = q.poll();
            st[t] = false;

            for(int i = h[t]; i!=-1; i=ne[i]){
                int j = e[i];
                if(d[j] > d[t] + w[i]){
                    d[j] = d[t] + w[i];
                    //记录cnt 为能够连接的边的数量
                    cnt[j] = cnt[t]+1;
                    //如果这个边数量比点数还多.那么则是产生了负环
                    if(cnt[j]>=n) return true;

                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);    
        n = sc.nextInt();
        m = sc.nextInt();

        Arrays.fill(h, -1);

        while(m-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            add(a,b,c);
        }

        if(spfa())System.out.println("Yes");
        else System.out.println("No");
    }
}