algo · 13

플로이드-워셜

DP전체쌍최단경로

플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프의 모든 정점 쌍 사이의 최단 거리를 한 번에 구하는 알고리즘입니다. 다익스트라나 벨만-포드가 한 출발점에서 모든 정점까지를 구하는 것과 달리, 출발점을 고르지 않고 "어느 정점에서 어느 정점까지든" 거리를 표로 만들어 둡니다. 코드는 삼중 반복문 하나로 끝날 만큼 짧습니다.

핵심 생각은 경유지를 하나씩 허용하는 것입니다. 처음에는 직접 이어진 간선만 쓰고, 정점 1번을 거치는 경로를 허용하고, 다음에 2번까지 거치는 경로를 허용하는 식으로 늘려 갑니다. 정점 k를 새로 허용할 때 i에서 j로 가는 최단 거리는 "k를 거치지 않는 기존 거리"와 "i에서 k까지 더하기 k에서 j까지" 중 작은 쪽입니다. 이 토픽에서는 거리 행렬이 경유지마다 갱신되는 모습, 한 칸을 비교하는 순간, 경로를 복원하는 방법을 봅니다.

핵심 개념

모든 쌍 최단 경로

정점 쌍 (i, j) 전부에 대해 최단 거리를 구하는 문제(All-Pairs Shortest Path)입니다. 결과는 V × V 크기의 거리 행렬입니다.

핵심 개념

경유지 k

경로 중간에 거치는 정점입니다. k 단계가 끝나면 경유지를 정점 1번부터 k번까지만 써서 구할 수 있는 최단 거리가 행렬에 들어 있습니다.

핵심 개념

점화식

d[i][j] = min(d[i][j], d[i][k] + d[k][j])입니다. k를 거치는 쪽이 더 짧으면 그 값으로 바꿉니다. 이전 단계의 결과를 쌓아 가는 동적 계획법입니다.

핵심 개념

삼중 반복문

경유지 k, 출발지 i, 도착지 j를 모두 도는 세 겹 반복문입니다. 바깥이 반드시 경유지 k여야 점화식이 성립합니다.

핵심 개념

경로 복원

거리를 갱신할 때 next[i][j]도 함께 갱신해 두면, 거리 행렬만큼의 공간으로 모든 쌍의 실제 경로를 따라갈 수 있습니다.

핵심 개념

음수 사이클 탐지

계산 후 대각선 d[i][i]가 0보다 작은 칸이 있으면 그래프에 음수 사이클이 있다는 신호입니다. 음수 간선 자체는 허용됩니다.

시간은 O(V³)입니다 — 경유지, 출발지, 도착지 세 값이 각각 V가지이므로 간선 수와 상관없이 일정합니다. 정점 수가 크지 않아 V³ 연산을 감당할 수 있을 때 실용적입니다.

공간은 O(V²)입니다 — V × V 거리 행렬 하나입니다. 같은 행렬을 제자리에서 갱신하면 단계마다 새 행렬이 필요하지 않습니다.

제자리 갱신이 안전합니다 — 경유지 k 단계에서 k 행과 k 열은 바뀌지 않으므로(음수 사이클이 없을 때) 읽는 값이 같은 단계에서 오염되지 않습니다.

조밀한 그래프에 잘 맞습니다 — 간선이 많은 그래프에서 다익스트라를 모든 정점에서 돌리는 것보다 단순하고 비슷하거나 빠릅니다. 간선이 적은 희소 그래프에서는 다른 방법이 더 빠를 수 있습니다.

이 시각화에서 확인할 것 — "거리 행렬 갱신" 탭에서 경유지가 늘 때마다 행렬 칸이 노란색으로 갱신되는 모습을, "한 칸 계산" 탭에서 d[i][k] + d[k][j]와 기존 값을 비교하는 순간을, "경로 복원" 탭에서 next를 따라 실제 경로를 얻는 과정을 STEP으로 확인하세요.

플로이드-워셜의 배경

