플로이드-워셜 알고리즘

수치해석 소프트웨어 마지막 수정: 2026-08-26 04:44:22

1. 개요[편집]

플로이드-워셜 알고리즘 Floyd–Warshall algorithm
기원	Roy(1959) · Warshall(1962) · Floyd(1962)
푸는 문제	모든 쌍 최단경로 (APSP)
음의 가중치	허용 — 음수 사이클은 대각선으로 검출
시간 · 공간	$\Theta(V^3)$ · $\Theta(V^2)$ (입력 크기와 무관하게 고정)
구조	중간 정점 집합에 대한 동적 계획법
일반화	닫힌 반환 위의 삼중 루프 — 이행 폐포 · 병목경로 · 정규식
코드 길이	중첩 for문 세 줄

플로이드-워셜 알고리즘은 «경유해도 되는 중간 정점의 집합»을 하나씩 늘려 가며 모든 정점 쌍 사이의 최단거리를 갱신하는 $\Theta(V^3)$ 동적 계획법이다. 음수 간선을 허용하고, 음수 사이클이 있으면 그것도 검출하며, 구현은 삼중 for문 다섯 줄이 전부다.

for k in 1..V:
  for i in 1..V:
    for j in 1..V:
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

알고리즘 하나가 이렇게 짧으면서 이렇게 많은 것을 하는 경우는 드물다. 실제로 이 다섯 줄은 최단경로만 푸는 것이 아니라 이행 폐포·병목 경로·정규 표현식 합성을 전부 같은 골격으로 처리하는데, 그 이유는 아래 반환(semiring) 절에서 다룬다. 코드가 짧다는 건 우연이 아니라 이 알고리즘이 사실 $(\min,+)$ 대수 위의 가우스 소거이기 때문이다.

같은 APSP 문제를 푸는 존슨 알고리즘과는 역할이 갈린다. 희소 그래프면 존슨, 조밀하거나 $V$ 가 작거나 코드 단순함이 중요하면 플로이드-워셜이다. 이 문서는 후자가 왜 그렇게 잘 버티는지 — 점근 복잡도가 나쁜데도 실전에서 자주 이기는 이유 — 까지 본다.

2. 점화식과 k 루프[편집]

$d^{(k)}[i][j]$ 를 중간 정점을 $\{1,\dots,k\}$ 안에서만 골라 쓸 때 $i \to j$ 최단거리로 정의한다. 여기서 “중간”은 양 끝점 $i, j$ 를 제외한 정점을 뜻한다. 그러면 $k$ 를 하나 더 허용했을 때 답은 두 가지뿐이다.

$k$ 를 안 쓴다 → $d^{(k-1)}[i][j]$ 그대로.
$k$ 를 쓴다 → 경로는 반드시 $i \leadsto k \leadsto j$ 로 쪼개지고, 음수 사이클이 없으면 최단경로는 단순 경로라 $k$ 를 두 번 지나지 않으므로 앞뒤 조각 각각이 $\{1,\dots,k-1\}$ 만 경유한다.

d^{(k)}[i][j] \;=\; \min\Big(\,d^{(k-1)}[i][j],\;\; d^{(k-1)}[i][k] + d^{(k-1)}[k][j]\,\Big)

초기값은 $d^{(0)}[i][j] = w(i,j)$ (간선 없으면 $\infty$ , $i=j$ 면 0)이고 답은 $d^{(V)}$ 다.

경유점 집합을 {0,…,k−1}에서 {0,…,k}로 한 겹씩 넓히며 D[i][j] ← min(D[i][j], D[i][k]+D[k][j]) 를 제자리에서 돌린다. 금색 테두리의 k 행·k 열이 이번 겹의 유일한 재료이고, 번쩍이는 칸이 실제로 짧아진 거리다 — 기본값 N = 20 에서 삼중 루프 8000회 중 값이 줄어드는 칸은 667개(8.3 %)뿐이다. 음수 간선을 섞어도 각 정점 벨만-포드와 2.8e−14 안에서 일치하고, 슬라이더 끝값의 음수 사이클 주입에서는 대각 D[i][i] 가 음수로 내려가 검출된다.

여기서 $k$ 가 바깥 루프여야 하는 이유가 나온다. $d^{(k)}$ 를 계산하려면 $d^{(k-1)}$ 이 모든 $(i,j)$ 에 대해 완성돼 있어야 한다. $k$ 를 안쪽으로 내리면 어떤 쌍은 $k$ 까지 반영된 값, 어떤 쌍은 $k-1$ 까지만 반영된 값이 섞여 점화식의 전제가 깨진다. 루프 순서를 i, j, k 로 바꾸면 컴파일도 되고 실행도 되고 작은 예제에서는 답까지 맞는데, 특정 그래프에서 조용히 틀린 답을 뱉는다.¹ 플로이드-워셜 버그의 9할이 이것이고, 자기 코드를 의심하는 사람이 가장 먼저 볼 자리다.

