한양과기고 에듀테크 수업도구 대시보드

플로이드-워셜 알고리즘 (Floyd-Warshall)

다익스트라나 벨만-포드는 한 출발점에서 모든 정점까지의 최단 거리를 구한다. 그런데 "모든 정점 쌍 사이의 최단 거리"가 필요하다면? 플로이드-워셜은 단 3중 for 루프, O(V³) 로 이걸 한 번에 푼다. 핵심 아이디어는 딱 하나 — "경유해도 되는 정점을 하나씩 늘려 가며, i → k → j 로 돌아가는 게 더 짧으면 갱신한다." 음수 간선도 허용하고, 대각선 dist[i][i] 가 음수가 되면 음수 사이클이 있다는 뜻이다.

경유지 k 를 늘려 가는 거리 행렬

dist[i][j] = 현재까지 알아낸 i 에서 j 로 가는 최단 거리. 처음엔 대각선 0, 직접 간선은 그 가중치, 나머지는 ∞ 다. [다음 경유지 ▶] 를 누를 때마다 정점 하나(k)를 "경유 허용 목록"에 추가하고, 모든 칸에 대해 dist[i][k] + dist[k][j] < dist[i][j] 이면 그 값으로 갱신한다. 파란 열은 ·→k, 주황 행은 k→·, 보라 십자가 이번에 기준이 되는 값이다.

·→k 열 k→· 행 기준 십자 이번에 갱신된 칸 대각선 (자기 자신)

경유 허용

{ }

이번 단계 갱신

–

누적 갱신 수

대각선은 0, 직접 간선은 가중치, 나머지는 ∞. [다음 경유지 ▶] 를 눌러 정점 A 부터 경유지로 추가해 보세요.

왜 k 가 가장 바깥 루프일까

dist^(k)[i][j] 를 "경유지를 {0, 1, …, k} 안에서만 골라 i 에서 j 로 가는 최단 거리"라고 정의하자. 그러면 정점 k 를 새로 허용했을 때, i→j 최단 경로는 딱 두 경우 뿐이다.

k 를 안 지난다 → 값이 그대로다: dist^(k-1)[i][j]
k 를 딱 한 번 지난다 → i ⇝ k 와 k ⇝ j 로 쪼개지고, 두 조각은 k 를 내부 경유지로 쓰지 않으므로 dist^(k-1)[i][k] + dist^(k-1)[k][j]

즉 dist^(k)[i][j] = min( dist^(k-1)[i][j], dist^(k-1)[i][k] + dist^(k-1)[k][j] ). k 를 바깥에 두면 단계마다 "경유 가능한 정점 집합"이 커지고, 안쪽 i, j 이중 루프가 전체 행렬을 한 번씩 훑는다. 신기하게도 행렬을 제자리(in-place)에서 덮어써도 정답이다 — k 행·열은 이번 단계에서 값이 바뀌지 않기 때문 (dist[i][k] 는 dist[i][k] + dist[k][k], 즉 +0 과 비교되므로).

음수 사이클은 대각선에서 드러난다

어떤 정점 v 에서 출발해 음수 가중치 합의 고리를 돌아 v 로 돌아올 수 있다면, 알고리즘이 끝난 뒤 dist[v][v] < 0 이 된다. 원래 대각선은 0 이어야 하므로 이는 명백한 신호다. 위 시뮬레이터에서 [예제: 음수 사이클] 을 실행한 뒤 대각선을 확인해 보자 (B → C → D → B 의 합이 음수라 dist[B][B] 가 음수로 내려간다).

# 알고리즘 종료 후 for v in range(V): if dist[v][v] < 0: print("음수 사이클 존재 — 최단 경로 정의 불가")

전체는 3중 루프가 끝이다

def floyd_warshall(W): # W[i][j] = 간선 가중치, 없으면 INF, W[i][i]=0 V = len(W) dist = [row[:] for row in W] for k in range(V): # 경유 허용 정점을 하나씩 추가 for i in range(V): for j in range(V): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist

경로까지 복원하려면 next[i][j] 표를 함께 갱신한다 (갱신 시 next[i][j] = next[i][k]). 시간 O(V³), 공간 O(V²). 코드가 짧고 상수가 작아 V 가 수백 이하면 매우 실용적이다.

언제 무엇을 쓸까

	플로이드-워셜	다익스트라 ×V회	벨만-포드 ×V회
구하는 것	모든 쌍 최단 거리	모든 쌍 (양수 간선)	모든 쌍 (음수 허용)
음수 간선	허용 ✔	불가 ✘	허용 ✔
시간 복잡도	`O(V³)`	`O(V·E·log V)`	`O(V²·E)`
유리한 경우	조밀 그래프, 작은 V, 짧은 코드	희소 그래프, 큰 V, 양수	거의 안 씀 (존슨 알고리즘이 대체)

요약: 정점이 몇백 개 이하이고 모든 쌍 거리가 필요하면 플로이드-워셜이 가장 간단하고 빠르다. 정점이 아주 많고 그래프가 희소하면 존슨 알고리즘(벨만-포드로 가중치 재조정 후 다익스트라 V회)이 더 낫다. 추이적 폐포(도달 가능 여부)나 최소 병목 경로 등 min-plus 대신 다른 연산으로 바꿔도 같은 뼈대가 통한다.