플로이드–워셜 알고리즘

최단 경로 알고리즘은 보통 한 정점에서 나머지 전부로 가는 거리를 푼다. 다익스트라와 벨만-포드 모두 시작점이 하나다. 모든 정점에서 모든 정점으로 가는 거리가 필요하면 다익스트라를 V번 돌릴 수도 있지만, 우선순위 큐와 인접 리스트를 매번 다시 세팅해야 하고 음수 가중치가 있으면 쓸 수 없다.

플로이드-워셜은 시작점을 고정하지 않는다. 거리 행렬 하나를 놓고 3중 루프를 한 번 돌면 모든 쌍의 최단 거리가 행렬에 채워진다. 코드는 12줄이고, 음수 간선을 처리하며, 음수 사이클의 존재 여부까지 알려준다.

핵심 아이디어

알고리즘 전체가 하나의 질문을 반복한다. 정점 i에서 j로 갈 때 정점 k를 경유하면 더 짧아지는가?

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

D[i][k] + D[k][j]는 i에서 k까지 간 뒤 k에서 j까지 가는 경로의 길이다. 이 값이 지금까지 알던 D[i][j]보다 짧으면 갱신한다. 이 한 줄을 모든 (i, j) 쌍에 대해 k를 1부터 V까지 바꿔 가며 적용하는 것이 전부다.

허용되는 경유지를 한 칸씩 늘려간다고 보면 된다. k=1 단계에서는 정점 1만 경유지로 쓸 수 있고, k=2에서는 1과 2를, k=V에서는 모든 정점을 쓸 수 있다. 경유지 집합이 전부 열리는 마지막 단계가 끝나면 최단 거리가 나온다. 부분 경로의 최단성이 전체 최단 경로의 최단성으로 이어진다는 최적 부분 구조 덕분에 이 점진적 확장이 성립한다.

3차원 점화식 D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])를 2차원 배열로 압축할 수 있는데, k번째 단계에서 D[i][k]와 D[k][j]는 어차피 k를 경유지로 쓰지 않은 값과 같기 때문에 같은 배열을 덮어써도 안전하다.

루프 순서

for k in 1..V:      # 경유지 (반드시 가장 바깥)
    for i in 1..V:  # 출발
        for j in 1..V:  # 도착
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

순서는 반드시 k → i → j다. k가 안쪽으로 들어가면 경유지를 한 칸씩 늘린다는 전제가 깨져서 틀린 답이 나온다. k가 가장 바깥에 있어야 k번째 단계가 k-1번째까지의 결과만 사용한다는 보장이 생긴다. 나머지는 기계적이다.

손으로 따라가는 실행

정점 4개에 간선이 다음과 같은 방향 그래프다.

간선: 1→2(3), 1→3(8), 2→3(2), 2→4(5), 3→4(1)

아래 행렬 추적은 위 점화식을 코드로 옮겨 출력한 결과다.

초기 행렬 (간선만 채우고 나머지는 INF, 대각선은 0):

      1    2    3    4
1 [   0    3    8  INF ]
2 [ INF    0    2    5 ]
3 [ INF  INF    0    1 ]
4 [ INF  INF  INF    0 ]

k=1 (정점 1을 경유지로): 1을 거쳐 더 짧아지는 경로가 없다. 변화 없음.

k=2 (정점 1, 2를 경유지로): 2를 거치는 경로가 열린다.

• D[1][3] = min(8, D[1][2]+D[2][3]) = min(8, 3+2) = 5 (1→2→3)
• D[1][4] = min(INF, D[1][2]+D[2][4]) = min(INF, 3+5) = 8 (1→2→4)

      1    2    3    4
1 [   0    3    5    8 ]
2 [ INF    0    2    5 ]
3 [ INF  INF    0    1 ]
4 [ INF  INF  INF    0 ]

k=3 (정점 1, 2, 3을 경유지로): 3을 거치며 더 줄어든다.

• D[1][4] = min(8, D[1][3]+D[3][4]) = min(8, 5+1) = 6 (1→2→3→4)
• D[2][4] = min(5, D[2][3]+D[3][4]) = min(5, 2+1) = 3 (2→3→4)

      1    2    3    4
1 [   0    3    5    6 ]
2 [ INF    0    2    3 ]
3 [ INF  INF    0    1 ]
4 [ INF  INF  INF    0 ]

k=4: 4는 나가는 간선이 없어 경유지로 쓸모가 없다. 변화 없음. 이것이 최종 결과다. 예를 들어 1에서 4까지의 최단 거리는 6이며, 경로는 1→2→3→4다.

구현

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

