Floyd-Warshall 알고리즘 정리

AlgorithmGraph

Floyd-Warshall이란

모든 노드 쌍 (i, j) 사이의 최단 경로를 한 번에 구하는 알고리즘이다. 단일 출발점 최단 경로(Dijkstra, BFS)를 N번 반복하는 대신, 3중 루프 하나로 해결한다.

핵심 아이디어

“i에서 j로 갈 때, 중간에 k를 거치는 게 더 짧은가?”를 모든 k에 대해 확인한다.

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

k를 1부터 N까지 순서대로 확장하면, k번째 루프가 끝난 시점에서 dist[i][j]는 {1, 2, …, k}만을 중간 노드로 사용했을 때의 최단 거리다.

코드: 최단 거리

const int INF = 1e9;
vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));

// 자기 자신은 0
for (int i = 1; i <= n; i++) dist[i][i] = 0;

// 간선 입력
for (auto& e : edges) {
    dist[e[0]][e[1]] = e[2];  // 방향 그래프
    // dist[e[1]][e[0]] = e[2];  // 무방향이면 추가
}

// Floyd-Warshall
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] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];
        }
    }
}

변형: 전이적 폐쇄 (Transitive Closure)

최단 거리 대신 “도달 가능한가?”만 구하는 변형이다. min(+) 대신 &&를 쓴다.

vector<vector<bool>> reach(n + 1, vector<bool>(n + 1, false));

for (auto& e : edges) {
    reach[e[0]][e[1]] = true;
}

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (reach[i][k] && reach[k][j])
                reach[i][j] = true;
        }
    }
}

메모

  • k가 가장 바깥 루프
    • k를 안쪽에 놓으면 아직 확장되지 않은 중간 노드를 참조하게 되어 틀린 결과가 나온다
    • k → i → j 순서는 바꿀 수 없다
  • 음수 간선
    • Floyd-Warshall은 음수 가중치 간선을 허용한다 (Dijkstra는 불가)
    • 단, 음수 사이클이 있으면 최단 경로가 정의되지 않는다. dist[i][i] < 0인 노드가 있으면 음수 사이클 존재
  • N ≤ 500 정도까지 실용적
    • O(N³)이므로 N = 500이면 1.25억, N = 1000이면 10억으로 시간 초과 위험
    • N이 크면 각 노드에서 Dijkstra를 돌리는 게 더 빠를 수 있다
  • 적용 사례

복잡도

시간공간
Floyd-WarshallO(N³)O(N²)