Floyd-Warshall — 모든 쌍 최단 경로와 경유지 사고법

모든 도시 쌍 사이의 최단 거리를 한 번에 구하고 싶습니다. 각 도시에서 Dijkstra를 돌려야 할까요? 더 단순한 방법이 있습니다.

개념 정의

Floyd-Warshall 알고리즘은 모든 정점 쌍 간의 최단 경로 를 O(V³)에 구하는 알고리즘입니다. 3중 for문 하나로 동작하며, 음수 간선도 처리할 수 있습니다.

왜 필요한가

상황	적합한 알고리즘
단일 출발점, 양수 간선	Dijkstra
단일 출발점, 음수 간선	Bellman-Ford
모든 쌍 , 소규모(V ≤ 500)	Floyd-Warshall
모든 쌍, 대규모, 양수 간선	Dijkstra V번

V가 작은 그래프(500 이하)에서 모든 쌍 최단 경로가 필요하면, Floyd-Warshall이 가장 단순하고 효율적입니다.

경유지 사고법

Floyd-Warshall의 핵심 아이디어는 ** 경유 노드를 하나씩 추가 **하는 것입니다.

PLAINTEXT

dp[k][i][j] = 노드 {0, 1, ..., k}만을 경유지로 사용할 때
              i에서 j까지의 최단 거리

점화식:
dp[k][i][j] = min(
    dp[k-1][i][j],           // k를 경유하지 않는 경우
    dp[k-1][i][k] + dp[k-1][k][j]  // k를 경유하는 경우
)

k = 0일 때는 경유지 없이 직접 간선만 사용. k가 증가할수록 더 많은 경유지를 고려합니다.

구현

3차원 배열은 필요 없습니다. k를 외부 루프로 순회하면 2차원으로 충분합니다.

JAVA

public static int[][] floydWarshall(int[][] graph) {
    int n = graph.length;
    int INF = Integer.MAX_VALUE / 2; // 오버플로우 방지

    // 초기화: 직접 간선 또는 무한대
    int[][] dist = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j]; // graph[i][j] = 간선 가중치 또는 INF
        }
        dist[i][i] = 0; // 자기 자신까지의 거리는 0
    }

    // 경유 노드 k를 하나씩 추가
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    return dist;
}

k가 반드시 가장 바깥 루프여야 합니다. 순서를 바꾸면 올바른 결과가 나오지 않습니다.

경로 추적

최단 거리뿐만 아니라 실제 경로도 구할 수 있습니다.

JAVA

static int[][] next; // next[i][j] = i에서 j로 갈 때 다음에 방문할 노드

public static void floydWithPath(int[][] graph) {
    int n = graph.length;
    int[][] dist = new int[n][n];
    next = new int[n][n];

    // 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != INF && i != j) {
                next[i][j] = j; // 직접 이동
            } else {
                next[i][j] = -1;
            }
        }
    }

    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (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를 경유하므로 다음 노드는 i→k의 다음 노드
                }
            }
        }
    }
}

// 경로 복원
public static List<Integer> getPath(int start, int end) {
    if (next[start][end] == -1) return List.of(); // 경로 없음

    List<Integer> path = new ArrayList<>();
    path.add(start);
    int curr = start;
    while (curr != end) {
        curr = next[curr][end];
        path.add(curr);
    }
    return path;
}

음수 사이클 탐지

알고리즘 수행 후 dist[i][i] < 0인 노드가 있으면, 그 노드를 포함하는 음수 사이클이 존재합니다.

JAVA

public static boolean hasNegativeCycle(int[][] dist) {
    for (int i = 0; i < dist.length; i++) {
        if (dist[i][i] < 0) return true;
    }
    return false;
}

변형: 도달 가능성 (Transitive Closure)

가중치를 무시하고 "i에서 j로 갈 수 있는가?"만 구하는 변형입니다.

JAVA

public static boolean[][] transitiveClosure(boolean[][] graph) {
    int n = graph.length;
    boolean[][] reach = new boolean[n][n];

    // 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            reach[i][j] = graph[i][j];
        }
        reach[i][i] = true;
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
    return reach;
}

