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

플로이드 와샬

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 사용하는 알고리즘이다. 플로이드 와샬은 가장 적은 비용을 하나씩 선택하는 다익스트라 알고리즘과 달리 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 또한, 플로이드 와샬 알고리즘은 기본적으로 다이나믹 프로그래밍 기술에 의거하는데, 그 이유는 

 

그럼 플로이드 와샬 알고리즘에 대해 알아보자. 플로이드 와샬 알고리즘은 표의 형태로 저장한 그래프에 거쳐갈 정점을 정해 바로 가는 비용과 정점을 거쳐서 가는 비용을 비교해 더 적은 비용으로 갱신하는 것을 반복하는 것이다.

이해를 돕기 위해 그림으로 살펴보면 다음과 같다.

 

이와 같은 그래프일 때

 

이를 구현한 코드는 아래와 같다.

 

#include <stdio.h>
 
int n = 4;
#define INF 100000000
 
// 자료 배열을 초기화
int a[4][4] = {
    {0,5,INF,8},
    {7,0,9,INF},
    {2,INF,0,4},
    {INF,INF,3,0} };
 
void folydWarshall() {
    //결과 그래프를 초기화
    int d[4][4];
 
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            d[i][j] = a[i][j];
        }
    }
 
    // k = 거쳐가는 노드
    for (int k = 0;k < n;k++) {
        // i = 출발 노드
        for (int i = 0;i < n;i++) {
            // j = 도착 노드
            for (int j = 0;j < n;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 < n;i++) {
        for (int j = 0;j < n;j++)
            printf("%d ", d[i][j]);
        printf("\n");
    }
}
 
int main() {
    folydWarshall();
    return 0;
}