콘텐츠로 이동

Floyd-Warshall 알고리즘

정점이 $n$개인 방향 또는 무방향 가중치 그래프 $G$가 주어집니다. 목표는 모든 정점 쌍 $i$와 $j$ 사이의 최단 경로 길이 $d_{ij}$를 구하는 것입니다.

그래프에는 음수 가중치 간선이 있을 수 있지만, 음수 가중치 사이클은 없어야 합니다.

그러한 음수 사이클이 있다면 이 사이클을 계속해서 반복하여 돌 수 있으며, 매 반복마다 경로의 비용이 더 작아집니다. 따라서 특정 경로를 임의로 작게 만들 수 있으며, 다시 말해 그러한 최단 경로는 정의되지 않습니다. 이는 곧 무방향 그래프에는 음수 가중치 간선이 하나도 있을 수 없다는 뜻입니다. 그러한 간선을 따라 원하는 만큼 앞뒤로 오갈 수 있으므로, 그 간선 자체가 이미 음수 사이클을 이루기 때문입니다.

이 알고리즘은 음수 사이클의 존재를 검출하는 데에도 사용할 수 있습니다. 알고리즘이 끝났을 때 어떤 정점 $v$에서 자기 자신까지의 거리가 음수이면 그래프에 음수 사이클이 있습니다.

이 알고리즘은 1962년에 Robert Floyd와 Stephen Warshall의 논문에서 동시에 발표되었습니다. 그러나 1959년에 Bernard Roy가 본질적으로 같은 알고리즘을 발표하였으나, 그 발표는 주목받지 못했습니다.

알고리즘 설명

이 알고리즘의 핵심 아이디어는 임의의 두 정점 사이의 최단 경로를 찾는 과정을 여러 개의 점진적인 단계로 나누는 것입니다.

정점에 1부터 $n$까지 번호를 매깁시다. 거리 행렬은 $d[ ][ ]$입니다.

$k$번째 단계($k = 1 \dots n$) 이전에, 임의의 정점 $i$와 $j$에 대해 $d[i][j]$는 정점 $i$와 정점 $j$ 사이의 경로 중 내부 정점으로 $\{1, 2, ..., k-1\}$의 정점만을 포함하는 최단 경로의 길이를 저장합니다.

다시 말해, $k$번째 단계 이전에 $d[i][j]$의 값은 정점 $i$에서 정점 $j$로 가는 경로가 번호가 $k$보다 작은 정점만 거쳐 갈 수 있을 때의 최단 경로 길이와 같습니다(경로의 시작점과 끝점은 이 조건의 제약을 받지 않습니다).

첫 번째 단계에서 이 성질이 성립함은 쉽게 확인할 수 있습니다. $k = 0$일 때, $i$와 $j$ 사이에 가중치가 $w_{i j}$인 간선이 있으면 $d[i][j] = w_{i j}$로, 간선이 없으면 $d[i][j] = \infty$로 행렬을 채우면 됩니다. 실제로는 $\infty$를 충분히 큰 값으로 둡니다. 뒤에서 살펴보겠지만, 이는 알고리즘에 필요한 조건입니다.

이제 $k$번째 단계에 있으며, 행렬 $d[ ][ ]$가 $(k + 1)$번째 단계의 조건을 만족하도록 계산하려 한다고 가정합시다. 일부 정점 쌍 $(i, j)$에 대해서는 거리를 갱신해야 합니다. 근본적으로 서로 다른 두 가지 경우가 있습니다:

  • 내부 정점이 집합 $\{1, 2, \dots, k\}$에 속하는 정점 $i$에서 정점 $j$로의 최단 경로가, 내부 정점이 집합 $\{1, 2, \dots, k-1\}$에 속하는 최단 경로와 일치하는 경우입니다.

    이 경우에는 전이 과정에서 $d[i][j]$가 바뀌지 않습니다.

  • 내부 정점이 $\{1, 2, \dots, k\}$에 속하는 최단 경로가 더 짧은 경우입니다.

    이는 새롭고 더 짧은 경로가 정점 $k$를 지난다는 뜻입니다. 이는 $i$와 $j$ 사이의 최단 경로를 $i$와 $k$ 사이의 경로, 그리고 $k$와 $j$ 사이의 경로라는 두 경로로 나눌 수 있다는 뜻입니다. 두 경로 모두 $\{1, 2, \dots, k-1\}$의 내부 정점만 사용하며, 그러한 조건을 만족하는 경로 중 최단 경로임이 분명합니다. 따라서 이 경로들의 길이는 이미 앞에서 계산해 두었으며, $i$와 $j$ 사이의 최단 경로 길이는 $d[i][k] + d[k][j]$로 계산할 수 있습니다.

이 두 경우를 종합하면, $k$번째 단계에서 모든 쌍 $(i, j)$의 길이를 다음과 같이 다시 계산할 수 있습니다:

$$d_{\text{new}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

따라서 $k$번째 단계에서 해야 할 일은 모든 정점 쌍을 순회하면서 그 사이의 최단 경로 길이를 다시 계산하는 것뿐입니다. 결과적으로 $n$번째 단계가 끝나면 거리 행렬의 값 $d[i][j]$는 $i$와 $j$ 사이의 최단 경로 길이가 되며, 정점 $i$와 $j$ 사이에 경로가 존재하지 않으면 $\infty$가 됩니다.

마지막으로 한 가지 짚어 두자면, $k$번째 단계의 최단 경로를 임시로 저장하기 위해 별도의 거리 행렬 $d_{\text{new}}[ ][ ]$를 만들 필요는 없습니다. 즉, 모든 변경은 어느 단계에서든 행렬 $d[ ][ ]$에 직접 반영할 수 있습니다. 실제로 어느 $k$번째 단계에서든 우리는 거리 행렬에 있는 경로의 거리를 개선하기만 할 뿐이므로, $(k+1)$번째 이후 단계에서 처리될 어떤 정점 쌍에 대해서도 최단 경로의 길이를 더 나쁘게 만들 수 없습니다.

이 알고리즘의 시간 복잡도는 명백히 $O(n^3)$입니다.

구현

$d[][]$를 앞서 설명한 대로 $0$번째 단계에 따라 채워진 $n \times n$ 크기의 2차원 배열이라고 합시다. 또한 $0$번째 단계에서 모든 $i$에 대해 $d[i][i] = 0$으로 설정합니다.

그러면 알고리즘은 다음과 같이 구현됩니다.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

두 정점 $i$와 $j$ 사이에 간선이 없으면 행렬의 $d[i][j]$에는 큰 수(이 그래프의 어떤 경로 길이보다도 클 만큼 충분히 큰 수)가 들어 있다고 가정합니다. 그러면 이 간선은 항상 택하는 것이 불리하므로 알고리즘이 올바르게 동작합니다.

그러나 그래프에 음수 가중치 간선이 있다면 특별한 조치를 취해야 합니다. 그렇지 않으면 행렬의 결과값이 $\infty - 1$, $\infty - 2$ 등의 형태가 될 수 있는데, 물론 이는 여전히 해당 정점들 사이에 경로가 존재하지 않음을 나타냅니다. 따라서 그래프에 음수 가중치 간선이 있다면, 존재하지 않는 경로를 이용한 전이를 수행하지 않도록 Floyd-Warshall 알고리즘을 다음과 같이 작성하는 것이 좋습니다.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

최단 경로의 정점 순서 복원하기

주어진 임의의 두 정점 사이의 최단 경로를 정점의 나열 형태로 복원할 수 있도록 추가 정보를 유지하는 것은 쉽습니다.

이를 위해 거리 행렬 $d[ ][ ]$ 외에 조상 행렬 $p[ ][ ]$를 유지해야 하며, 이 행렬에는 두 정점 사이의 최단 거리가 마지막으로 갱신된 단계의 번호가 저장됩니다. 이 단계의 번호가 다름 아닌 구하려는 최단 경로 중간에 있는 정점이라는 것은 분명합니다. 이제 정점 $i$와 $p[i][j]$ 사이, 그리고 $p[i][j]$와 $j$ 사이의 최단 경로를 찾기만 하면 됩니다. 이로부터 최단 경로를 복원하는 간단한 재귀 알고리즘을 얻을 수 있습니다.

실수 가중치의 경우

간선의 가중치가 정수가 아니라 실수라면, 부동소수점 자료형을 다룰 때 발생하는 오차를 고려해야 합니다.

Floyd-Warshall 알고리즘에는 오차가 매우 빠르게 누적된다는 달갑지 않은 성질이 있습니다. 실제로 첫 번째 단계에서 $\delta$만큼의 오차가 있다면, 이 오차는 두 번째 반복에서 $2 \delta$, 세 번째 반복에서 $4 \delta$와 같은 식으로 전파될 수 있습니다.

이를 피하기 위해 다음과 같은 비교를 사용하여 오차(EPS = $\delta$)를 고려하도록 알고리즘을 수정할 수 있습니다.

if (d[i][k] + d[k][j] < d[i][j] - EPS)
    d[i][j] = d[i][k] + d[k][j];

음수 사이클의 경우

엄밀히 말하면 Floyd-Warshall 알고리즘은 음수 가중치 사이클을 포함하는 그래프에는 적용되지 않습니다. 그러나 $i$에서 시작하여 음수 사이클을 거쳐 $j$에서 끝나는 경로가 존재하지 않는 모든 정점 쌍 $i$와 $j$에 대해서는 알고리즘이 여전히 올바르게 동작합니다.

(두 정점 사이의 경로에 음수 사이클이 있어서) 답이 존재하지 않는 정점 쌍에 대해서는 Floyd 알고리즘이 거리 행렬에 임의의 수(아마도 매우 작은 음수이겠지만 반드시 그렇지는 않음)를 저장합니다. 하지만 Floyd-Warshall 알고리즘을 개선하여 이러한 정점 쌍을 신중하게 처리하고, 예를 들어 $-\text{INF}$로 출력하도록 할 수 있습니다.

이는 다음과 같이 할 수 있습니다. 주어진 그래프에 대해 일반적인 Floyd-Warshall 알고리즘을 실행합시다. 그러면 정점 $i$와 $j$ 사이의 최단 경로가 존재하지 않을 필요충분조건은 $i$에서 $t$에 도달할 수 있고 $t$에서 $j$에 도달할 수 있으며 $d[t][t] < 0$인 정점 $t$가 존재하는 것입니다.

또한 음수 사이클이 있는 그래프에 Floyd-Warshall 알고리즘을 사용할 때에는 거리가 음의 방향으로 지수적으로 빠르게 커지는 상황이 발생할 수 있다는 점을 염두에 두어야 합니다. 따라서 최소 거리를 어떤 값(예: $-\text{INF}$)으로 제한하여 정수 오버플로를 처리해야 합니다.

그래프에서 음수 사이클을 찾는 방법에 대해 더 알아보려면 별도의 글 그래프에서 음수 사이클 찾기를 참고하십시오.

연습 문제