변형: 최대 최소 경로 (Minimax)

경로의 간선 중 최대 가중치를 최소화하는 문제입니다. 화물 운송에서 "가장 좁은 도로"를 최대화하는 것과 같습니다.

JAVA

// dist[i][j] = i에서 j로 가는 경로 중, 최대 간선을 최소화한 값
for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 경유지 k를 거치면 max(i→k, k→j)
            dist[i][j] = Math.min(dist[i][j],
                                   Math.max(dist[i][k], dist[k][j]));
        }
    }
}

시간 복잡도 분석

방법	시간 복잡도	공간 복잡도
Floyd-Warshall	O(V³)	O(V²)
Dijkstra V번 (힙)	O(V(V+E) log V)	O(V² + E)
Bellman-Ford V번	O(V²E)	O(V²)

V ≤ 500, 밀집 그래프에서는 Floyd-Warshall이 가장 단순합니다.

백엔드/실무에서의 연결

네트워크 라우팅

소규모 네트워크에서 모든 노드 쌍의 최단 경로를 미리 계산하여 라우팅 테이블을 구축합니다.

소셜 네트워크 분석

사용자 간의 최단 연결 거리(degrees of separation)를 모든 쌍에 대해 구할 때 사용합니다. "Six Degrees of Separation" 검증에 활용됩니다.

교통 시스템

도시 간 최단 이동 시간, 최소 비용 경로를 모든 쌍에 대해 미리 계산하여 캐시합니다. 도시 수가 제한적이면 Floyd-Warshall이 적합합니다.

게임 맵의 거리 테이블

게임에서 지역 간 최단 거리를 미리 계산하여 NPC 경로 찾기, 이동 시간 표시 등에 사용합니다.

API Gateway의 서비스 거리

MSA에서 서비스 간 호출 홉 수를 미리 계산하여, 호출 체인 최적화에 활용할 수 있습니다.

주의사항

오버플로우 방지

JAVA

// 나쁜 코드: INF + INF가 오버플로우
if (dist[i][k] + dist[k][j] < dist[i][j])

// 좋은 코드: INF 검사
int INF = Integer.MAX_VALUE / 2;
if (dist[i][k] < INF && dist[k][j] < INF &&
    dist[i][k] + dist[k][j] < dist[i][j])

k 루프 순서

k가 가장 바깥 루프여야 합니다. i, j, k 순서로 바꾸면 결과가 틀립니다.

자기 자신으로의 거리

dist[i][i] = 0으로 초기화해야 합니다. 자기 자신으로의 간선이 있는 경우를 제외하면 항상 0입니다.

주의할 점

음수 간선이 있는 그래프에서 Dijkstra를 사용하는 실수

Dijkstra는 음수 간선에서 최적해를 보장하지 않습니다. "이미 확정된 최단 거리"가 나중에 음수 간선으로 더 짧아질 수 있기 때문입니다. 음수 간선이 있으면 Bellman-Ford를 사용해야 합니다.

Bellman-Ford에서 음수 사이클 탐지를 빠뜨리는 실수

V-1번 반복 후에도 갱신이 발생하면 음수 사이클이 존재합니다. 이 체크를 빠뜨리면 무한 루프에 빠지거나 잘못된 결과를 반환합니다.

정리

특성	Floyd-Warshall
목적	모든 쌍 최단 경로
시간	O(V³)
음수 간선	처리 가능
음수 사이클	dist[i][i] < 0으로 탐지
적합한 크기	V ≤ 500
구현 난이도	매우 쉬움 (3중 for문)

기억할 포인트:

Floyd-Warshall의 핵심은 ** 경유 노드를 하나씩 추가 **하는 것입니다.
k가 반드시 가장 바깥 루프 여야 합니다.
음수 간선을 처리할 수 있고, dist[i][i] < 0으로 음수 사이클을 탐지합니다.
구현이 매우 단순하여 V가 작은 문제에서 모든 쌍 최단 경로가 필요하면 첫 번째 선택지입니다.