1962년 로버트 플로이드(Robert W. Floyd)가 ACM 통신(Communications of the ACM)에 "Algorithm 97: Shortest path"라는 짧은 글로 이 알고리즘을 실었습니다. 같은 해 스티븐 워셜(Stephen Warshall)은 "A theorem on Boolean matrices"에서 불리언 행렬의 전이적 폐쇄(transitive closure)를 구하는 방법을 발표했는데, 반복 구조가 같아서 두 이름을 붙여 부릅니다. 워셜의 방법은 거리 대신 도달 가능 여부를 다룹니다.

숫자로 확인하기

예시 그래프 — 정점 A, B, C, D 4개와 방향 간선 7개(A → B 3, A → D 7, B → A 8, B → C 2, C → A 5, C → D 1, D → A 2)입니다. 처음 거리 행렬은 직접 이어진 칸만 값이 있고 나머지는 ∞입니다.

경유지 A, B — A를 허용하면 B → D 15, C → B 8, D → B 5가 새로 생기고, B를 허용하면 A → C 5와 D → C 7이 생깁니다. 아직 닿지 못하던 칸이 채워지는 단계입니다.

경유지 C, D — C를 허용하면 A → D가 7에서 6으로, B → A가 8에서 7로, B → D가 15에서 3으로 줄어듭니다. D를 허용하면 B → A 5, C → A 3, C → B 6으로 더 줄어듭니다.

최종 행렬 — 행이 출발, 열이 도착일 때 A는 0, 3, 5, 6, B는 5, 0, 2, 3, C는 3, 6, 0, 1, D는 2, 5, 7, 0입니다. 총 11칸이 갱신되었습니다.

경로 복원 — next 행렬을 따라가면 A에서 D까지 경로는 A, B, C, D이고 간선 가중치 합이 3 + 2 + 1 = 6으로 d[A][D]와 같습니다.

코드 확인 — 파이썬과 자바 구현이 같은 그래프에서 같은 행렬을 돌려줍니다. B → D(-20) 간선을 더하면 B → D → A → B의 합이 -15인 음수 사이클이 생겨 대각선에 음수가 나타납니다.

자주 하는 오해

반복문 순서는 상관없다 — 경유지 k가 가장 바깥이어야 합니다. i, j를 바깥에 두면 "k까지 허용했을 때의 최단 거리"라는 점화식의 의미가 깨져 결과가 틀릴 수 있습니다.

음수 간선이 있으면 쓸 수 없다 — 음수 사이클이 없다면 음수 간선이 있어도 올바른 최단 거리를 구합니다. 문제가 되는 것은 음수 사이클입니다.

다익스트라를 V번 돌리는 것보다 항상 느리다 — 이진 힙 다익스트라를 모든 정점에서 돌리면 조밀한 그래프에서 O(V³ log V)라 점근적으로 플로이드-워셜이 낫고, 피보나치 힙을 쓰면 같은 O(V³)입니다. 다익스트라는 음수 간선이 없을 때만 쓸 수 있고, 희소한 그래프에서는 다익스트라 쪽이 빠를 수 있습니다.

경로까지 구하려면 공간이 크게 늘어난다 — next 행렬도 V × V이므로 공간은 여전히 O(V²)입니다. 경로를 통째로 저장하지 않고 다음 정점만 저장합니다.

INF에 아무 값이나 더해도 된다 — 정수 최댓값을 INF로 쓰면 INF에 양수를 더할 때 넘쳐 음수가 됩니다. 두 거리가 모두 INF가 아닐 때만 더합니다. 넘치지 않을 만큼 작은 INF를 쓰더라도 음수 간선이 있으면 INF 여부를 함께 검사해야 합니다.

면접에서 이렇게 물어요

면접 질문

플로이드-워셜의 점화식은?

d[i][j] = min(d[i][j], d[i][k] + d[k][j])입니다. 경유지 k를 하나씩 늘려 가며 "k를 거치는 경로가 더 짧은가"를 모든 칸에서 확인하는 동적 계획법입니다.

면접 질문