DP의 축이 무엇인지도 짚고 갈 만하다. 벨만-포드 알고리즘의 DP 축은 경로에 쓴 간선 개수이고 플로이드-워셜의 축은 경유 가능한 정점 집합이다. 전자는 라운드를 $V-1$ 번 돌려 “간선 $i$ 개 이하”를 넓혀 가고 후자는 “정점 $k$ 이하”를 넓혀 간다. 같은 벨만 방정식을 다른 방향으로 접은 셈이다.

3. 배열 하나로 in-place가 되는 이유[편집]

교과서 점화식은 $d^{(k)}$ 와 $d^{(k-1)}$ 을 구분하니 3차원 배열 $V^3$ 개가 필요해 보인다. 그런데 실제 구현은 2차원 배열 하나를 그냥 덮어쓴다. 정당화는 한 줄이다.

$k$ 번째 패스 동안 $k$ 행과 $k$ 열은 변하지 않는다.

d^{(k)}[i][k] = \min\big(d^{(k-1)}[i][k],\; d^{(k-1)}[i][k] + \underbrace{d^{(k-1)}[k][k]}_{\ \ge\ 0}\big) = d^{(k-1)}[i][k]

$d[k][k] \ge 0$ 은 음수 사이클이 없다는 가정에서 나온다. 열 쪽도 대칭으로 같다. 즉 패스 $k$ 에서 읽는 값 $d[i][k]$ 와 $d[k][j]$ 는 덮어쓰기와 무관하게 항상 $d^{(k-1)}$ 판이므로, 새 배열을 따로 둘 필요가 없다. 공간이 $\Theta(V^3)$ 에서 $\Theta(V^2)$ 로 내려가는 것이 이 관찰 하나 덕이고, 그 덕에 알고리즘이 실용성을 얻는다.

가정이 깨지면(음수 사이클) 값들이 서로 뒤섞이며 임의로 작아진다. 하지만 어차피 그 경우 최단경로 자체가 정의되지 않으므로 값의 의미를 따질 필요가 없고, 아래의 검출만 유효하면 된다.

4. 경로 복원과 음수 사이클[편집]

경로 복원. 거리만으로는 경로를 못 되돌리므로 행렬을 하나 더 둔다. 두 관습이 있다.

후속자 행렬 nxt[i][j] — $i$ 에서 $j$ 로 갈 때 첫 걸음. 초기값은 간선이 있으면 $j$ , 갱신될 때 nxt[i][j] = nxt[i][k]. 복원은 $i$ 에서 출발해 nxt를 따라가면 끝이라 가장 간단하다.
선행자 행렬 pre[i][j] — 갱신될 때 pre[i][j] = pre[k][j]. 뒤에서부터 거슬러 올라간다.

어느 쪽이든 메모리가 $\Theta(V^2)$ 하나 더 늘 뿐이고, 복원 비용은 경로 길이에 비례한다.

음수 사이클 검출. 알고리즘을 끝까지 돌린 뒤 대각선을 본다.

\exists\, i:\ d[i][i] < 0 \quad\Longleftrightarrow\quad i\ \text{를 지나는 음수 사이클이 존재}

정직하고 싸다. 한 걸음 더 나가 어떤 쌍이 오염됐는지까지 표시하려면 후처리를 한 번 더 돌린다 — $d[k][k] < 0$ 인 $k$ 에 대해 $d[i][k]$ 와 $d[k][j]$ 가 모두 유한한 모든 $(i,j)$ 의 거리를 $-\infty$ 로 찍는다. 음수 사이클을 경유할 수 있는 쌍만 답이 없는 것이고 나머지 쌍의 답은 여전히 멀쩡하다는 점이, 통째로 실패를 선언하는 벨만-포드 알고리즘 단일 출발점 판과 다른 점이다.

주의할 구현 함정 하나 — INF를 큰 정수(예: $10^9$ )로 흉내 냈다면 d[i][k] + d[k][j]가 $2\times10^9$ 로 오버플로한다. 갱신 전에 두 값이 모두 INF 미만인지 확인하거나, INF를 자료형 최댓값의 1/4 이하로 잡는다.

5. 반환 위에서 — 같은 삼중 루프의 여러 얼굴[편집]

내부 연산 min과 +를 다른 한 쌍 $(\oplus, \otimes)$ 으로 바꿔도 삼중 루프의 정당성 논증이 그대로 간다. 필요한 것은 $\otimes$ 가 $\oplus$ 위로 분배되고 각각에 항등원이 있다는 것, 즉 닫힌 반환(closed semiring) 구조뿐이다.

