플루이드 와샬

다익스트라는 간선에 가중치가 있을 때 출발 정점에서 도착 정점까지의 최단 거리를 구하는 알고리즘이다. 플루이드 와샬도 최단 거리를 구한다는 점은 동일하다. 하지만 플루이드 와샬은 모든 정점에서 모든 정점까지의 최단 거리를 구한다는 점에서 차이가 있다. 또한 다익스트라는 가장 적은 비용의 간선을 선택하지만 플루이드 와샬은 거쳐가는 정점을 정해서 비용을 비교하고 갱신한다.

 

그림으로 알고리즘의 진행 과정을 살펴보자.

먼저 다음과 같이 그래프에 대해서 인접 행렬을 초기화한다.

이제 1을 거치지 않는 경로와 1을 거쳐가는 경로의 비용을 비교해서 인접 행렬을 갱신해준다.

다음으로 2를 거치지 않는 경로와 2를 거쳐가는 경로의 비용을 비교해서 갱신한다.

다음으로 3

다음으로 4

다음으로 5

최종 모습

이제 소스 코드로 구현해보자. 구현은 굉장히 간단하다. 거쳐가는 노드 개수 만큼 전체 갱신을 반복한다.

#include <iostream>
using namespace std;

#define INF (int)1e9

int arr[5][5] = {
    {0, 1, 1, INF, INF},
    {INF, 0, INF, INF, 1},
    {3, INF, 0, INF, 2},
    {INF, 3, INF, 0, 1},
    {INF, INF, INF, 1, 0}
};

int main() {
    for(int k = 0; k < 5; k++) {
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                if(arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }

    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            if(arr[i][j] == INF) cout << "- ";
            else cout << arr[i][j] << ' ';
        }cout << endl;
    }
}


출력 결과
0 1 1 3 2 
- 0 - 2 1
3 4 0 3 2
- 3 - 0 1
- 4 - 1 0

 

코드에서도 보이지만 플루이드 와샬의 시간 복잡도는 O(N ^ 3) 이다. 성능이 좋지는 않다.