알고리즘: 플로이드 와샬(Floyd Warshall) 알고리즘(Dynamic programming) (feat. c++)

 

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

 

 

가중치가 포함된 어떤 그래프가 있을 때

모든 지점에서 모든 지점까지의 최소거리를 구하는데 유용하다.

 

물론 Brute-force 알고리즘을 이용하면 구할 수 있지만, 이는 매우 비효율적이다.

 

그래서 이러한 문제들은 동적프로그래밍을 이용하여 효율적으로 해결한다.

 

 

 

플로이드를 이용하기 위한 그래프 인접행렬에 대한 표현은 다음과 같다. 

 

 

 

그리고 W를 통해서 D를 구한다. 

 

 

아울러 P를 두어 두 지점 사이를 거치는 지점을 매핑한다. 

 

 

 

 

<Floyd Algorithm>

void floyd(const int W[N][N], int D[N][N], int P[N][N]) {

	for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)
		D[i][j] = W[i][j];

	for (int k = 0; k < N; k++)
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)			
				if (D[i][j] > D[i][k] + D[k][j])
				{
					D[i][j] = (D[i][k] + D[k][j]);
					P[i][j] = k + 1;					
				}
}

 

 

 

다음과 같은 인접행렬 W가 있을 때 

 

 

플로이드 알고리즘을 이용하면 D와 P는 다음과 같다.

 

 

1번 노드에서 2번노드까지의 최소거리 = 1

1번 노드에서 3번노드까지의 최소거리 = 3 

1번 노드에서 4번노드까지의 최소거리 = 1 

1번 노드에서 5번노드까지의 최소거리 = 4

 

...

 

5번 노드에서 1번노드까지의 최소거리 = 3  

5번 노드에서 2번노드까지의 최소거리 = 4  

5번 노드에서 3번노드까지의 최소거리 = 6  

5번 노드에서 4번노드까지의 최소거리 = 4  

 

 

 

 

 

5번 노드에서 3번 노드까지의 최소거리로 갈때 

어떤 노드를 지나는지 알아보자

 

5번노드에서 3번노드까지 갈 때 마지막으로 거치는 노드 : 4

5번노드에서 4번노드까지 갈 때 마지막으로 거치는 노드 : 1

5번노드에서 1번노드까지 갈 때 마지막으로 거치는 노드 : 없음

 

 

∴ 5 -> 1 -> 4 -> 3 을 거쳐 최소거리를 갖는다.

 

출처 : Foundations of Algorithms, Using C++ Pseudocode