SPFA

问题

解决这样的问题

1. 起点确定的，可以有重边和自环的，各边权可能为负数的图的最短路问题

要用SPFA求最短路，一定要确保没有负环回路 这类问题用Bellman-ford也能做，但速度慢，Bellman-Ford专门解决有边数限制的最短路问题

1. 求一个图中是否有负权回路。

   要素

   与堆优化版Dijkstra很像，不同的是Dijkstra用优先队列，而SPFA用普通队列就可以

2. h[], idx, e[], ne[], w[] 用邻接表存储图

3. st[]记录每一轮需要更新的点，这一点与Dijkstra不同
4. dist[] 存储每个点到起点的最短距离

   思路

   用bfs对Bellman-Ford算法进行优化，不再是无脑对每条边更新一次，而是每次将被更新的边的临点加入队列，下一次只对队列中这些点的临点进行更新

时间复杂度：平均O(m)，最差与Bellman Ford 一致，为O(NM)
本质：DP

模板

求最短路

851. spfa求最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 impossible。
数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。
输入样例：

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

2

import java.util.*;
public class Main {
    static final int N = 100010, INF = 0x3f3f3f3f;
    static int[] e = new int[N], h = new int[N], ne = new int[N], w = new int[N];
    static int idx, n, m;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            add(a, b, c);
        }
        spfa(1, dist);
        if (dist[n] == INF)
            System.out.println("impossible");
        else System.out.println(dist[n]);
    }
    static void spfa(int start, int[] dist) {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        Arrays.fill(st, false);
        st[1] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            st[u] = false;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i], ww = w[i];
                if (dist[j] > dist[u] + ww) {
                    dist[j] = dist[u] + ww;
                    if (!st[j]) {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
    }
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

:::tips Bellman_ford算法里最后return “impossible”的判断条件写的是dist[n]>0x3f3f3f3f/2;而spfa算法写的是dist[n]==0x3f3f3f3f;其原因在于Bellman_ford算法会遍历所有的边，因此不管是不是和源点连通的边它都会得到更新；但是SPFA算法不一样，它相当于采用了BFS，因此遍历到的结点都是与源点连通的，因此如果你要求的n和源点不连通，它不会得到更新，还是保持的0x3f3f3f3f。 :::

求是否有环

852. spfa判断负环

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000
1≤m≤10000
图中涉及边长绝对值均不超过 10000
输入样例：

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：

Yes

思路：
类似求最短路，只是加一个数组记录每个点当前的最短路是从起点经过多少步达成的，如果超过n-1说明有负环回路

要注意一点，刚开始把所有点都加入到队列中，因为图不一定是连通图，从1不一定能够到所有其它节点。
dist不需要初始化，因为如果负权回路存在的话到该点的最短距离一定趋于负无穷。

import java.util.*;
public class Main {
    static final int N = 2010, M = 10010, INF = 0x3f3f3f3f;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int idx, n, m;
    static int[] dist = new int[N];
    static int[] cnt = new int[N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            add(a, b, c);
        }
        boolean res = spfa();
        if (res) System.out.println("Yes");
        else System.out.println("No");
    }
    static boolean spfa() {
        Arrays.fill(st, true);
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            st[u] = false;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i], ww = w[i];
                if (dist[j] > dist[u] + ww) {
                    dist[j] = dist[u] + ww;
                    cnt[j] = cnt[u] + 1;
                    if (cnt[j] >= n) return true;
                    if (!st[j]) {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
        return false;
    }
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}