[알고리즘] Floyd-Warshall 알고리즘이란?

오늘은 그래프의 최단 경로를 찾는 알고리즘 중 마지막 Floyd-Warshall 알고리즘에 대해서 알아보겠습니다.

 

---

Floyd-Warshall 알고리즘

Floyd-Warshall 알고리즘은 기존 Dijkstra와 Bellman-Ford의 단점을 모두 보완한 알고리즘입니다. 총 n번 반복하는동안 i(i=0, 1, ..., n-1)번째 정점을 경유하여 가는 경우들을 갱신하는 방법을 이용합니다.

 

Floyd-Warshall은 DP(Dynamic Programming)에 속합니다. 결국 Floyd-Warshall 알고리즘을 이용하여 결과를 도출할 때, 각 정점 사이의 거리를 이용하여 결과를 도출하기 때문입니다.

 

예제를 통해 Floyd-Warshall 알고리즘의 과정을 살펴봅시다.

 

위와 같은 그래프와 우측에는 D라는 이중배열이 있습니다. 가장 처음 이중배열에는 지금 당장 접근 가능한 정점까지의 가중치를 표시하였습니다.

 

이제 우리는 k=0, 1, ..., 4(=n-1)까지 반복하며 이중배열 D를 업데이트 해줄 것입니다.

 

 

우선 k=0일 때, 어떤 값들이 갱신되는지 확인해봅시다.

 

k=0일 때, 0을 거쳐갈 수 있는 새로운 것들을 찾아봅시다. 확인해보니 3으로부터 0을 거쳐서 2를 갈 수 있고, 1을 갈 수 있겠네요.

 

3 -> 0 -> 1

3 -> 0 -> 2

 

이 값들을 갱신해주면 됩니다. 그 외에 다른 값들은 갱신되지 않습니다. weight가 이전 값보다 더 크게 형성되기 때문이죠.

 

이제 k=1을 확인해봅시다.

1을 거쳐갈 수 있는 값 중 새롭게 갱신된 값은

 

0 -> 1 -> 4

4 -> 1 -> 2

 

입니다. 가중치의 합만큼 배열 D의 값을 수정해줍니다.

 

k=2도 확인해보겠습니다.

7개의 값이 갱신됐네요.

 

0 -> 2 -> 3

0 -> 2 -> 4

1 -> 2 -> 0

1 -> 2 -> 3

1 -> 2 -> 4

4 -> 2 -> 0

4 -> 1 -> 2 -> 3

 

이제 k=3을 확인해봅시다.

3개의 값이 갱신됐습니다.

 

1 -> 2 -> 3 -> 0

2 -> 3 -> 0

4 -> 1 -> 2 -> 3 -> 0

 

마지막으로 k=4를 확인해봅시다.

 

3개의 값이 갱신됐습니다.

 

0 -> 2 -> 4 -> 1

2 -> 4 -> 1

3 -> 4 -> 1

 

이제 각 정점으로부터 모든 정점의 최단거리를 구했습니다.

 

 

Floyd-Warshall 알고리즘의 구현

Floyd-Warshall은 모든 정점 방문을 위한 for문 1번, 각 정점에 대해 모든 노드의 경로를 계산하기 위해 for문 두번.

 

총 for문이 세번 필요합니다. 아래에는 간단한 Floyd-Warshall 코드를 보여줍니다.

for(int i=0; i<n; i++){ // 초기화
	for(int j=0; j<n; j++) 
    	D[i][j] = adjMatrix[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];
        }
    }
}

 

 

Floyd-Warshall 알고리즘의 수행시간

코드에서도 알 수 있듯이 Floyd-Warshall은 총 3번의 반복을 요구하므로 O(n^3)입니다.

 

---

지금까지 Floyd-Warshall에 대해서 알아봤습니다. 감사합니다.