플로이드 와샬(Floyd Warshall)

장승현·2023년 3월 21일

알고리즘

목록 보기

9/11

개요

플로이드 와샬 알고리즘은 지난 글에서의 다익스트라 알고리즘과 같은 다이나믹 프로그래밍을 활용한 최단 경로 탐색 알고리즘 중 하나이다. 이번 글에서는 이 플로이드 와샬 알고리즘에 대해 다익스트라 알고리즘과 비교하며 알아보고자 한다.

플로이드 와샬

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이었다. 하지만, 플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다.
또한, 다익스트라 알고리즘은 가장 적은 비용을 하나씩 갱신했다면 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다.

수행 과정

경유 노드를 선정한다.
모든 노드에 대해 기존 비용과 경유 노드를 거쳐간 비용을 비교하여 최소 비용을 갱신한다.
1~2번 과정을 모든 비용을 갱신할 때까지 반복한다.

예시

위 그림에서 동그라미 안의 번호는 노드 번호를 의미하며 빨간색 숫자는 노드에서 노드로 가는 비용을 의미한다. 표로 정리하면 다음과 같다.

1행 1열은 1번 노드에서 1번 노드로 가는 비용을 의미하며 그 값은 '0'이다. 1행 2열의 경우는 1번 노드에서 2번 노드로 가는 비용을 의미하며 그 값은 '2'인 방식이다. 1행 5열의 경우 1번 노드에서 5번 노드로 가는 경로가 없어 비용은 'INF'가 된다.
여기서 수행 과정을 진행하면 다음과 같다.

1번 노드를 경유 노드로 하는 경우, 출발 노드와 도착 노드가 같은 경우(빨간색)를 제외하고 출발 노드와 도착 노드가 각각 경유 노드와 중복되는 경우(노란색)를 제외하면 다음과 같다.

2번 노드에서 3번 노드로 바로 가는 비용은 '3'이다. 1번 노드를 경유한다면, 2번 노드에서 1번 노드로 가는 경로가 없기에 갱신이 일어나지 않는다.
3번 노드에서 2번 노드로 바로 가는 비용은 '4'이다. 1번 노드를 경유한다면, 3번 노드에서 1번 노드로 가는 비용은 '2'이고, 1번 노드에서 2번 노드로 가는 비용은 '2'로 그 합인 '4'로 최소 비용을 갱신할 수 있다.
이와 같은 과정을 모든 흰색의 경우에 반복한 결과는 다음과 같다.

2번 노드를 경유 노드로 하는 경우, 갱신 가능한 경우는 다음과 같다.

위 과정을 모든 흰색의 경우에 적용하면 다음과 같다.

이렇게 모든 과정을 반복했을 때의 결과는 다음과 같다.

시간 복잡도

다익스트라 알고리즘은 하나의 정점에 대해서만 최단 경로를 구한 반면에, 플로이드 와샬 알고리즘은 모든 정점에서의 최단 경로를 구하기 때문에 N번을 더 곱한 만큼의 시간 복잡도를 가진다. 따라서, Big-O 표기법으로 O(N^3)이 된다.

코드 구현

플로이드 와샬을 코드로 구현하면 다음과 같다.

#include <iostream>

int INF = 1000000;
int array[5][5] = {
    {0, 2, 1, 2, INF},
    {INF, 0, 3, 5, 1},
    {2, 5, 0, 5, INF},
    {1, 4, 3, 0, 2},
    {1, 2, INF, 4, 0},
};

int main(){
    for (int i=0;i<5;i++){ //경유 노드
        for (int j=0;j<5;j++){ //출발 노드
            if(i!=j){
                for (int k=0;k<5;k++){ //도착 노드
                    if (j!=k && i!=k) {
                        if (array[j][i] + array[i][k] < array[j][k]){
                            array[j][k] = array[j][i] + array[i][k];
                        }
                    }
                }
            }
        }
    }

    for (int i=0;i<5;i++){
        for (int j=0;j<5;j++){
            std::cout<<array[i][j]<<' ';
        }
        std::cout<<std::endl;
    }

    return 0;
}
//0 2 1 2 3 
//2 0 3 4 1 
//2 4 0 4 5 
//1 3 2 0 2 
//1 2 2 3 0