[Algorithm] Floyd-Warshall Algorithm (플로이드-워셜 알고리즘)

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

출처 : 위키백과

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

모든 정점들 사이의 최단거리를 구하는 알고리즘이므로, 시간이 많이 소요된다는 단점이 있다.

예)

초기 배열은 자기 자신은 0, 나머지는 무한대로 초기화한다.

각 간선의 정보를 배열에 설정한다.

경유지를 탐색하여, 더 짧은 경로가 존재하면 업데이트한다.

(0 → 3 의 경우 거리가 4이나, 0 → 1 → 3 으로 1을 거쳐가는 경우 거리가 1 + 2 = 3 으로 더 짧다.)

소스코드 (입력하는 과정 생략)

import java.io.*;

public class Main {
	public static final int INF = 10000;
	public static void main(String[] args) {
		int[][] d = new int[][]{{0,   1,   INF, 4},
								{INF, 0,   3,   2},
								{1,   INF, 0,   5},
								{INF, INF, INF, 0}};

		// 경유지
		for (int k = 0; k < 4; k++) {
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					if (d[i][j] > d[i][k] + d[k][j]) {
						d[i][j] = d[i][k] + d[k][j];
					}
				}
			}
		}
		
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (d[i][j] == INF)
					System.out.printf("%4s", "INF");
				else
					System.out.printf("%4d", d[i][j]);
			}
			System.out.println();
		}
	}
}

순서를 몇가지 나열해보면

① k = 0일 때,

i = 0

    j = 0 : d[0][0] > d[0][0] + d[0][0]

    j = 1  : d[0][1]  > d[0][0] + d[0][1]

    j = 2 : d[0][2] > d[0][0] + d[0][2]

    j = 3 : d[0][3] > d[0][0] + d[0][3]

i = 1

    j = 0 : d[1][0] > d[1][0] + d[0][0]

    j = 1  : d[1][1]  > d[1][0] + d[0][1]

    j = 2 : d[1][2] > d[1][0] + d[0][2]       --->   [1 → 2]로 가는 거리와, [1 → 0 → 2] 0을 거쳐가는 거리 비교

    j = 3 : d[1][3] > d[1][0] + d[0][3]

...

② k = 1일 때,

i = 0

    j = 0 : d[0][0] > d[0][1] + d[1][0]

    j = 1  : d[0][1]  > d[0][1] + d[1][1]

    j = 2 : d[0][2] > d[0][1] + d[1][2]

    j = 3 : d[0][3] > d[0][1] + d[1][3]

...

이와 같이, 모든 노드 사이의 최단경로를 구한다.