시간·공간 복잡도는?

시간은 O(V³), 공간은 O(V²)입니다. 경유지, 출발지, 도착지 세 겹 반복문과 V × V 행렬 하나가 그 이유입니다.

면접 질문

다익스트라, 벨만-포드와는 언제 구분해 쓰나요?

한 출발점에서의 거리만 필요하면 다익스트라(음수 간선이 없을 때)나 벨만-포드(음수 간선이 있을 때)를 씁니다. 모든 쌍이 필요하고 정점 수가 크지 않으면 플로이드-워셜이 간단합니다.

면접 질문

음수 사이클은 어떻게 알 수 있나요?

계산이 끝난 뒤 대각선 d[i][i]에 음수가 있으면 그래프에 음수 사이클이 있습니다. i에서 출발해 i로 돌아오는 경로의 합이 0보다 작아졌다는 뜻이고 그 경로는 음수 사이클을 포함합니다. 음수가 나온 정점이 꼭 그 사이클 위에 있는 것은 아닙니다.

실제 시스템에서는

전이적 폐쇄 — 워셜의 방법은 합과 최소 대신 논리합과 논리곱으로 "i에서 j로 갈 수 있는가"를 모든 쌍에 대해 구합니다. 간접적으로라도 이어진 항목을 모두 찾는 개념입니다.

그래프 지표 계산 — 모든 쌍의 최단 거리가 있으면 (모든 쌍이 서로 닿을 때) 그래프의 지름(가장 먼 쌍의 거리)이나 정점이 다른 정점들에 얼마나 가까운지를 재는 지표를 바로 계산할 수 있습니다.

라이브러리 — NetworkX의 floyd_warshall 함수와 SciPy의 scipy.sparse.csgraph.floyd_warshall이 이 알고리즘을 제공합니다.

함께 보면 좋은 토픽

다익스트라 — 한 출발점에서의 최단 경로를 구하는 방법을 봅니다.

벨만-포드 — 음수 간선과 음수 사이클을 다루는 최단 경로 알고리즘을 봅니다.

DP 기초 — 작은 단계의 결과를 쌓아 가는 동적 계획법을 봅니다.

그래프 — 인접 행렬과 인접 리스트 표현을 봅니다.

참고 자료

논문 — Floyd, R. W., "Algorithm 97: Shortest path", Communications of the ACM 5(6), 1962

논문 — Warshall, S., "A theorem on Boolean matrices", Journal of the ACM 9(1), 1962

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 3rd ed., Section 25.2 The Floyd-Warshall algorithm

공식 문서 — NetworkX floyd_warshall

공식 문서 — SciPy csgraph.floyd_warshall

Python — 플로이드-워셜과 경로 복원

INF = float('inf')

