Algorithms/Graph Algorithms

2.17.3 Floyd–Warshall

개념

플로이드–워셜은 모든 시작점과 도착점 쌍의 최단 거리를 한 번에 구합니다. 다익스트라와 벨만–포드가 한 시작점에서의 거리를 구하는 것과 달리, 결과를 정점 수만큼의 행과 열을 가진 거리 표로 만듭니다. 여러 출발지와 도착지에 대한 질문이 반복될 때 이 표에서 답을 바로 찾을 수 있습니다.

경유 정점을 하나씩 허용하기

처음에는 직접 연결된 간선의 비용을 기록합니다. 같은 두 정점을 잇는 간선이 여러 개이면 가장 작은 비용을 사용하고, 자기 자신까지의 거리는 00으로 둡니다. 직접 연결되지 않은 정점 쌍은 아직 도달하지 못한 상태입니다.

정점 ii에서 jj까지 현재 구한 거리를 d(i,j)d(i,j)라고 하겠습니다. 이제 정점 kk를 중간에 거치는 경로를 추가로 고려합니다. 기존 경로와 i→k→ji\to k\to j 경로 중 더 짧은 쪽을 선택합니다.

d(i,j)=min⁡(d(i,j), d(i,k)+d(k,j)).d(i,j)=\min\bigl(d(i,j),\ d(i,k)+d(k,j)\bigr).

아래는 정점 66개와 방향 간선 1010개가 있는 그래프입니다. 6→26\to2가 있어 여러 정점을 돌아오는 경로도 있습니다. 각 간선 위의 수는 비용입니다.

3 8 2 5 1 4 2 7 1 6 1 2 3 4 5 6
▲ [그림 1] 모든 정점 쌍의 거리를 구할 그래프

거리 표의 행은 출발점, 열은 도착점입니다. 정점 1,21,2까지 경유를 허용한 상태에서는 1→2→31\to2\to3의 비용 3+2=53+2=5, 1→2→41\to2\to4의 비용 3+5=83+5=8을 기록합니다. ∞\infty는 현재 허용된 경유 정점으로는 경로를 찾지 못한 상태입니다.

1 1 0 3 5 8 ∞ ∞ 2 2 ∞ 0 2 5 ∞ ∞ 3 3 ∞ ∞ 0 1 4 ∞ 4 4 ∞ ∞ ∞ 0 2 7 5 5 ∞ ∞ ∞ ∞ 0 1 6 6 ∞ 6 8 11 ∞ 0
▲ [그림 2] 정점 1과 2까지 경유를 허용한 거리 표

이제 정점 33도 경유할 수 있게 합니다. 11에서 33까지의 거리 55와 3→43\to4의 비용 11을 더하면 66입니다. 따라서 11행 44열이 88에서 66으로 줄어듭니다. 22행 44열도 55에서 2+1=32+1=3으로 줄어듭니다.

또한 1,2,61,2,6에서 33을 거쳐 55로 가는 경로를 새로 찾습니다. 진한 칸은 이번 단계에서 값이 줄어든 칸입니다. 하나의 경유 정점을 추가하면 여러 출발지·도착지 쌍의 거리가 함께 바뀔 수 있습니다.

1 1 0 3 5 6 9 ∞ 2 2 ∞ 0 2 3 6 ∞ 3 3 ∞ ∞ 0 1 4 ∞ 4 4 ∞ ∞ ∞ 0 2 7 5 5 ∞ ∞ ∞ ∞ 0 1 6 6 ∞ 6 8 9 12 0
▲ [그림 3] 정점 3을 경유하여 여러 정점 쌍의 거리 갱신

이후 4,5,64,5,6도 차례로 경유 정점에 포함하면 모든 정점 쌍의 최단 거리를 얻습니다.

두 구간 중 하나라도 도달할 수 없다면 그 경유 경로를 만들 수 없습니다.

경유 정점의 순서가 중요한 이유

정점을 11번부터 차례대로 경유지로 허용합니다. kk번째 단계가 시작될 때는 중간 정점으로 11번부터 k−1k-1번까지 사용할 수 있는 최단 거리가 준비되어 있습니다.

새 경로는 kk를 거치지 않거나, kk를 거치는 두 경우로 나뉩니다. 전자는 기존 거리이고, 후자는 ii에서 kk까지와 kk에서 jj까지의 거리를 합한 값입니다. 따라서 위 식으로 두 경우를 비교하면 kk번까지 경유할 수 있는 최단 거리를 얻습니다.

한 경유 정점에 대해 모든 출발지·도착지 쌍을 갱신한 뒤 다음 경유 정점으로 넘어갑니다. 이 단계 순서를 유지하도록 경유 정점에 대한 반복을 가장 바깥에 둡니다.

