[알고리즘] 최단거리 알고리즘 SPFA Java 참고코드

SPFA(Shortest Path Faster Algorithm) 은 벨만포드 알고리즘을 개선한 알고리즘이다. v - 1번 반복하는 동안 매 반복마다 모든 간선에 대해서 간선 경감을 진행하는 대신, 간선 경감이 일어나는 정점에 대해서만 그 정점에 연결된 간선들에 대해서 다음 간선 경감을 진행하는 방식이다. 최악의 경우 O(V^3) 의 시간복잡도를 갖지만, 평균적으로 O(E) 의 시간복잡도를 갖는다.

https://www.acmicpc.net/problem/11657

package 최단경로.spfa.타임머신;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        
        long[] dist = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            dist[i] = Long.MAX_VALUE;
        }
        ArrayList<int[]>[] arr = (ArrayList<int[]>[]) new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<int[]>();
        }
        
        for (int i = 0; i < m; i++) {
            String[] nums = br.readLine().split(" ");
            int a = Integer.parseInt(nums[0]);
            int b = Integer.parseInt(nums[1]);
            int c = Integer.parseInt(nums[2]);
            
            arr[a].add(new int[] {b, c});
        }
        
        boolean[] check = new boolean[n + 1];
        int[] cnt = new int[n + 1];
        Queue<Integer> q = new LinkedList<>();
        check[1] = true;
        dist[1] = 0;
        cnt[1]++;
        q.offer(1);
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            check[cur] = false;
            
            for (int i = 0; i < arr[cur].size(); i++) {
                int next = arr[cur].get(i)[0];
                int cost = arr[cur].get(i)[1];
                
                if (dist[next] > dist[cur] + cost) {
                    dist[next] = dist[cur] + cost;
                    
                    if (check[next] == false) {
                        check[next] = true;
                        q.offer(next);
                        
                        cnt[next]++;
                        if (cnt[next] >= n) {
                            System.out.println(-1);
                            return;
                        }
                    }
                }
            }
        }
        
        for (int i = 2; i <= n; i++) {
            if (dist[i] == Long.MAX_VALUE) System.out.println(-1);
            else System.out.println(dist[i]);
        }
    }
}