卡码网：94.城市间货物运输II（存在负权回路）

输出描述：

如果没有发现负权回路，则输出一个整数，表示从城市1到城市n的最低运输成本（包括政府补贴）。

如果发现了负权回路的存在，则输出“circle”。如果从城市1无法到达到城市n，则输出“unconnected”。

本题要判断 有负权值的有向图 中是否存在 负权回路。（负权回路是指图中出现环且环上的边总权值为负数）

如果在这里的图中求最短路的话，就会在这个环里无限循环，因为每次循环都会得到更小权值总和，无法求的最短路径。

所以对于 在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。

在前两篇文章中介绍的Bellman_ford朴素版算法或者Bellman_ford堆优化版算法(SPFA)，核心算法就是一句话：对 所有边 进行n-1 次松弛。

在没有负权回路的有向图中，松弛n次，或者>>n次，minDist结果不会有变化。

但是对于有负权回路的有向图中，松弛n次及以上，结果就会发生变化。当松弛第n次时，minDist还会更新，就导致可以无限最短路径 。

问：上述都是理论分析，那么落实到代码上，如何体现负权回路呢？
答：设置标志字段boolean flag = false；
当进行第n次松弛时，去判断，是否还可以更新minDist数组（不要真的更新），如果还能走更新minDist数组的逻辑，那么就设置flag = true；
最后输出结果的时候进行单独判断

完整代码如下：

import java.util.*;

//Bellman_ford朴素版 判断是否有负权回路
public class Main{
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        //建立边的集合即可
        List<Edge> edges = new ArrayList<>(m);
        //初始化
        for(int i = 0; i < m; i++){
            int s = scanner.nextInt();
            int t = scanner.nextInt();
            int v = scanner.nextInt();
            edges.add(new Edge(s, t, v));
        }
        //minDist数组创建以及初始化
        int[] minDist = new int[n + 1];
        for(int i = 0; i < minDist.length; i++){
            minDist[i] = Integer.MAX_VALUE;
        }
        minDist[1] = 0;
        //用来标记松弛超过n-1次后 是否还会更新minDist数组
        boolean flag = false;
        //开始对所有边 松弛 n 次
        for(int i = 1; i <= n; i++){
            for(Edge edge : edges){
                if(i <= n - 1){
                    if(minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.to]){
                        minDist[edge.to] = minDist[edge.from] + edge.val;
                    }
                }else{
                    if(minDist[edge.from] != Integer.MAX_VALUE && minDist[edge.from] + edge.val < minDist[edge.to]){
                        flag = true;
                    }
                }
            }
        }
        //先判断是否有负权回路
        if(flag == true){
            System.out.print("circle");
        }else if(minDist[n] == Integer.MAX_VALUE){
            //再判断是否可以到达
            System.out.print("unconnected");
        }else{
            System.out.print(minDist[n]);
        }
    } 
}

class Edge{
    public int from;
    public int to;
    public int val;
    public Edge(int from, int to, int val){
        this.from = from;
        this.to = to;
        this.val = val;
    }   
}

上述完整代码使用的是Bellman_ford朴素版，为解决含有 负权回路 的有向图，使用SPFA算法也可以实现。

再来回过头看看Bellman_ford朴素版解法：对所有边松弛 n-1 次后，再松弛一次，如果出现minDist发生变化就判断有负权回路。

如果使用 SPFA 那么节点都是进队列的，那么节点进入队列几次后 足够判断该图是否有负权回路呢？在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。那么如果节点加入队列的次数 超过了 n-1次 ，那么该图就一定有负权回路。