Algorithm 24일차

알고리즘에서 최단 경로를 찾는 데 플로이드 워샬을 활용할 수 있다.

플로이드 워샬은 다익스트라와 달리 음의 가중치에서도 최단 경로를 찾을 수 있다.
따라서 음의 가중치에서 최단 경로를 찾을 때 주로 사용한다.

플로이드 워샬의 주요 아이디어는 아래와 같다.

1~n 까지의 모든 정점을 경유 가능한 정점들로 고려하며 모든 쌍의 최단 경로를 계산한다.

이는 1~n 까지의 모든 정점들을 반드시 경유하는 경로를 의미하지 않음을 주의하자.

플로이드 워샬의 부분 문제는 아래와 같이 정의된다.

Dijk = 정점 {1, 2, ..., k} 중 경유 가능한 정점들로 고려하여, i부터 j까지의 최단 경로

플로이드 워샬의 도출 과정은 아래와 같다.

1. k = 1일 때

i != j != k인 상황에서 1을 첫번째 경유지로 고려해보자.
그럼 i에서 j까지의 경로는 1을 거쳐서 가는 경로, 1을 거치지 않는 경로가 있다.
이 중 거리가 짧은 경로가 최단 경로로 정의된다.

아래 그림은 위 상황을 잘 보여준다.

※ Dij0은 아무 것도 경유하지 않은 경로를 의미한다.

2. k = 2일 때

이번엔 2를 두번째 경유지로 고려해보자.
이 때 1을 경유지로 할지 말지를 고려한 결과가 사용된다.
그럼 i에서 j까지의 경로는 2를 거쳐서 가는 경로, 2를 거지치 않는 경로가 있다.
이 중 거리가 짧은 경로가 최단 경로로 정의된다.

아래 그림은 위 상황을 잘 보여준다.

※ Dij1은 첫 번째 경유지를 고려한 최단 경로를 의미한다.

3. k = n일 때

이번엔 n을 n번째 경유지로 고려해보자.
이 때 n-1을 경유지로 할지 말지를 고려한 결과가 사용된다.
그럼 i에서 j까지의 경로는 n을 거쳐서 가는 경로, n을 거지치 않는 경로가 있다.
이 중 거리가 짧은 경로가 최단 경로로 정의된다.

아래 그림은 위 상황을 잘 보여준다.

이를 일반식으로 정리하면 아래와 같다.

따라서 플로이드 워샬의 구현은 아래와 같다.

이 때 D는 정점 간 거리로 초기화가 필요하다. 플로이드 워샬의 시간 복잡도는 O(N^3)이다.

플로이드 워샬을 실제로 구현하면 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Floyd {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int k = 0; k < N; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
				}
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(arr[i][j] + " ");
			}
			
			System.out.println();
		}
	}
}

입력값은 아래와 같다.

4
0 10 1 5
10 0 2 4
1 2 0 3
5 4 3 0

출력 결과는 아래와 같다.

0 3 1 4
3 0 2 4
1 2 0 3
4 4 3 0