题目描述

计算含负权边图的最短路算法，时间复杂度m,最坏为nm,是一种优化后的bellman—ford算法

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

public class SPFA{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String temp[] = reader.readLine().split(" ");
        int n, m, idx = 0, N = 100010;
        n = Integer.parseInt(temp[0]);m = Integer.parseInt(temp[1]);
        int h[] = new int[N], e[] = new int[2*N];
        int ne[] = new int[2*N], dist[] = new int[N];
        int w[] = new int[2*N];
        boolean st[] = new boolean[N];

        Arrays.fill(h, -1);
        Arrays.fill(dist, 0x3f3f3f3f);
        while(m-- > 0){
            int a,b,c;
            temp = reader.readLine().split(" ");
            a = Integer.parseInt(temp[0]);
            b = Integer.parseInt(temp[1]);
            c = Integer.parseInt(temp[2]);
            //与bellman—ford不同，SPFA使用邻接表存储图，与堆优化版的Dijkstra类似
            e[idx] = b;
            w[idx] = c;
            ne[idx] = h[a];
            h[a] = idx++;
        }
        dist[1] = 0;
        //使用队列进行存储
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(1);
        st[1] = true;//这里的st[]存储的是当前点是否存在于队列中
        /**
         * 每次将队头元素取出，遍历当前点连接的所有边，如存在距离更近的点，判断该点是否是否在队列中
         * 若不存在，则将当前点加入到队列中
         *
         * 与bellman-ford不同，该方法在循环过程中只会更新有距离更新的点之后的其它点，而不是更新所有的点
         */
        while(!queue.isEmpty()){
            int t = queue.poll();
            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;
                        queue.addLast(j);
                    }
                }
            }
        }

        if (dist[n] != 0x3f3f3f3f) System.out.println(dist[n]);//与bellman-ford不同，最后的距离只要不等于最开始的极大值，则输出解
        else System.out.println("impossible");
    }
}