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

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

 

플로이드-워셜 알고리즘은 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘입니다. 데이크스트라 알고리즘이 하나의 정점(시작 정점)으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘이며 음의 경로가 존재하는 그래프에서도 사용할 수 있습니다. 또한 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법이 적용될 수 있습니다.

 

알고리즘 원리

플로이드-워셜 알고리즘은 정점 A에서 정점 C에 대한 최단경로를 구하기 위해 `정점 A에서 정점 C에 대한 경로`와 `정점 A에서 정점 B를 거쳐 정점 B에서 정점 C로 가는 경로`를 비교합니다. 

 

예를 들어 정점 1 -> 정점 3의 직접 경로가 15이고, 정점 1 -> 정점 2의 직접 경로가 12라고 해보겠습니다. 이때, 만약 정점 2 -> 정점 3의 직접 경로가 2라면 정점 1에서 정점 2를 거쳐 정점 3으로 가는 경로는 12 + 2 = 14이므로 정점 1 -> 정점 3의 경로보다 비용이 더 적은 경로가 됩니다. 그러므로 최단 경로는 15에서 14로 변경됩니다.

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	7	INF	4
INF	0	INF	3	6
INF	3	0	INF	INF
-1	INF	-4	0	INF
INF	INF	INF	5	0

예제를 통해 원리를 자세히 살펴보겠습니다. 그래프는 현재 플로이드-워셜 알고리즘으로 최단 경로를 갱신하기 이전 상태이며 위 표는 현재 상태의 그래프를 2차원 배열 형태로 나타낸 것입니다. 

 

이제 각각의 정점을 거쳐갈 때 마다 어떤 경로가 갱신되는지 알아보겠습니다.

 

(1) 정점 1을 거쳐가는 경로

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	7	INF	4
INF	0
INF		0
-1			0
INF				0

정점 1을 거쳐가는 경로를 다시 갱신하기 위한 경로를 위 표에서 빈칸으로 표시하겠습니다. 이제부터 빈칸에 해당하는 경로를 채우는데 만약 새로 갱신되는 값이 있으면 값을 새로 설정하고 그렇지 않으면 기존값이 다시 채워지게 됩니다.

 

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	7	INF	4
INF	0	INF	3	6
INF	3	0	INF	INF
-1	1	-4	0	3
INF	INF	INF	5	0

▶ 정점 2 -> 정점 3 = INF 였습니다. 하지만 [정점 2 -> 정점 1 = INF] + [정점 1 -> 정점 3 = 7] = INF + 7 이므로 갱신되지 않습니다.

▶ 정점 2 -> 정점 4 = 3 이었습니다. 하지만 [정점 2 -> 정점 1 = INF] + [정점 1 -> 정점 4 = INF] = INF + INF 이므로 갱신되지 않습니다.

▶ 정점 2 -> 정점 5 = 6 이었습니다. 하지만 [정점 2 -> 정점 1 = INF] + [정점 1 -> 정점 5 = 4] = INF + 4 이므로 갱신되지 않습니다.

▶ 정점 3 -> 정점 2 = 3 이었습니다. 하지만 [정점 3 -> 정점 1 = INF] + [정점 1 -> 정점 2 = 2] = INF + 2 이므로 갱신되지 않습니다.

▶ 정점 3 -> 정점 4 = INF 였습니다. 하지만 [정점 3 -> 정점 1 = INF] + [정점 1 -> 정점 4 = INF] = INF + INF 이므로 갱신되지 않습니다.

▶ 정점 3 -> 정점 5 = INF 였습니다. 하지만 [정점 3 -> 정점 1 = INF] + [정점 1 -> 정점 4 = 4] = INF + 4 이므로 갱신되지 않습니다.

▶ 정점 4 -> 정점 2 = INF 였습니다. 그런데 [정점 4 -> 정점 1 = -1] + [정점 1 -> 정점 2 = 2] = 1 이므로 최단경로가 1로 갱신됩니다.

▶ 정점 4 -> 정점 3 = -4 였습니다. 하지만 [정점 4 -> 정점 1 = -1] + [정점 1 -> 정점 3 = 7] = 6 이므로 갱신되지 않습니다.