⊕ (경로들 사이)	⊗ (간선 이어붙이기)	d[i][j]의 뜻	부르는 이름
min	+	최단거리	플로이드-워셜
or	and	도달 가능 여부	워셜의 이행 폐포
max	min	경로의 최소 간선 용량 최대화	병목 경로 (widest path)
min	max	경로의 최대 간선 최소화	미니맥스 경로
max	×	가장 확률 높은 경로	최대신뢰도 경로
합집합	이어붙이기	i→j 경로들의 언어	클레이니 알고리즘

역사가 이 표를 그대로 따라간다. 워셜(1962)이 불 행렬의 이행 폐포로 이 삼중 루프를 발표했고, 같은 해 같은 학회지에 플로이드가 최단경로판을 실었다. 사실 프랑스의 로이가 1959년에 이미 같은 것을 냈다는 이유로 로이-플로이드-워셜이라 부르는 문헌도 있다.²

병목 경로는 시뮬레이션 쪽에서 의외로 자주 나온다. 네트워크의 최대 처리량 경로, 지형에서 “가장 낮은 고개를 넘는 길”, 이미지 분할에서 두 픽셀을 잇는 최소 장벽 경로가 전부 $(\max,\min)$ 반환이다. 최소신장트리의 경로가 곧 병목 경로라는 사실 때문에 실제로는 최소 신장 트리로 더 싸게 푸는 경우가 많지만, “삼중 루프의 min을 max로 고치기만 하면 된다”는 접근성은 여전히 매력적이다.

클레이니 알고리즘은 유한 오토마타를 정규 표현식으로 변환하는 표준 절차다. 상태 $i$ 에서 $j$ 로 가는 문자열의 집합을 정규식으로 들고, 상태 $k$ 를 경유하는 경우를 흡수하며 $k$ 를 하나씩 제거해 나간다. 여기서는 $\otimes$ 에 항등원 말고 클레이니 스타 $R^*$ 가 필요한데, 상태 $k$ 를 여러 번 도는 루프를 표현해야 하기 때문이다. 일반 반환 위의 정식 점화식이

d^{(k)}[i][j] \;=\; d^{(k-1)}[i][j] \;\oplus\; d^{(k-1)}[i][k]\otimes \big(d^{(k-1)}[k][k]\big)^{*}\otimes d^{(k-1)}[k][j]

인 것이 이 때문이고, $(\min,+)$ 에서는 음수 사이클이 없다는 가정 덕에 $\big(d[k][k]\big)^{*} = 0$ (곱셈 항등원)이 되어 그 항이 통째로 사라진다. 우리가 아는 다섯 줄짜리 코드는 일반형의 특수화인 셈이다. 유한 상태 기계 쪽에서 이 알고리즘을 “상태 제거법”이라 부른다.

6. Θ(V³)을 실제로 밀어붙이기[편집]

점근 복잡도가 나쁘다는 평판과 달리, 플로이드-워셜은 하드웨어를 가장 잘 먹는 그래프 알고리즘 축에 든다. 이유가 셋이다.

자료구조가 없다. 힙도 큐도 포인터도 없이 밀집 2차원 배열 하나뿐이라 명령어당 오버헤드가 사실상 0이다.
분기가 없다. min은 조건부 이동 명령 하나로 컴파일되어 분기 예측 실패가 없고, SIMD로 폭넓게 벡터화된다. 내부 $j$ 루프는 d[i][*]와 d[k][*]를 연속 접근하는 완벽한 벡터 연산이다.
$k$ 고정 시 $V^2$ 개 갱신이 전부 독립이다. 층 안에서는 마음껏 병렬화된다.

발목을 잡는 것은 메모리 대역폭이다. $V$ 가 커지면 행 하나가 캐시에 안 들어가 매 $k$ 마다 $V^2$ 짜리 배열 전체를 두 번씩 훑게 된다. 표준 처방이 블록(타일) 플로이드-워셜이다. 행렬을 $B\times B$ 타일로 자르고 각 $k$ -블록마다 세 단계로 진행한다 — 대각 타일을 먼저 자기 자신으로 갱신하고, 그 대각 타일이 속한 행·열의 타일들을 갱신하고, 마지막으로 나머지 타일들을 갱신한다. 각 단계가 타일 두세 개만 만지므로 캐시 안에서 끝나고, 구조가 밀집 행렬 곱셈의 블록 알고리즘과 사실상 동일해진다.³

그래서 GPU 컴퓨팅 이식이 유난히 잘 된다. 블록 세 단계를 커널 세 개로 짜고 타일을 공유 메모리에 올리면 $V =$ 수천에서 수만까지 실용 시간에 들어온다. 진짜 한계는 시간이 아니라 공간이다 — $\Theta(V^2)$ 이므로 $V = 10^5$ 이면 4바이트 정수로도 40 GB다. “플로이드-워셜은 $V$ 가 수천까지”라는 실무 감각의 근거는 $V^3$ 이 아니라 $V^2$ 쪽인 경우가 많다.

