SPFA算法

一、简介

SPFA算法是Bellman-Ford算法的队列优化。它可以求出单源最短路，也可检测到负环，实现起来也比较容易。但是现在很多题目会卡SPFA，所以要看情况使用。

二、中心思想

可以证明，只有上一次迭代中松弛过的点才有可能参与下一次迭代的松弛操作。朴素的Bellman-Ford算法中对于每一次迭代，都会尝试松弛所有边，这无疑造成了巨大浪费。所以我们通过队列，保存所有松弛过的边，可以极大提高效率。

三、算法特征

其实，
不记录节点是否已访问的最小堆的Dijkstra等于用优先队列优化的SPFA。
不记录节点是否已访问的最小堆且不采用优先队列的Dijkstra等于SPFA。

所以，推荐使用优先队列优化的SPFA判定负权图。不存在负权时，使用Dijkstra算法。

四、算法实现（使用优先队列）

仅仅需要将使用优先队列进行优化基于邻接表的Dijkstra算法删去记录节点已访问的部分即可。

如果需要判断负环，记录每个点加入队列的次数即可，只要次数大于等于点的个数，就说明存在负环。

    public static final int N = 510;  //点个数

    public static int[] h = new int[N];  //头节点的next指向，初始值为-1
    public static int index = 0;  //当前边
    public static int[] dist = new int[N];  //终点到起点的距离
    public static List<Edge> list = new ArrayList<>();
    public static int[] count = new int[N];  //点被加入队列的次数

    private static class Edge {
        public int to;  //边的终点
        public int value;  //边的权值
        public int next;  //边的next指向

        public Edge(int to, int value, int next) {
            this.to = to;
            this.value = value;
            this.next = next;
        }
    }

    private static class Point implements Comparable<Point> {
        public int index;  //点的序号

        public Point(int index) {
            this.index = index;
        }

        @Override
        public int compareTo(Point o) {  //根据点目前到起点的距离判断优先级
            return Integer.compare(dist[this.index], dist[o.index]);
        }
    }

    public static void add(int from, int to, int value) {  //头插法
        list.add(new Edge(to, value, h[from]));  //这条边指向原来from顶点指向的边
        h[from] = index++;  //更新from顶点，指向这条边
    }

    /**
     * @return start到end的最短路
     * @param start 起点
     * @param end 终点
     * @param n 点的个数
     */
    public static int spfa(int start, int end, int n) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;  //起点到起点的距离为0

        Queue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(start));  //起点加入优先队列
        count[start]++;
        while (!queue.isEmpty()) {
            int t = queue.poll().index;

            for (int j = h[t]; j != -1; j = list.get(j).next) {  //从头节点遍历与该节点连通的点
                Edge e = list.get(j);  //得到下一条边
                if (dist[e.to] > dist[t] + e.value) {
                    dist[e.to] = dist[t] + e.value;
                    queue.add(new Point(e.to));  //将更新过的目的顶点加入优先队列
                    count[e.to]++;
                    if (count[e.to] >= n) {  //如果有点加入队列的次数大于n-1，说明存在负环
                        return -2;
                    }
                }
            }
        }

        if (dist[end] == Integer.MAX_VALUE) {
            return -1;
        }
        else {
            return dist[end];
        }
    }