플로이드 와샬 알고리즘 (Floyd Warshall Algorithm)

플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 탐색하는 알고리즘이다.

 

플로이드 와샬 (Floyd Warshall) 알고리즘

다음과 같은 그래프가 존재할 때, 각각의 정점이 다른 정점으로 가는 거리(비용)을 2차원 배열로 나타내면 아래와 같다.

0	5	INF(무한)	8
7	0	9	INF(무한)
2	INF(무한)	0	4
INF(무한)	INF(무한)	3	0

위 표는 현재까지 계산된 최소 비용이며, 이러한 2차원 배열을 반복적으로 갱신하여 모든 최소 비용을 구하는 과정은 아래와 같다.

(1) 노드 1을 거쳐가는 경우 [ 2->3 ]

   노드 1을 거쳐가야 하기 때문에 1을 포함하지 않은 경우들만 계산해주면 된다.

0	5	INF(무한)	8
7	0	[ 2->3 ]	[ 2->4 ]
2	[ 3->2 ]	0	[ 3->4 ]
INF(무한)	[ 4->2 ]	[ 4->3 ]	0

   먼저 노드2에서 노드3으로( [2->3] ) 가는 경우를 노드2에서 노드1로 가고 노드1에서 노드3으로( [2->1->3] )

 

   가는 방법으로 보면 된다. [2->1]로 가는 비용은 7이고 [1->3]으로 가는 비용은 무한이 된다. 결과적으로 

 

   [2->1->3]의 비용 = 무한 < [2->3]의 비용 = 9 이기 때문에 갱신되지 않고 그대로 9로 남게 된다.

 

(2) 노드 1을 거쳐가는 경우 [ 2->4 ]

0	5	INF(무한)	8
7	0	9	[ 2->4 ]
2	[ 3->2 ]	0	[ 3->4 ]
INF(무한)	[ 4->2 ]	[ 4->3 ]	0

   노드2에서 노드4로( [2->4] ) 가는 경우를 노드2에서 노드1로 가고 노드1에서 노드4로( [2->1->4] )

 

   가는 방법으로 보면 된다. [2->1]로 가는 비용은 7이고 [1->4]로 가는 비용은 8이다. 결과적으로

 

   [2->1->4]의 비용 = 15 < [2->4]의 비용 = 무한 이기 때문에 기존의 무한 값을 15로 갱신한다.

 

(3) 노드 1을 거쳐가는 경우 [ 3->2 ]

0	5	INF(무한)	8
7	0	9	15
2	[ 3->2 ]	0	[ 3->4 ]
INF(무한)	[ 4->2 ]	[ 4->3 ]	0

   노드3에서 노드2로( [3->2] ) 가는 경우를 노드3에서 노드1로 가고 노드1에서 노드2로( [3->1->2] )

 

   가는 방법으로 보면 된다. [3->1]로 가는 비용은 2이고 [1->2]로 가는 비용은 5이다. 결과적으로

 

   [3->1->2]의 비용 = 7 < [3->2]의 비용 = 무한 이기 때문에 기존의 무한 값을 7로 갱신한다.

 

 

이와 같은 방식으로 노드 2를 거쳐가는 경우, 노드 3을 거쳐가는 경우, 노드 4를 거쳐가는 경우 또한 반복적으로 수행해준다.

 

[예제]

#include <stdio.h>

int number = 4;
int INF = 100000000;

//자료 배열 초기화
int a[4][4] = {
	{0, 5, INF, 8},
	{7, 0, 9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0},
} ;

void floydWarshall() {
	int d[number][number];
	for(int i=0; i<number; i++) {
		for(int j=0; j<number; j++) {
			d[i][j] = a[i][j];
		}
	}
	for(int k=0; k<number; k++) {
		for(int i=0; i<number; i++) {
			for(int j=0; j<number; j++) {
				if(d[i][k] + d[k][j] < d[i][j]) {
					d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
	}
	
	for(int i=0; i<number; i++) {
		for(int j=0; j<number; j++) {
			printf("%3d ", d[i][j]);
		}
		printf("\n");
	}
}

int main() {
	floydWarshall();
}

 

우선 각 비용을 배열로 초기화한다. floydWarshall() 함수에서 결과 그래프를 초기화해준 뒤 조건문을 통해

 

만약 d[i][k] + d[k][j] 즉, i 노드로 출발해서 k로 거쳐간뒤 k 노드에서 도착 노드인 j 노드로 가는 비용이

 

d[i][j] 즉, 즉시 가는 비용보다 작다면 기존의 비용 값을 최소 비용으로 갱신해준다.

---

출처

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