int main() {
    int n, m; // n: 정점 수, m: 간선 수
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));

    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0; // 자기 자신으로의 거리는 0
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], (long long)c); // 중복 간선은 최솟값
    }

    // 3중 루프 — k가 가장 바깥
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 음수 사이클 검사: 자기 자신까지 거리가 음수면 존재
    bool hasNegativeCycle = false;
    for (int i = 1; i <= n; i++) {
        if (dist[i][i] < 0) { hasNegativeCycle = true; break; }
    }

    if (hasNegativeCycle) {
        cout << "음수 사이클이 존재합니다." << '\n';
    } else {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == INF) cout << "INF ";
                else cout << dist[i][j] << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

알고리즘 본체는 3중 루프 그대로이고, 실수는 주변에서 나온다.

• dist[i][i] = 0 초기화를 빠뜨리면 자기 자신까지의 거리가 INF로 남아 음수 사이클 검사가 망가지고 결과도 틀어진다.
• dist[i][k] != INF && dist[k][j] != INF 가드. INF끼리 더하면 오버플로우로 음수가 되어 존재하지 않는 경로가 짧은 경로로 둔갑한다. 더하기 전에 검사한다.
• 중복 간선. 같은 (a, b)에 여러 간선이 올 수 있으니 최솟값을 취한다.
• 무향 그래프. (a, b)와 (b, a)를 둘 다 넣는다.

음수 사이클 탐지

플로이드-워셜이 다익스트라보다 나은 지점은 음수 간선이다. 다익스트라는 한 번 확정한 거리가 다시 줄지 않는다고 가정해 음수 간선에서 깨지지만, 플로이드-워셜은 모든 경유 조합을 빠짐없이 검토하므로 음수 간선이 있어도 정확하다.

음수 사이클은 한 바퀴 돌 때 가중치 합이 음수인 사이클이다. A → B → C → A의 합이 -5라면 돌수록 거리가 -5, -10, -15로 끝없이 줄어 최단 경로 자체가 정의되지 않는다.

탐지는 간단하다. 알고리즘이 끝난 뒤 대각선만 보면 된다. 정상이라면 자기 자신으로 돌아오는 거리 D[i][i]는 0이다. 음수 사이클이 있으면 그 사이클 위의 정점은 자기 자신으로 돌아오는 길에서 음수가 누적되어 D[i][i] < 0이 된다. O(V) 한 번 훑기로 끝난다.

이 성질은 환차익(arbitrage) 탐지에 쓰인다. 화폐 간 환율 r을 -log(r)로 바꾸면 환전의 곱셈이 덧셈이 되고, 음수 사이클이 곧 환전을 반복하면 무위험 수익이 나는 고리가 된다.

경로 복원

거리만으로 부족하고 실제 경로가 필요하면 next 배열을 함께 유지한다. next[i][j]는 i에서 j로 가는 최단 경로에서 i 다음에 밟을 정점이다.

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

void printPath(int i, int j, vector<vector<int>>& next) {
    if (next[i][j] == -1) { cout << "경로 없음" << '\n'; return; }
    cout << i;
    while (i != j) {
        i = next[i][j];
        cout << " -> " << i;
    }
    cout << '\n';
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> next(n + 1, vector<int>(n + 1, -1));

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

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c < dist[a][b]) {
            dist[a][b] = c;
            next[a][b] = b; // 직접 연결된 정점으로 시작
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k]; // 경유지 k 쪽 첫 정점을 물려받는다
                }
            }
        }
    }

    printPath(1, n, next); // 1 -> n 경로 출력
    return 0;
}

거리를 갱신할 때 next[i][j] = next[i][k]로 함께 갱신하는 것이 요점이다. i에서 j로 가는 더 짧은 길이 k를 경유하면, 그 길의 첫걸음은 i에서 k로 가는 길의 첫걸음과 같다. 출력할 때는 next를 따라가며 정점을 차례로 나열한다. 위 그래프에 적용하면 1→4 경로로 1 -> 2 -> 3 -> 4가 나온다. 경로 복원이 필요할지 모른다면 처음부터 next를 유지한다. 나중에 붙이려면 알고리즘을 다시 돌려야 한다.

O(V³)의 의미와 한계

3중 루프가 각각 V번 도므로 연산 횟수는 V³이고, 각 연산은 덧셈·비교·갱신으로 상수 시간이다. 공간은 거리 행렬 O(V²)이며 next를 더해도 O(V²)다.

V가 세제곱으로 들어가므로 정점이 수백 개를 넘으면 급격히 느려진다. 플로이드-워셜은 정점이 적고 간선이 빽빽한 그래프에 어울린다.

모든 쌍이 필요하고 그래프가 작거나 밀집했거나 음수 간선이 있으면 플로이드-워셜을 쓴다. 시작점이 하나뿐이거나, 정점이 많고 간선이 희소하면서 가중치가 양수면 다익스트라가 낫다.