▶ 정점 4 -> 정점 5 = INF 였습니다. 그런데 [정점 4 -> 정점 1 = -1] + [정점 1 -> 정점 5 = 4] = 3 이므로 최단 경로가 3으로 갱신됩니다.

▶ 정점 5 -> 정점 2 = INF 였습니다. 하지만 [정점 5 -> 정점 1 = INF] + [정점 1 -> 정점 2 = 2] = INF + 2 이므로 갱신되지 않습니다.

▶ 정점 5 -> 정점 3 = INF 였습니다. 하지만 [정점 5 -> 정점 1 = INF] + [정점 1 -> 정점 3 = 7] = INF + 7 이므로 갱신되지 않습니다.

▶ 정점 5 -> 정점 4 = 5 였습니다. 하지만 [정점 5 -> 정점 1 = INF] + [정점 1 -> 정점 4 = INF] = INF + INF 이므로 갱신되지 않습니다.

 

결론적으로 정점 1을 거쳐간다고 했을 때 새로 갱신된 정점 간의 최단 경로는 [정점 4 -> 정점 2] 와 [정점 4 -> 정점 5]입니다.

 

(2) 정점 2를 거쳐가는 경로

정점 1	정점 2	정점 3	정점 4	정점 5
0	2
INF	0	INF	3	6
	3	0
	1		0
	INF			0

정점 2를 거쳐가는 경로 역시 위에서와 같은 방식대로 풀이하면 아래와 같은 표로 만들어집니다.

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	7	5	4
INF	0	INF	3	6
INF	3	0	6	9
-1	1	-4	0	3
INF	INF	INF	5	0

 

(2) 정점 3을 거쳐가는 경로

정점 1	정점 2	정점 3	정점 4	정점 5
0		7
	0	INF
INF	3	0	6	9
		-4	0
		INF		0

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	7	5	4
INF	0	INF	3	6
INF	3	0	6	9
-1	-1	-4	0	3
INF	INF	INF	5	0

 

(4) 정점 4를 거쳐가는 경로

정점 1	정점 2	정점 3	정점 4	정점 5
0			5
	0		3
		0	6
-1	-1	-4	0	1
			5	0

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	1	5	4
2	0	-1	3	6
5	3	0	6	9
-1	-1	-4	0	3
4	4	1	5	0

 

(4) 정점 5를 거쳐가는 경로

정점 1	정점 2	정점 3	정점 4	정점 5
0				4
	0			4
		0		7
			0	1
4	4	1	5	0

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	1	5	4
2	0	-1	3	6
5	3	0	6	9
-1	-1	-4	0	3
4	4	1	5	0

 

정점 5까지 거치는 과정을 완료하면 결과적으로 다음과 같은 플로이드-워셜 알고리즘의 결과 그래프 표가 형성됩니다.

정점 1	정점 2	정점 3	정점 4	정점 5
0	2	1	5	4
2	0	-1	3	6
5	3	0	6	9
-1	-1	-4	0	3
4	4	1	5	0

 

알고리즘 구현

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

#include <iostream>

using namespace std;

int n = 5;
int INF = 100;

int arr[5][5] = {
	{0, 2, 7, INF, 4},
	{INF, 0, INF, 3, 6},
	{INF, 3, 0, INF, INF},
	{-1, INF, -4, 0, INF},
	{INF, INF, INF, 5, 0},
};

void floydWarshall() {
	// 결과 그래프
	int d[5][5];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			d[i][j] = arr[i][j];
		}
	}

	// p : 거쳐갈 정점
	for (int p = 0; p < n; p++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (d[i][p] + d[p][j] < d[i][j]) {
					d[i][j] = d[i][p] + d[p][j];
				}
			}
		}
	}

	// 결과 그래프 출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%3d ", d[i][j]);
		}
		cout << endl;
	}
	
}
int main() {
	floydWarshall();
}
/* 
  0   2   1   5   4
  2   0  -1   3   6
  5   3   0   6   9
 -1  -1  -4   0   3
  4   4   1   5   0
  */

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.