7-Spfa算法（队列优化的Bellman-Ford算法）

算法思想

1. 将第一个节点加入队列
2. 尝试缩短距离
   1. 使用队列中的节点尝试更新（第一个节点至）其他节点的距离
3. 将被更新的节点加入队列
   1. 若（第一个节点至）当前节点的距离被缩短，则将当前节点加入队列
4. 循环2-3步骤，直至队列为空

原理

根据松弛操作的公式我们可知，只有当 dist[u] 变小时，dist[v]才会变小 所以我们仅需将被更新的节点加入队列，然后再尝试用该节点更新其他节点， 依次往复，便可完成所有节点的距离更新

记忆口诀

1. 我更新过谁，再用谁来更新别人

算法模板

import java.util.*;
public class Main {
    static int N = 100010, INF = 0x3f3f3f3f;
    static int[] e = new int[N], ne = new int[N], 
        h = new int[N], w = new int[N];
    static int[] dist = new int[N];
    // st[i]存储编号为 i 的节点加入队列的情况    
    static boolean[] st = new boolean[N];
    static int n, m, idx;


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h, -1);
        Arrays.fill(dist, INF);
        
        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt(), weight = in.nextInt();
            if(from == to) continue;
            add(from, to, weight);
        }
        spfa();
        var res = dist[n] == INF ? "impossible" : dist[n] + "";
        System.out.println(res);
    }

    static void add(int u, int x, int weight)
    {
        w[idx] = weight;
        e[idx] = x;
        ne[idx] = h[u];
        h[u] = idx ++ ;
    }
    
    static void spfa()
    {
        // 初始化
        Arrays.fill(dist, MAX);
        dist[1] = 0;
    
        // q[]存储被更新过的节点的编号
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        // 标记编号为1的节点已加入队列
        st[1] = true;

        while(!q.isEmpty())
        {
            int t = q.poll();
            // 标志编号为1的节点已弹出队列
            // 被弹出的节点有可能会被其他节点更新，
            // 从而再次被加入到队列当中
            st[t] = false;
            
            for(int i = h[t]; i != -1 ; i = ne[i])
            {
                int j = e[i];
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if(!st[j])
                    {
                        st[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
    }
}

找出负权回路

import java.util.*;
public class Main {
    static int N = 10010, INF = 0x3f3f3f3f;
    static int[] e = new int[N], ne = new int[N], 
        h = new int[N], w = new int[N];
    // cnt[i] 存储任意点走到 i 号点经过的边的数量
    static int[] cnt = new int[N], dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m, idx;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h, -1);
        
        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt(), weight = in.nextInt();
            add(from, to, weight);
        }
        var res = spfa() ? "Yes" : "No";
        System.out.println(res);
    }
    
    static void add(int u, int x, int weight)
    {
        e[idx] = x;
        w[idx] = weight;
        ne[idx] = h[u];
        h[u] = idx ++ ;
    }
    
    static boolean spfa()
    {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        
        var q = new LinkedList<Integer>();
        // 初始化队列 q
        // 将所有节点放入队列，
        // 即使所有节点不处于同一个连通集，
        // 也可以找出存在的负权回路        
        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];
                int weight = w[i];
                
                if(dist[t] + weight < dist[j])
                {
                    dist[j] = dist[t] + weight;
                    cnt[j] = cnt[t] + 1;
                    
                    if(cnt[j] >= n) return true;
                    if(!st[j])
                    {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        
        return false;
    }
}