개발/알고리즘

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

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm)은 가중치가 있는 그래프에서 최단 거리를 구하는 알고리즘 중 하나다.

 

다익스트라나 벨만 포드 알고리즘은 한 정점으로부터 다른 정점까지의 최단 거리를 구하지만, 플로이드 와샬 알고리즘은 모든 정점 쌍 $(i, j)$에 대해 최단 거리를 구해준다. 또한 벨만 포드 알고리즘처럼 음수 간선이 있는 그래프에서도 정상적으로 작동한다.

동작 원리

플로이드 와샬 알고리즘의 동작 원리는 매우 간단하다. 정점 $i$와 $j$의 최단 거리를 계산할 때, 모든 정점 $k$에 대해 $i\rightarrow k \rightarrow j$가 $i \rightarrow j$보다 짧다면 $k$를 경유하는 것으로 최단 거리를 바꾸어 주면 된다.

 

$i$와 $j$가 처음에 이어져 있는 경우라면 상관이 없지만, 이어져 있지 않다면 어떻게 해야 할까? $\infty$(실제로는 아주 큰 값)으로 최단 거리 배열을 초기화하여 실제로 $i \rightarrow j$ 경로가 선택되지 않도록 하면 된다. 이렇게 하면 최단 거리 계산이 끝났을 때 도달할 수 없는 정점 간의 거리는 $\infty$로 저장되어 있다.

 

시간 복잡도는 모든 $(i,j)$ 쌍에 $k$를 시도해봐야 하므로 $O(V^3)$이다. 다익스트라를 모든 정점에서 수행하는 $O(VE\log V)$나 벨만 포드 알고리즘을 모든 정점에서 수행하는 $O(V^2 E)$에 비해 현실적으로 더 빠르다.

구현

플로이드의 구현 역시 동작 원리만큼이나 간단하다.

 

  1. 그래프의 인접 행렬을 만들고 전부 $\infty$로 초기화한다. 그리고 adj[i][i]꼴의 거리는 $0$으로 바꾸어 준다.
  2. 그 후 인접 행렬에 입력을 받는다. adj[i][j] = "$i$번째 정점에서 $j$번째 정점으로 가는 간선의 가중치"다.
  3. 3중 for문을 돌리면서 모든 쌍 $(i, j)$에 대해 최단 거리를 갱신한다.
  4. 이제 adj[i][j]에는 "$i$번째 정점에서 $j$번째 정점으로 가는 최단 거리"가 담겨 있다.
int adj[MAX][MAX]; // 인접 행렬
int n; // 정점 수

const int INF = 0x3f3f3f3f; // 무한대 값

void floyd() {
    memset(adj, INF, sizeof(adj));
    for (int i = 0; i < MAX; i++) adj[i][i] = 0;

    input(); // 그래프 입력

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (adj[i][k] + adj[k][j] < adj[i][j]) { // 만약 k를 경유하는 거리가 더 짧으면
                    adj[i][j] = adj[i][k] + adj[k][j]; // k를 경유하는 거리로 갱신
                }
            }
        }
    }
}

실제 최단 경로 구하기

플로이드를 수행하면서 실제 최단 경로를 구할 수 있다. from[i][j]를 $i \rightarrow j$에서 경유한 정점의 번호(경유하지 않았다면 $-1$)이라고 했을 때, 이를 바탕으로 재귀 호출을 하면서 경로를 구하면 된다.

 

from[i][j] == -1이면 $i$에서 $j$로 곧바로 간 것이므로 path 배열에 $i, j$를 push하고, 아니라면 경유점 $w$를 통하므로 $i\rightarrow w$를 재귀 호출, path 맨 뒤를 pop($w$가 겹치므로), $w \rightarrow j$를 재귀 호출한다.

int adj[MAX][MAX]; // 인접 행렬
int from[MAX][MAX]; // 경유 정점
int n; // 정점 수

const int INF = 0x3f3f3f3f; // 무한대 값

void floyd() {
    memset(adj, INF, sizeof(adj));
    memset(from, -1, sizeof(from)); // 경유점을 -1로 초기화
    for (int i = 0; i < MAX; i++) adj[i][i] = 0;

    input(); // 그래프 입력

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (adj[i][k] + adj[k][j] < adj[i][j]) { // 만약 k를 경유하는 거리가 더 짧으면
                    adj[i][j] = adj[i][k] + adj[k][j]; // k를 경유하는 거리로 갱신
                    from[i][j] = k; // 경유점 저장
                }
            }
        }
    }
}

void rec(int i, int j, vector<int> &path) {
    // rec(i, j, path): i -> j 경로를 path에 저장

    if (from[i][j] == -1) {
        path.push_back(i);
        path.push_back(j);
        return;
    }

    int w = from[i][j];
    rec(i, w, path);
    path.pop_back();
    rec(w, j, path);
}

    티스토리툴바