SPFA(Shortest Path First Algorithm)

SPFA(Shortest Path First Algorithm) 알고리즘은 "음수 간선을 포함한 데이크스트라 알고리즘"으로 이해하면 편한 "벨만 포드 알고리즘"을 개선한 알고리즘 입니다.

BFS - 데이크스트라 - 벨만포드(SPFA)로 학습을 진행하시면 편합니다.

 

벨만 포드는 "모든 간선에 대해 업데이트를 진행"하지만, SPFA는 "바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행"합니다.

벨만포드를 학습하지 않고, SPFA를 학습하셔도 태그로 벨만포드가 들어간 문제를 대부분 해결하실 수 있습니다.

 

ex)

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

11657번: 타임머신

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

1에서 2로 가는데 걸리는 최소 시간은 1 -> 2으로, 4이 소요됩니다.

1에서 3으로 가는데 걸리는 최소 시간은 1 -> 2 -> 3으로, 4 + -1 = 3이 소요됩니다.

 

음수 간선일 경우 cycle이 발생하므로, 해당 사이클이 발생하는지 체크 후, 발생하게 된다면 탈출하는 방식으로 해결하면 됩니다.

 

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

public class Main {
	static int n, m;
	static ArrayList<int[]>[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new ArrayList[n + 1];
		for(int i = 0; i <= n; i++) {
			arr[i] = new ArrayList<>();
		}
		
		while(m --> 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			arr[a].add(new int[] {b, val});
		}
		
		System.out.print(spfa());
	}
	
	public static String spfa() {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n + 1];
		long[] dist = new long[n + 1];	//가는데 걸리는 시간
		int[] cycle = new int[n + 1];	// 사이클이 발생하는지 체크
		
		Arrays.fill(dist, Integer.MAX_VALUE);//방문하지 않은 노드들에 가는 시간 max로 설정
		
		queue.add(1);
		dist[1] = 0;
		cycle[1]++;
		visited[1] = true;
		
		while(!queue.isEmpty()) {
			int now = queue.poll();
			
			visited[now] = false;//다시 방문할 수 있으니 false로 설정
			
			for(int i = 0; i < arr[now].size(); i++) {
				int next = arr[now].get(i)[0];
				int cost = arr[now].get(i)[1];
				
				if(dist[next] > dist[now] + cost) {
					dist[next] = dist[now] + cost;
					
					if(!visited[next]) {
						cycle[next]++;
						
						if(cycle[next] >= n) {
							return "-1";
						}//사이클이 발생한다면 return
						queue.add(next);
						visited[next] = true;
					}
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 2; i <= n; i++) {
			sb.append(dist[i] != Integer.MAX_VALUE ? dist[i] : -1).append("\n");
		}//갈 수 없는 노드는 -1, 갈수 있는 노드는 dist[i]
		return sb.toString();
	}
}

 

추천 문제

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

1865번: 웜홀

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

1738번: 골목길