CS학습2026년 8월 26일

Floyd-Warshall: 모든 쌍 최단 경로를 동적 계획법으로 구하기

Floyd-Warshall은 그래프 내 모든 정점 쌍 사이의 최단 경로를 O(V³) 시간에 계산하는 동적 계획법(dynamic programming) 알고리즘이다. 음수 가중치 간선이 있어도 동작하며, 중간 경유지를 하나씩 늘려가며 최단 거리를 갱신하는 방식이 핵심이다. 다익스트라(Dijkstra)를 정점마다 반복 실행하는 것보다 구현이 단순해 밀집 그래프

송민성4분 읽기

1. 개념

Floyd-Warshall은 가중치가 있는 방향 그래프에서 모든 정점 쌍 사이의 최단 경로를 구하는 알고리즘이다. 단일 출발점 최단 경로를 구하는 다익스트라나 벨만-포드(Bellman-Ford)와 달리, 한 번의 실행으로 (V × V) 크기의 최단 거리 행렬 전체를 채운다.

핵심 아이디어는 "정점 k를 경유해도 되는가"라는 질문을 k = 1부터 V까지 순서대로 확장하면서, i에서 j로 가는 최단 거리를 갱신하는 것이다.

2. 왜 사용하는가

그래프의 모든 정점 쌍에 대한 최단 거리가 필요할 때, 다익스트라를 V번 반복하는 것보다 코드가 단순하다.
음수 가중치 간선을 허용한다 (단, 음수 사이클은 허용하지 않는다).
정점 수가 적거나 중간(수백 개 이하)인 밀집 그래프에서 실용적이다.
그래프의 이행적 폐쇄(transitive closure), 즉 "i에서 j로 도달 가능한가"를 구하는 데도 변형해서 쓸 수 있다.

3. 동작 원리

dist[i][j]를 정점 i에서 j까지의 최단 거리라고 하자. 초기값은 간선이 있으면 그 가중치, 없으면 무한대(∞), 자기 자신은 0이다.

k = 1부터 V까지 반복하면서 다음 점화식을 적용한다.

text

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

이 식은 "i에서 j로 가는 기존 경로"와 "i에서 k를 거쳐 j로 가는 경로" 중 더 짧은 쪽을 선택한다는 뜻이다. k를 바깥쪽 루프에 두는 이유는, k번째 반복이 끝난 시점에 dist[i][j]가 "1부터 k까지의 정점만 중간 경유지로 사용했을 때의 최단 거리"라는 불변식(invariant)을 유지하기 위해서다. 이 불변식 덕분에 k를 하나씩 늘려갈 때마다 이전 단계의 결과를 그대로 재사용할 수 있다.

음수 사이클이 존재하면 dist[i][i]가 음수가 되는데, 이를 통해 음수 사이클 존재 여부를 판별할 수 있다.

4. 코드 예제

python

import math

def floyd_warshall(n: int, edges: list[tuple[int, int, float]]) -> list[list[float]]:
    """
    n: 정점 개수 (0번부터 n-1번까지)
    edges: (출발, 도착, 가중치) 튜플의 리스트
    반환값: dist[i][j] = i에서 j까지의 최단 거리
    """
    INF = math.inf
    dist = [[INF] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # 중복 간선 대비 min 처리

    for k in range(n):
        for i in range(n):
            # dist[i][k]가 INF면 i->k->j 경로는 의미 없으므로 건너뛴다
            if dist[i][k] == INF:
                continue
            for j in range(n):
                new_dist = dist[i][k] + dist[k][j]
                if new_dist < dist[i][j]:
                    dist[i][j] = new_dist

    return dist


def has_negative_cycle(dist: list[list[float]]) -> bool:
    return any(dist[i][i] < 0 for i in range(len(dist)))


if __name__ == "__main__":
    # 정점 0,1,2,3 / 간선: (출발, 도착, 가중치)
    n = 4
    edges = [
        (0, 1, 5),
        (0, 3, 10),
        (1, 2, 3),
        (2, 3, 1),
    ]

    dist = floyd_warshall(n, edges)

    for row in dist:
        print(row)
    # [0, 5, 8, 9]
    # [inf, 0, 3, 4]
    # [inf, inf, 0, 1]
    # [inf, inf, inf, 0]

    print("음수 사이클 존재:", has_negative_cycle(dist))

경로 자체를 복원하려면 next_hop[i][j] 배열을 추가로 관리한다.

python

def floyd_warshall_with_path(n: int, edges: list[tuple[int, int, float]]):
    INF = math.inf
    dist = [[INF] * n for _ in range(n)]
    next_hop = [[None] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0
        next_hop[i][i] = i

    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            next_hop[u][v] = v

    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next_hop[i][j] = next_hop[i][k]

    return dist, next_hop


def reconstruct_path(next_hop, u: int, v: int) -> list[int]:
    if next_hop[u][v] is None:
        return []  # 경로 없음
    path = [u]
    while u != v:
        u = next_hop[u][v]
        path.append(u)
    return path

5. 시간 복잡도 또는 성능 특성

시간 복잡도: O(V³) — 삼중 루프가 정점 수만큼 정확히 반복된다.
공간 복잡도: O(V²) — 거리 행렬을 저장해야 한다.
정점 수가 500~1000개 정도까지는 실용적으로 동작하지만, 그 이상으로 커지면 V³ 연산량이 급격히 늘어나 비효율적이다. 예를 들어 V=1000이면 10억 번 연산에 근접한다.
다익스트라를 모든 정점에서 V번 실행하는 방식은 O(V × (V+E)logV)로, 그래프가 희소(edge 수가 적음)할 때는 이 방식이 더 빠르지만, 그래프가 밀집(dense)되어 있으면 Floyd-Warshall이 구현 단순성 면에서 유리하다.

6. 실무 사용 사례

네트워크 라우팅에서 모든 노드 쌍 간 최단 경로 테이블을 미리 계산해둘 때.
게임 맵에서 소수의 주요 지점(웨이포인트) 간 최단 거리를 미리 구해 캐싱해두는 경우.
그래프의 지름(diameter, 모든 쌍 최단 거리 중 최댓값)을 구할 때.
이행적 폐쇄를 구해 "어떤 두 노드가 서로 연결 가능한가"를 O(1)에 조회하는 전처리 단계.

7. 주의할 점

정점 수가 수천 개를 넘어가면 O(V³)와 O(V²) 메모리 때문에 비현실적이다. 이런 경우 다익스트라를 V번 돌리는 방식이나 존슨 알고리즘(Johnson's algorithm)을 고려한다.
음수 사이클이 있는 그래프에 그대로 적용하면 최단 거리가 무한히 작아지는 문제가 생긴다. 알고리즘 실행 후 dist[i][i] < 0인지 반드시 검사해야 한다.
반복문 순서(k가 가장 바깥쪽)를 바꾸면 불변식이 깨져서 잘못된 결과가 나온다. i, j, k 순서를 임의로 바꾸면 안 된다.
dist[i][k]가 무한대일 때 오버플로우나 불필요한 연산을 막기 위해 조건문으로 건너뛰는 최적화가 실무에서 중요하다.

8. 핵심 정리

Floyd-Warshall은 "k번째 정점까지만 경유지로 허용했을 때의 최단 거리"라는 불변식을 유지하며 k를 하나씩 늘려가는 동적 계획법이다. O(V³) 시간과 O(V²) 공간으로 모든 정점 쌍의 최단 거리를 한 번에 구하며, 음수 가중치도 처리하지만 음수 사이클은 별도로 검사해야 한다. 구현이 단순하고 정점 수가 많지 않은 밀집 그래프에 적합하다.