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

플로이드 와샬 알고리즘이란?

다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점으로의 최단거리를 구하는 알고리즘이라면, 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

거쳐가는 정점을 기준으로 최단 거리를 구한다.

원리

동적 프로그래밍 기법의 원리를 사용한다.

각각 정점이 다른 정점으로 가는 비용을 이차원 배열에 담아준다.(행에서 열로 가는 비용)

이차원 배열을 반복(거쳐가는 정점을 기준으로)적으로 갱신하여 모든 최소 비용을 구한다.

예를 들면, 2->3 으로 바로가는 비용과, (2->1) + (1->3) 이런식으로 정점 1을 거쳐가는 경우를 비교해서 최소거리를 갱신하는 것이다.

구현

시간복잡도는 O(n^3)이다.(3중 for문 사용)

#include <stdio.h>

int number = 4; // 노드 갯수
int INF = 1000000000; // 무한대

// 자료 배열 초기화
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];
        }
    }

    // 플로이드 와샬
    // k: 거쳐가는 노드
    for(int k=0;k<number;k++) {
        // i: 출발 노드
        for(int i=0;i<number;i++) {
            // j: 도착 노드
            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("%d ",d[i][j]);
        }
        printf("\n");
    }    
}

int main(void) {
    floydWarshall();
    return 0; 
}

reference: https://www.youtube.com/watch?v=9574GHxCbKc&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=26