플로이드-워셜 알고리즘 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

플로이드-워셜이 해결하는 문제

한 출발점이 아니라 모든 장소 쌍 사이의 거리가 필요할 때가 있습니다. 모든 도시 간 이동 시간표, 모든 서버 쌍 사이의 지연 시간, 의존성 그래프의 전체 도달 가능성이 그 예입니다. 플로이드-워셜은 아주 짧은 동적 계획법 알고리즘으로 이 모든 쌍 최단 경로 문제를 풉니다.

로버트 플로이드(Robert Floyd)가 1962년에 발표했으며("Algorithm 97: Shortest path"), 같은 해 스티븐 워셜(Stephen Warshall)이 발표한 추이적 폐쇄(transitive closure) 알고리즘을 토대로 합니다.

핵심 아이디어

노드에 0부터 V − 1까지 번호를 매깁니다. 노드 k까지 처리하고 나면 dist[i][j]는 중간 경유지로 노드 0부터 k까지만 사용하는 i에서 j까지의 최단 경로입니다. 중간 노드 k를 하나 더 허용하면 선택지는 둘입니다. k를 피하는 기존 최선의 경로, 또는 k 이전의 노드만 쓰는 두 최선 경로를 이은 i → k → j 경로입니다.

1. 행렬을 채웁니다. 대각선은 0, 간선이 있는 곳은 간선 가중치, 나머지는 무한대입니다.
2. k = 0부터 V − 1까지, 모든 쌍 (i, j)에 대해 dist[i][k] + dist[k][j] < dist[i][j]이면 갱신합니다.
3. 마지막 k까지 끝나면 행렬에 모든 최단 거리가 들어 있습니다. 대각선에 음수 값이 있으면 음수 사이클이 있다는 뜻입니다.

반복문의 순서가 중요합니다. k가 가장 바깥쪽 반복문이어야 합니다.

단계별 예제

노드 4개와 간선 0→1 (3), 0→3 (7), 1→0 (8), 1→2 (2), 2→0 (5), 2→3 (1), 3→0 (2)로 이루어진 방향 그래프입니다. 초기 행렬은 다음과 같습니다(행 = 출발, 열 = 도착).

1. k = 0: 경로가 노드 0을 거칠 수 있습니다. 1→3은 8 + 7 = 15, 2→1은 5 + 3 = 8, 3→1은 2 + 3 = 5가 됩니다.
2. k = 1: 노드 1을 거칩니다. 0→2는 3 + 2 = 5, 3→2는 5 + 2 = 7이 됩니다.
3. k = 2: 노드 2를 거칩니다. 0→3은 7에서 5 + 1 = 6으로, 1→3은 15에서 2 + 1 = 3으로, 1→0은 8에서 2 + 5 = 7로 개선됩니다.
4. k = 3: 노드 3을 거칩니다. 1→0은 7에서 3 + 2 = 5로, 2→0은 5에서 1 + 2 = 3으로, 2→1은 8에서 1 + 5 = 6으로 개선됩니다.

최종 행렬의 각 행: 0 → [0, 3, 5, 6], 1 → [5, 0, 2, 3], 2 → [3, 6, 0, 1], 3 → [2, 5, 7, 0].

파이썬 구현

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

nxt 행렬은 i에서 j로 가는 최선 경로의 첫 번째 단계를 저장하며, 이것만으로 어떤 경로든 복원할 수 있습니다.

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

노드가 많고 파이썬에서 속도가 필요하다면 같은 3중 반복문을 k마다 한 번의 벡터화된 갱신으로 NumPy로 쓸 수 있습니다. d = np.minimum(d, d[:, k, None] + d[None, k, :]).

시간 복잡도와 공간 복잡도

가중치가 음수가 아닌 희소 그래프에서는 모든 노드에서 다익스트라를 실행하면 O(V × (V + E) log V)가 들며, E가 V²보다 훨씬 작다면 O(V³)보다 빠릅니다.

변형과 흔한 실수

• 음수 사이클: 반복문이 끝난 뒤 어떤 i에 대해 dist[i][i] < 0이면 노드 i가 음수 사이클 위에 있으며, 그 노드를 지나는 최단 경로는 정의되지 않습니다.
• 추이적 폐쇄(워셜): 불리언 값을 사용하고 min/plus를 or/and로 바꿉니다. reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
• 미니맥스와 맥시민 경로: +를 max(또는 min)로 바꾸면, 예를 들어 가장 큰 간선이 최대한 작은 경로를 찾을 수 있습니다.
• 무한대 대신 큰 유한 수를 쓰는 것은 그 둘의 합이 오버플로하지 않는다고 확신할 때만 하세요. 파이썬에서는 float("inf")가 안전한 선택입니다.
• 대각선은 0으로 초기화하고, 평행 간선이 있으면 가장 작은 가중치만 남기세요.

언제 쓰는지와 실제 활용

• 나중에 조회할 수 있도록 모든 역, 창고, 도시 사이의 거리 표를 미리 계산하기.
• 작은 네트워크의 근접 중심성이나 지름 같은 그래프 분석.
• 코딩 인터뷰 문제: 거리 임계값 이내 이웃이 가장 적은 도시 찾기, 나눗셈 계산하기(비율을 경로의 곱으로), 선수 과목을 추이적 폐쇄로 표현하기.