YEAHx4YEAHx4
PS

Floyd-Warshall

플로이드-워셜

YEAHx4

YEAHx4

2025-05-29
9 mins

이번 챕터에서 시작해서 앞으로 몇 개의 챕터에 걸쳐서 최단 경로(shortest path) 알고리즘에 대해 알아보겠습니다. 최단 경로 알고리즘은 그래프 이론에서 매우 중요한 알고리즘입니다. 모든 최단 경로 알고리즘의 목적은 그래프에서 두 정점 사이의 최단 경로를 찾는 것입니다. 최단 경로 알고리즘에는 다양한 종류가 있지만, 목적은 모두 같습니다. 각 알고리즘마다 장점, 단점, 한계가 있으니 상황에 맞게 선택해 사용하면 됩니다.

플로이드-워셜

플로이드-워셜은 "모든" 정점 쌍 사이의 최단 경로를 찾는 알고리즘입니다. 여기서 모든 이라는 말이 중요합니다. 많은 경우 시작점이 정해져 있고, 시작점에서 다른 정점으로 가는 최단 경로를 찾습니다. 하지만 플로이드-워셜은 모든 정점 쌍 사이의 최단 경로를 찾습니다. 그래서 다른 최단 경로 알고리즘에 비해 느리지만, 한 번 구해 놓으면 \( O(1) \)시간에 최단경로를 읽을 수 있습니다.

설명을 위해 \( D_{ij} \)를 정점 \( i \)에서 정점 \( j \)로 가는 경로의 길이라고 하겠습니다. \( n \)개의 정점이 있는 그래프에서 플로이드-워셜 알고리즘은 \( n \times n \) 크기의 2차원 배열을 만듭니다. 배열의 이름을 dist라고 할때 \( D_{ij} \)는 dist[i][j]로 표현합니다. 즉, 알고리즘의 실행이 끝나면 dist가 완성되고 dist[i][j]는 정점 \( i \)에서 정점 \( j \)로 가는 최단 경로의 길이가 됩니다.

작동 방식

플로이드-워셜의 기본 아이디어는 다음과 같습니다. \( i \)에서 \( j \)로 갈 때 중간에 다른 정점 \( k \)를 지날 수 있고, \( k \)를 거쳐서 가는게 더 빠르다면 \( i \)에서 \( j \)로 가는 경로를 \( i \to k \to j \)로 바꿉니다. 점화식으로 표현하면 다음과 같습니다.

\[ D_{ij} = \min(D_{ij}, D_{ik} + D_{kj}) \]

이 아이디어와 dp를 결합하면 플로이드-워셜 알고리즘을 만들 수 있습니다.

좀더 엄밀한 증명을 위해 귀납법을 통해 설명하겠습니다. 이 부분은 그렇구나 하고 넘어가셔도 됩니다. 처음 상태에서 \( D^{(0)}_{ij} \)는 \( i \)와 \( j \)를 직접 연결하는 간선의 길이입니다. 만약 \( i \)와 \( j \)를 직접 연결하는 간선이 없다면 \( D^{(0)}_{ij} = \infty \)입니다. 여기서 \( D^{(k - 1)}_{ij} \)는 1번부터 \( k - 1 \)번 까지의 정점을 고려해 \( i \)에서 \( j \)로 가는 최단 경로의 길이입니다. 여기서 고려한다는 의미는 위의 점화식을 통해 지나거나 지나지 않는다는 의미입니다. 여기서 \( k \)번째 정점을 고려할 때, \( D^{(k)}_{ij} \)는 다음과 같이 정의됩니다.

\[ D^{(k)}_{ij} = \min(D^{(k - 1)}_{ij}, D^{(k - 1)}_{ik} + D^{(k - 1)}_{kj}) \]

즉, \( D^{(k)}_{ij} \)는 \( k \)번째 정점을 고려했을 때 \( i \)에서 \( j \)로 가는 최단 경로의 길이입니다. 따라서 \( D^{(n)}_{ij} \)는 모든 정점을 고려했을 때 \( i \)에서 \( j \)로 가는 최단 경로의 길이가 됩니다.

구현

플로이드-워셜 알고리즘은 3개의 반복문을 사용해서 간단히 구현할 수 있습니다. 먼저 2차원 배열을 만들고, dist[i][i]는 0으로 dist[i][j]는 INF로 초기화합니다. 그 다음, 간선의 길이를 입력받아 dist[i][j]에 저장합니다. 마지막으로 3개의 반복문을 사용해서 위에서 살펴본 점화식을 적용합니다. 그러면 dist[i][j]는 정점 \( i \)에서 정점 \( j \)로 가는 최단 경로의 길이가 됩니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int dist[n + 1][n + 1];
    memset(dist, 0x3f, sizeof(dist));

    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
        dist[v][u] = w;
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

반복문의 순서에 주의하세요. 정점이 \( N \)개일 때 시간복잡도는 \( O(N^3) \)입니다. 시간복잡도가 큰 대신 모든 정점 쌍 사이의 최단 경로를 구하기 때문에 필요한 경우에만 사용해야 합니다.

연습문제