Floyd-Warshall Algorithm - 플로이드 워셜 알고리즘

이 글의 목차

인터랙티브

중간 정점을 하나씩 허용하는 모든 쌍 최단 경로

k 진행자동초기화

방향 그래프

거리 행렬

	A	B	C	D	E
A	0	∞	∞	∞	∞
B	∞	0	∞	∞	∞
C	∞	∞	0	∞	∞
D	∞	∞	∞	0	∞
E	∞	∞	∞	∞	0

k 진행을 눌러 A를 중간 정점으로 허용하세요.

dist[i][j] ← min(dist[i][j], dist[i][k] + dist[k][j])

모든 쌍 최단 경로를 구하는 플로이드–워셜

여러 정점 쌍 사이의 거리가 필요할 때마다 단일 출발점 탐색을 반복하면 비효율적일 수 있습니다. 플로이드–워셜은 각 정점을 중간 경유지로 하나씩 허용하는 동적 계획법입니다. 음수 간선도 다룰 수 있지만, 조회하는 정점 쌍의 경로에 영향을 주는 음수 사이클이 없어야 유한한 최단 거리가 정의됩니다.

점화식과 불변식

정점 번호를 0부터 V - 1까지 붙입니다. 중간 정점 0, ..., k - 1을 처리한 뒤 D[i][j]를 처리된 정점만 내부 경유지로 쓰는 i에서 j까지의 최소 경로 비용이라 합시다. 처음에는 중간 정점을 허용하지 않습니다. D[i][i] = 0으로 두고, 직접 간선이 있으면 그 가중치(평행 간선은 최솟값)를 넣으며, 간선이 없으면 무한대로 둡니다.

단계 k의 최적 경로는 k를 거치지 않거나 k를 거칩니다. 후자는 k에서 두 부분 경로로 나뉘고, 두 부분 경로의 내부 정점은 앞 단계에서 허용된 정점뿐입니다. 따라서 다음과 같이 갱신합니다.

$$D[i][j]\leftarrow\min(D[i][j],D[i][k]+D[k][j]).$$

1. 단계 k 이전 허용된 내부 경유 정점: {0, …, k − 1}

   D[i][j]는 이 정점들만 내부 경유지로 사용합니다.

2. k를 사용해 갱신 D[i][j] ← min(D[i][j], D[i][k] + D[k][j])

   최단 경로는 k를 피하거나 k에서 두 부분으로 나뉩니다.

3. 단계 k 이후 허용된 내부 경유 정점: {0, …, k}

   이 단계 전체를 마쳐야 k+1을 허용할 수 있습니다.

가장 바깥 반복문은 중간 정점 k에 대한 반복이어야 합니다. k+1을 허용하기 전에 k 단계 전체를 완료해야 이 불변식에 따라 점화식이 구현됩니다.

실행 가능한 C++ 예제

아래 함수는 n >= 0, 모든 간선의 양 끝점이 [0,n)에 있고, 입력 가중치와 점화식에서 생기는 유한한 합이 -INF와 INF 사이이며 int64_t 범위 안에 있다고 가정합니다. INF는 도달할 수 없음을 나타냅니다. 더하기 전에 양쪽 값이 모두 INF가 아닌지 확인합니다. 가중치 0인 간선도 유효하므로 참·거짓 값으로 간선 존재를 판단하지 않습니다. 예제는 유향 그래프를 읽어 도달할 수 없는 쌍에 INF를 출력합니다. 구조 분해 선언을 사용하므로 C++17 이상이 필요합니다.

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>

using Weight = std::int64_t;
constexpr Weight INF = (Weight{1} << 60);

std::vector<std::vector<Weight>> floydWarshall(
    int n, const std::vector<std::tuple<int, int, Weight>>& edges) {
  std::vector<std::vector<Weight>> dist(n, std::vector<Weight>(n, INF));
  for (int i = 0; i < n; ++i) dist[i][i] = 0;
  for (const auto& [from, to, weight] : edges)
    dist[from][to] = std::min(dist[from][to], weight);

  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i) {
      if (dist[i][k] == INF) continue;
      for (int j = 0; j < n; ++j) {
        if (dist[k][j] == INF) continue;
        dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  return dist;
}

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::tuple<int, int, Weight>> edges;
  for (int e = 0; e < m; ++e) {
    int from, to;
    Weight weight;
    std::cin >> from >> to >> weight;
    edges.emplace_back(from, to, weight);
  }
  const auto dist = floydWarshall(n, edges);
  for (const auto& row : dist) {
    for (int j = 0; j < n; ++j) {
      if (j) std::cout << ' ';
      if (row[j] == INF) std::cout << "INF";
      else std::cout << row[j];
    }
    std::cout << '\n';
  }
}

입력 예:

4 5
0 1 4
0 2 11
1 2 -2
2 3 3
1 3 7

출력:

0 4 2 5
INF 0 -2 1
INF INF 0 3
INF INF INF 0

0에서 3으로 갈 때 최선의 경로는 0→1→2→3이며 비용은 4-2+3=5입니다. 음수 간선은 있지만 음수 사이클은 없습니다.

복잡도와 음수 사이클

세 겹 반복문의 시간 복잡도는 O(V^3), 거리 표의 공간 복잡도는 O(V^2)입니다. 많은 정점 쌍을 모두 알아야 할 때 유용하지만, 한 시작점만 필요하다면 단일 출발점 알고리즘이 더 적합할 수 있습니다.

음수 사이클을 반복해서 돌면 경로 비용을 한없이 작게 만들 수 있습니다. 갱신이 끝난 뒤 dist[v][v] < 0이면 음수 사이클이 감지된 것입니다. 어떤 정점 v가 i에서 도달 가능하고 v에서 j로도 갈 수 있다면 (i,j)의 최단 거리는 유한하게 정의되지 않습니다. 그 밖의 음수 사이클은 해당 쌍에 영향을 주지 않습니다. 영향을 받지 않는 쌍의 유한 거리는 계산할 수 있지만, 영향을 받는 값을 유한한 최단 거리로 보고해서는 안 됩니다.

핵심: 중간 정점 반복을 가장 바깥에 두고, 도달 불가 구간은 더하기 전에 건너뛰며, 음수 사이클의 영향은 정점 쌍별로 판단합니다.