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

날짜:


플로이드-와샬 알고리즘 (Floyd-Warshall Algorithm) 이란?


이전에 얘기했던 다익스트라 알고리즘, 벨만-포드 알고리즘과 함께 최단 경로를 구하는 알고리즘이다. 앞의 이름만 따서 플로이드 알고리즘이라고도 한다. 벨만-포드 알고리즘처럼 사이클이 존재하지 않는다면 음의 가중치를 갖는 그래프도 처리할 수 있다. 아이디어는 모든 정점에 대하여 최단 경로를 모두 찾아서 업데이트하는 방식이다. 3중 for문으로 쉽게 구현할 수 있어 최단 경로를 구하는데에 있어서 종종 사용된다.

그렇다면 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘의 차이는 뭘까? 셋 다 최단 경로를 구하는 알고리즘이란 건 알겠지만, 명확한 차이를 비교해본 적은 없다. 

다익스트라 알고리즘: 음수 가중치가 없는 그래프에서 한 점에서 그 점과 연결 된 모든 점의 최단 거리를 구하는 것

벨만-포드 알고리즘: 음수 가중치와 관계 없이 특정 그래프에서의 한 점에서 다른 정점들과의 최단 거리를 구하는 것 

플로이드-와샬 알고리즘: 한 점만 탐색하는 것이 아닌, 모든 점에서 다른 모든 점까지의 최단 거리를 구하는 것


자신이 개발하는 프로그램에 따라, 또는 풀고 있는 문제에 따라 어떤 알고리즘을 사용할지는 모두 다를 수 있으며, 세 가지 방법 모두로 해결할 수도 있다. 따라서 어떤 알고리즘을 사용해야 가장 효율적일지 잘 생각해보고 선택하도록 하자.




플로이드-와샬 알고리즘 구현


사실상 아래의 코드가 플로이드-와샬 알고리즘 그 자체이며, 형태만 유지하면 어떤 플로이드-와샬 알고리즘 관련 문제라도 해결 가능하다. 다이나믹 프로그래밍이나 완전 탐색에서의 BFS, DFS 같은 경우 문제에 따라 형태가 천차만별로 달라지지만, 플로이드 문제는 형태만 어느 정도 유지만 해도 대부분 풀 수 있다. (물론 문제의 조건만 제대로 충족했다면 말이다.) 일단 뼈대는 아래와 같이 3중 for문을 이용하게 된다.

void floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dp[i][j] > dp[i][k] + dp[k][j]){
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }
}

i, j는 어떤 정점에서 모든 정점을 탐색하는 점을 의미하는 것은 플로이드의 정의를 잘 생각해보면 금방 알 수 있을 것이다. 그럼 k와 dp[i][j] > dp[i][k] + dp[k][j]가 갖는 의미는 뭘까? 

일단 이 의미를 이해하기 전에 플로이드 알고리즘의 초기화를 먼저 보고 가자. 2차원 배열을 이용하여 한 점에서 다른 점까지의 초기 경로를 설정하고, 인접 행렬이나 인접 리스트를 이용하여 한 점이 어떤 점들과 연결되어 있는지 저장해줘야 한다. 점들 간의 초기 경로를 초기화하는 코드부터 보자.

  for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) dp[i][j] = 0;
            else dp[i][j] = MAX;
        }
    }

자기 자신으로부터 자기 자신까지의 경로, 가령 1 -> 1, 2 -> 2, 3 -> 3 ... 은 0으로 초기화해준다. 현재 위치에서 현재 위치로 가는데 비용이 왜 들겠는가. 그냥 0이 된다. 그 외의 모든 경로는 아직 최소 비용이 얼마인지 모르므로 적당히 큰 수를 넣도록 한다. 

