플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

앞서 다익스트라 알고리즘 포스트에서, 그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다고 했다.

하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)

하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)

하나의 목적지로가는 모든 최단 경로를 구하는 문제(single destination shortest path problem)

마지막으로 모든 최단 경로를 구하는 문제(All pairs shortest path problem).

플로이드-워셜 알고리즘은 이 중에서 마지막, 모든 최단 경로를 구하는 방법이다. (다익스트라는 single source shortest path problem였다.)

또한 다익스트라 알고리즘은 음의 가중치를 가진 간선은 못쓴다는 제약이 있었다. 하지만 플로이드-워셜에선 사용이 가능하다.

모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다.

플로이드-워셜은 optimal substructure의 개념을 이용하여 최단 경로를 찾는다. optimal substructure란 특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념이다.

1. 플로이드-워셜 알고리즘 기본 로직

플로이드-워셜에선 2개의 테이블을 사용하는데. 하나는 모든 경로에 대한 비용을 저장하는 테이블, 나머지 하나는 각 정점까지 가기 직전의 정점을 저장한 테이블이다. 각각의 테이블을 D와 P라고 하겠다.

테이블 D와 P에는 처음엔 인접 리스트에 대한 내용만 들어가게 된다. 그 후 경로를 추가 할 때마다 두 테이블이 갱신된다.

위 그래프를 보자. 플로이드-워셜에선 처음엔 인접리스트의 정보만 들어간다고 했다. 따라서 맨 처음에 초기화되는 테이블 D,P는 다음과 같다.

거리를 저장한 테이블 D

	1	2	3	4	5
1	0	3	8	INF	-4
2	INF	0	INF	1	7
3	INF	4	0	INF	INF
4	2	INF	-5	0	INF
5	INF	INF	INF	6	0

직전 정점을 저장한 테이블 P

	1	2	3	4	5
1	NIL	1	1	NIL	1
2	NIL	NIL	NIL	2	2
3	NIL	3	NIL	NIL	NIL
4	4	NIL	4	NIL	NIL
5	NIL	NIL	NIL	5	NIL

여기서 INF는 무한대를 뜻하며, NIL은 직전 정점이 없다(즉 연결되어있지 않다)는 뜻이다. 위 정점은 아무런 정점을 중간 경로로 사용하지 않고, 오직 인접 리스트만 표현한 것이기 때문에, 그 외는 INF,NIL로 명시되었다.

이제 여기서 경로 1을 중간 경로로 하는 테이블을 구해보자. 얼핏 봐도 4->2가 중간경로 1을 추가하면 4->1->2로 접근 할 수 있고, 4->5도 4->1->5로 접근 할 수 있게 됨을 볼 수 있다.

중간 경로 1을 추가한 테이블 D

	1	2	3	4	5
1	0	3	8	INF	-4
2	INF	0	INF	1	7
3	INF	4	0	INF	INF
4	2	5	-5	0	-2
5	INF	INF	INF	6	0

중간 경로 1을 추가한 테이블 P

	1	2	3	4	5
1	NIL	1	1	NIL	1
2	NIL	NIL	NIL	2	2
3	NIL	3	NIL	NIL	NIL
4	4	1	4	NIL	1
5	NIL	NIL	NIL	5	NIL

이렇게 경로가 갱신되며, 갱신 될 시 테이블 P의 해당 컬럼 또한 1로 갱신된다. 직전 경로가 갱신되므로 테이블 P를 이용하면 최단 경로 또한 구할 수 있다. 

이를 모든 정점을 경로에 추가할 때 까지 반복한다.

따라서 다음과 같은 관계가 성립됨을 알 수 있다.

2. C++ 플로이드-워셜 알고리즘  코드

밑은 위 식과 개념으로 작성한 코드이다. 여기선 테이블을 두개로 안두고, pair로 그냥 하나의 테이블로 묶었다, 또한 테이블 P와 스택을 이용해서 경로 또한 구했다.

#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#define MAX 987654321
#define NIL -1
using namespace std;
int n, m, x;
//플로이드 와샬 테이블. pair 하나는 D, 하나는 Pi 
vector<vector<pair<int, int> > > fw;
stack<int> path;
int main() {
    scanf("%d %d %d", &n, &m, &x);
    //플로이드 와샬 테이블 초기화. 
    fw.resize(n + 1);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            fw[i].push_back(make_pair(MAX, NIL));
            if (i == j) fw[i][j].first = 0;
        }
    }
    for (int i = 0; i<m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        fw[u - 1][v - 1].first = w;
        fw[u - 1][v - 1].second = u - 1;
    }

    printf("///////////초기테이블///////////\n");
    printf("--거리\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].first == MAX ? "INF\t" : "%d\t", fw[i][j].first);
        }
        printf("\n");
    }
    printf("--직전 프로시져\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].second == NIL ? "NIL\t" : "%d\t", fw[i][j].second+1);
        }
        printf("\n");
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j<n; j++) {
            for (int k = 0; k<n; k++) {
                if (fw[k][j].first > fw[k][i].first + fw[i][j].first) {
                    fw[k][j].first = fw[k][i].first + fw[i][j].first;;
                    fw[k][j].second = fw[i][j].second;;
                }
            }
        }
    }

    printf("\n/////////완료 후 테이블/////////\n");
    printf("--거리\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].first == MAX ? "INF\t" : "%d\t", fw[i][j].first);
        }
        printf("\n");
    }
    printf("--직전 프로시져\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            printf(fw[i][j].second == NIL ? "NIL\t" : "%d\t", fw[i][j].second+1);
        }
        printf("\n");
    }
    printf("\n");
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if(fw[i][j].second == NIL) continue;
            printf("%d부터 %d까지 경로 : ",i+1,j+1);
            int pre = j;
            path.push(j+1);
            while (i != fw[i][pre].second) {
                pre = fw[i][pre].second;
                path.push(pre+1);
            }
            printf("%d",i+1);
            while(!path.empty()){
                printf("-%d",path.top()); path.pop();
            }
            printf("\n");
        }
    }

}

입출력 코드가 많아서 그렇지 플로이드-워셜 코드 자체는 되게 짧고 간결하다.

<실행 화면>