def floyd_warshall(n, edges):
    dist = [[INF] * n for _ in range(n)]
    nxt = [[None] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v                           # 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]       # k 쪽으로 먼저 간다
    return dist, nxt

def path(nxt, i, j):
    p = [i]
    while i != j:
        i = nxt[i][j]
        p.append(i)
    return p

# A=0, B=1, C=2, D=3 · (출발, 도착, 가중치)
E = [(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, E)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]
print(path(nxt, 0, 3), dist[0][3])       # [0, 1, 2, 3] 6

플로이드-워셜은 거리 행렬 dist에서 시작해, 경유지 k를 하나씩 허용하며 모든 칸 (i, j)에서 dist[i][j]와 dist[i][k] + dist[k][j] 중 작은 값을 고릅니다. 이 점화식 하나가 알고리즘의 전부이고, 경유지 k, 출발지 i, 도착지 j의 삼중 반복이므로 O(V³)입니다. 이 예시 그래프에서는 A → D가 직접 7이지만 A → B → C → D로 3 + 2 + 1 = 6이 되어 dist[0][3]이 6으로 바뀝니다. 경유지 k를 가장 바깥 반복문에 두는 것이 중요합니다. 바깥 반복이 k여야 "경유지를 k까지 허용했을 때의 최단 거리"라는 뜻이 유지되고, 순서를 바꾸면 결과가 틀릴 수 있습니다. dist를 갱신할 때 nxt[i][j]도 nxt[i][k]로 바꿔 두면, path 함수가 nxt를 따라가며 실제 경로를 복원합니다. A에서 D까지는 [0, 1, 2, 3], 곧 A → B → C → D입니다. 시각화의 거리 행렬 갱신 탭과 경로 복원 탭이 보여 주는 과정과 같습니다.

Python — 음수 사이클 탐지

neg = E + [(1, 3, -20)]                      # B → D(-20) 추가
d2, _ = floyd_warshall(4, neg)
print([d2[i][i] for i in range(4)])      # [-15, -15, -5, -30]
print(any(d2[i][i] < 0 for i in range(4)))     # True

플로이드-워셜은 음수 가중치 간선이 있어도 음수 사이클만 없으면 올바르게 동작합니다. 음수 사이클이 있는지는 계산이 끝난 뒤 대각선 dist[i][i]를 보면 알 수 있습니다. 정점에서 출발해 자기 자신으로 돌아오는 경로의 합이 0보다 작아졌다면, 그 경로가 음수 사이클을 포함하므로 그래프에 음수 사이클이 있다는 뜻입니다. 음수가 나온 정점이 꼭 그 사이클 위에 있는 것은 아닙니다. 위에서는 B → D(-20) 간선을 더해 B → D → A → B의 합이 -20 + 2 + 3 = -15인 음수 사이클을 만들었고, 대각선에 음수가 나타납니다. 음수 사이클이 있으면 최단 거리가 정의되지 않으므로 이때의 거리 값은 쓰지 않습니다.

Java — 플로이드-워셜

static final int INF = Integer.MAX_VALUE;

static int[][] floydWarshall(int n, int[][] edges) {
    int[][] d = new int[n][n];
    for (int[] row : d) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int[] e : edges) d[e[0]][e[1]] = e[2];
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] != INF && d[k][j] != INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
    return d;
}

// 같은 그래프의 결과
// [0, 3, 5, 6]  [5, 0, 2, 3]  [3, 6, 0, 1]  [2, 5, 7, 0]

자바 버전도 같은 삼중 반복문입니다. INF를 Integer.MAX_VALUE로 두었기 때문에 두 거리를 더하기 전에 둘 다 INF가 아닌지 검사해야 합니다. 검사하지 않으면 INF에 양수를 더할 때 값이 넘쳐 음수가 되어 닿지 못하는 쌍이 가까운 것처럼 갱신됩니다. 정점 수 V에 대해 시간은 O(V³), 거리 행렬 저장에 공간은 O(V²)입니다. 모든 쌍을 한꺼번에 구해야 하고 정점 수가 크지 않을 때 간단해서 많이 씁니다. 한 출발점에서만 구한다면 다익스트라나 벨만-포드가 알맞습니다.

플로이드-워셜 알고리즘이 구하는 것은?

"All-Pairs Shortest Path" 문제를 풉니다.

플로이드-워셜은 그래프의 모든 정점 쌍(i, j)에 대해 최단 거리를 한 번에 구하는 알고리즘입니다.

플로이드-워셜 알고리즘의 시간 복잡도는? (V: 정점 수)

경유지, 출발지, 도착지에 대한 삼중 반복문입니다.

경유지 k, 출발지 i, 도착지 j의 세 겹 반복문으로 모든 조합을 확인하므로 O(V^3)입니다. 정점 수가 크지 않을 때 실용적입니다.

플로이드-워셜의 점화식으로 알맞은 것은? (k를 경유지로 고려할 때)

i에서 j로 갈 때 k를 거치는 경로가 더 짧은지 비교합니다.

경유지 k를 추가로 허용했을 때, i에서 j로 바로 가는 기존 거리와 i→k→j로 가는 거리 중 더 짧은 쪽을 택합니다. k를 하나씩 늘려 가며 갱신하는 DP 방식입니다.