인접 행렬 및 인접 리스트를 구현하는 것은 조건에 따라 달라지는데, 단방향 그래프일 경우, 양방향 그래프일 경우, 어떤 점에서 다른 점까지의 경로가 1개가 아닌 여러개일 경우 등으로 구현을 달리 해줘야한다. 그 외에도 여러 조건이 존재할 수 있는데, 문제에 따라 인접 행렬 & 리스트를 잘 작성해줘야 한다.

    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;

        // 단방향 그래프일 경우이면서 한 점에서 다른 점까지의 경로가 오직 1개만 있을 경우
        dp[a][b] = c;

        // 양방향 그래프일 경우이면서 한 점에서 다른 점까지의 경로가 오직 1개만 있을 경우
        dp[a][b] = c;
        dp[b][a] = c;

        // 단방향 그래프일 경우이면서 한 점에서 다른 점까지의 경로가 여러개일 경우
        dp[a][b] = min(dp[a][b], c);

        // 양방향 그래프일 경우이면서 한 점에서 다른 점까지의 경로가 여러개일 경우
        dp[a][b] = min(dp[a][b], c);
        dp[b][a] = min(dp[b][a], c);
    }



이제 인접 행렬 & 인접 리스트도 작성했고, 최소 경로를 초기화하는 과정도 진행했으므로 다시 위로 올라가서 아까의 3중 for문이 의미하는 게 무엇인지 생각해보자. 일단 아래와 같은 그래프가 있을 때를 생각해보자. 
dp[1][3] 의 경우를 생각해보자. 
dp[1][3] > dp[1][k] + dp[k][3] (k = 1, 2, 3) 라는 식이 세워진다.

k = 1일 때를 보자.

dp[1][3] > dp[1][1] + dp[1][3] 일 때 dp[1][3]은 지금까지 탐색했던 1 -> 3의 경로의 최솟값을 의미하고 부등호 오른쪽인 dp[1][1] 은 1 -> 1 경로 중 최소 비용이 든 경로의 값에 1 -> 3 경로 중 최소 비용이 든 경로의 값을 합한 것이다. 즉 1 -> 3 경로의 최단 경로의 값과 1 -> 1 -> 3의 경로의 비용 중 더 작은 값을 저장한다.
dp[1][3] > dp[1][1] + dp[1][3]    --->    MAX > 0 + 4 (true)   --->    dp[1][3] = 4 

k = 2일 때를 보자.

위와 같은 방식이다.
dp[1][3] > dp[1][2] + dp[2][3]    --->    4 > 1 + 1 (true)   --->    dp[1][3] = 2

k = 3일 때를 보자.

dp[1][3] > dp[1][3] + dp[3][3]    --->    2 > 4 + 0 (false)    --->    dp[1][3] = 3



즉 dp[i][j]는 i -> j 까지의 경로 중에서의 최단 경로를 의미하는 것이고, 
dp[i][k] + dp[k][j]는 i -> k -> j 까지의 경로 중에서의 최단 경로를 의미하는 것이며, 
dp[i][j] > dp[i][k] + dp[k][j] 는 i -> j 와 i -> k -> j 중 어떤 경로가 더 짧은지를 비교하는 것이다.



결국 위의 3중 for문의 의미는 

"모든 정점 i에 대하여, 다른 모든 정점 j까지의 경로 중에서, i -> j 까지 가는 도중에 거치는 정점 k (거칠 수도 있고, 거치지 않을 수도 있다.) 를 포함해서 어떤 경로가 가장 짧은가"

를 구한다고 보면 되겠다.



백준 11404. 플로이드 문제와 코드를 보면서 어떻게 사용하는 것인지 감을 잡을 수 있으면 좋겠다.


문제


풀이
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

int MAX = 100000000;
int dp[101][101];
int n, m;

void floyd(){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dp[i][j] > dp[i][k] + dp[k][j]){
                    dp[i][j] = dp[i][k] + dp[k][j];
                }
            }
        }
    }
}


int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i == j) dp[i][j] = 0;
            else dp[i][j] = MAX;
        }
    }

    for(int i = 0; i < m; i++){
        int a, b, c; cin >> a >> b >> c;
        dp[a][b] = min(dp[a][b], c);
    }
    floyd();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dp[i][j] == MAX) cout << 0 << " ";
            else cout << dp[i][j] << " "; 
        }
        cout << '\n';
    }
    return 0;
}

댓글

댓글 쓰기