정점 수와 계산량

정점 수를 VV라고 하면 경유 정점, 출발지, 도착지를 각각 VV개씩 살펴보므로 총 V3V^3개의 조합을 확인합니다. 간선 수가 적더라도 이 반복 범위는 같습니다.

정점 수 VV확인하는 조합 수 V3V^3
100100100100만
30030027002700만
50050011억 25002500만
100010001010억

대회에서는 정점이 수백 개 정도인 모든 쌍 최단 거리 문제에서 먼저 고려할 수 있습니다. 500500개라면 이미 11억 회가 넘는 반복이므로 시간 제한과 사용 언어를 함께 확인해야 합니다. 특히 Python은 같은 정점 수에서도 반복문의 실행 시간이 C++과 다를 수 있습니다. 500500은 통과를 보장하는 고정 기준이 아닙니다.

출발지가 하나뿐이거나, 큰 희소 그래프에서 일부 출발지의 거리만 필요하다면 필요한 출발지에서의 거리만 계산하면 됩니다. 가중치가 00 이상인 경우에는 필요한 출발지마다 다익스트라를 실행하는 방법과 비교합니다.

음수 간선과 알고리즘 선택

플로이드–워셜은 음수 간선도 처리합니다. 다만 음수 사이클을 거치는 경로는 반복할수록 비용이 줄어들어 유한한 최단 거리가 없습니다. 계산 후 d(i,i)<0d(i,i)<0인 정점이 있다면, 자기 자신으로 돌아오면서 비용이 줄어드는 음수 사이클이 있다는 뜻입니다.

알고리즘구하는 거리가중치 조건과 특징주로 확인할 입력 조건
BFS한 시작점에서 각 정점까지모든 간선의 비용이 같을 때 이동 횟수 계산정점 수와 간선 수
다익스트라한 시작점에서 각 정점까지가중치가 모두 00 이상필요한 출발지 수, 정점 수와 간선 수
벨만–포드한 시작점에서 각 정점까지음수 간선 처리, 도달 가능한 음수 사이클 판별정점 수와 간선 수의 곱
플로이드–워셜모든 정점 쌍 사이음수 간선 처리, 저장된 표에서 두 정점 사이의 거리 조회정점 수의 세제곱과 거리 표 크기

복잡도

정점 수를 VV라고 합니다. 정점 수가 작은 그래프의 모든 쌍 거리가 필요할 때 사용합니다.

연산시간복잡도공간복잡도
모든 쌍 최단 거리O(V3)O(V^3)거리 표 O(V2)O(V^2)

예제

문제

방향 그래프의 모든 정점 쌍에 대해 최단 거리를 구하여라.

입력

첫째 줄에 정점 수 NN과 간선 수 MM이 공백을 사이에 두고 주어진다. 1≤N≤501\le N\le50; 0≤M≤2000\le M\le200이다.

다음 MM개 줄에 간선의 시작점 aa, 끝점 bb, 가중치 ww가 공백을 사이에 두고 주어진다. 1≤a,b≤N1\le a,b\le N; 1≤w≤1001\le w\le100이다. 같은 두 정점을 잇는 간선이 여러 개 주어질 수 있다.

출력

NN개 줄에 거리 표를 출력한다. ii번째 줄에는 정점 ii에서 정점 11부터 NN까지의 최단 거리를 번호 순서대로 공백을 사이에 두고 출력한다. 도달할 수 없는 정점의 거리는 -1, 자신까지의 거리는 0으로 출력한다.

예제 입력

3 3
1 2 2
2 3 3
1 3 8

예제 출력

0 2 5
-1 0 3
-1 -1 0

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> d;

int main() {
    const int INF = 1000000;
    int n, m, i, j, k, a, b, w;

    cin >> n >> m;
    d.assign(n + 1, vector<int>(n + 1, INF));
    for (i = 1; i <= n; ++i) {
        d[i][i] = 0;
    }
    for (i = 0; i < m; ++i) {
        cin >> a >> b >> w;
        // 같은 두 정점 사이의 여러 간선 중 최소 가중치 저장
        d[a][b] = min(d[a][b], w);
    }

    // 경유 가능한 정점을 k까지 확장하므로 k를 가장 바깥에서 순회
    for (k = 1; k <= n; ++k) {
        for (i = 1; i <= n; ++i) {
            for (j = 1; j <= n; ++j) {
                // i에서 k 또는 k에서 j로 갈 수 없으면 경로 결합 제외
                if (d[i][k] == INF || d[k][j] == INF) continue;
                // 기존 거리와 i → k → j 경로의 거리 비교
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= n; ++j) {
            if (d[i][j] == INF) cout << -1 << ' ';
            else cout << d[i][j] << ' ';
        }
        cout << '\n';
    }
}