이행 폐포 전용이라면 한 발 더 나간다. 불 행렬의 한 행을 비트로 채우면 or 갱신이 워드 단위로 처리되어 $\Theta(V^3/w)$ 가 된다( $w$ 는 워드 폭). 64비트 워드에 SIMD까지 얹으면 상수가 수백 배 줄어, $V = 10^4$ 짜리 폐포가 노트북에서 몇 초다.

7. 언제 쓰나[편집]

$V$ 가 작고 $E$ 가 많다. $V \lesssim 500$ 이면 고민할 이유가 없다. 조밀 그래프에서는 존슨 알고리즘의 $O(VE\log V)$ 가 $O(V^3\log V)$ 라 오히려 진다.
모든 쌍이 정말 필요하다. 라우팅 테이블 전체, 게임의 사전계산 거리 행렬, 그래프 지름·중심성 지표, 경로 계획에서 웨이포인트 사이 거리표 등. 몇 쌍만 필요하면 그 쌍마다 다익스트라를 돌리는 게 낫다.
음수 간선이 있는데 코드가 짧아야 한다. 알고리즘 대회에서 ” $V \le 300$ , 가중치에 음수 가능, 모든 쌍”이면 사실상 지시문이다.
반환을 갈아 끼우고 싶다. 도달성·병목·신뢰도를 한 코드로 처리하려면 이쪽이 압도적으로 편하다. 존슨은 $(\min,+)$ 에 묶여 있다.

반대로 쓰면 안 되는 자리도 분명하다. $V$ 가 $10^5$ 인 도로망에서는 메모리부터 터진다. 그런 규모의 APSP는 애초에 전부 저장하지 않고, 축약 계층이나 허브 라벨링 같은 전처리로 질의마다 답을 만들어 낸다.

8. 여담[편집]

세 사람 이름이 붙었지만 정작 “플로이드-워셜”이라는 합성 명칭은 나중에 굳어진 것이다. 플로이드의 원논문 Algorithm 97: Shortest Path는 CACM 한 쪽짜리로, 알고리즘 번호가 붙은 짧은 투고 시리즈의 한 편이었다. 반 쪽짜리 알고리즘이 60년 넘게 교과서를 지킨다.
$\Theta(V^3)$ 을 진짜로 깨는 것은 아직 미해결이다. 밀집 APSP가 “진성 준세제곱”( $O(V^{3-\varepsilon})$ ) 시간에 되느냐는 세밀 복잡도 이론의 대표적 난제이고, 지금까지의 최선은 $V^3$ 을 로그의 제곱근 지수만큼 나눈 $V^3/2^{\Theta(\sqrt{\log V})}$ 수준이다(Williams, 2014). 상수와 로그를 깎았을 뿐 지수는 그대로다.
행렬 곱셈의 슈트라센류 빠른 알고리즘을 $(\min,+)$ 에 그대로 못 쓰는 이유는 뺄셈이 없기 때문이다. 슈트라센은 곱셈 횟수를 줄이려고 항들을 더하고 빼는데, $(\min,+)$ 반환에는 min의 역원이 없다. 반환 구조가 코드를 짧게 만들어 준 대가를 여기서 치른다.

9. 관련 문서[편집]

왜 하필 조용히 틀리느냐가 이 버그의 악질적인 점이다. i, j, k 순서로 돌려도 완전 그래프처럼 경로가 짧은 경우에는 답이 맞아떨어져서 테스트를 통과해 버린다. 실제로는 삼중 루프를 여러 번 반복하면(총 $V$ 번쯤) 수렴하긴 하는데, 그건 이미 $\Theta(V^4)$ 짜리 다른 알고리즘이다. ↩
Warshall, S. (1962). “A theorem on Boolean matrices”. JACM 9(1), 11–12. / Floyd, R. W. (1962). “Algorithm 97: Shortest Path”. CACM 5(6), 345. 워셜의 논문에는 전설 하나가 붙어 다닌다 — 동료와 술내기를 하고 그 자리에서 증명을 해냈다는 이야기. 진위는 확인된 바 없지만 두 쪽짜리 논문이라는 사실이 소문에 힘을 실어 준다. ↩
그래서 이 알고리즘은 HPC 강의에서 “캐시 블로킹을 가르치기 가장 좋은 예제” 자리를 오래 지켰다. 행렬 곱셈만큼 단순한데 데이터 의존성이 살짝 있어서, 학생들이 “그냥 타일로 자르면 되는 거 아닌가”라고 했다가 대각 타일 처리에서 한 번 깨진다. ↩