[Daily morning study] 플로이드-워셜(Floyd-Warshall) 알고리즘 — 모든 쌍 최단 경로
#daily morning study
개요
Floyd-Warshall은 그래프에서 모든 쌍(all-pairs)의 최단 경로를 한 번에 구하는 알고리즘이다.
Dijkstra나 Bellman-Ford가 단일 출발점(single-source)에서 각 정점까지의 최단 거리를 구하는 것과 달리, Floyd-Warshall은 임의의 두 정점 (i, j) 사이의 최단 거리를 모두 계산한다.
핵심 아이디어
“k번 정점을 중간 경유지로 허용했을 때, i에서 j까지의 최단 경로는 얼마인가?”
경유지 k를 1번부터 N번까지 하나씩 늘려가면서 점화식을 반복 적용한다.
점화식:
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
dp[i][j]: 현재까지 허용된 경유지를 사용했을 때 i → j의 최단 거리k: 이번에 추가로 허용된 경유지 번호
k를 1부터 N까지 순서대로 고려하면, 최종적으로 모든 경유지를 허용한 결과(즉, 진짜 최단 경로)가 dp에 저장된다.
구현
INF = float('inf')
def floyd_warshall(N, edges):
# 초기화
dp = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
dp[i][i] = 0
for u, v, w in edges:
dp[u][v] = w # 방향 그래프
# 삼중 루프: 경유지 k를 하나씩 추가
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
if dp[i][k] + dp[k][j] < dp[i][j]:
dp[i][j] = dp[i][k] + dp[k][j]
return dp
루프 순서가 중요하다. 가장 바깥 루프가 k (경유지) 여야 한다. i, j 루프를 바깥으로 빼면 올바른 결과를 얻을 수 없다.
시간/공간 복잡도
| 항목 | 복잡도 |
|---|---|
| 시간 | O(V³) |
| 공간 | O(V²) |
V는 정점 수. 삼중 루프이므로 자연스럽게 O(V³). V가 500 이하일 때 실용적이다 (V=1000이면 약 10억 연산).
다른 최단 경로 알고리즘과 비교
| 항목 | Dijkstra | Bellman-Ford | Floyd-Warshall |
|---|---|---|---|
| 목적 | 단일 출발점 | 단일 출발점 | 모든 쌍 |
| 시간복잡도 | O((V+E) log V) | O(VE) | O(V³) |
| 음수 간선 | 불가 | 가능 | 가능 |
| 음수 사이클 탐지 | 불가 | 가능 | 가능 |
| 구현 난이도 | 중 | 하 | 하 |
Floyd-Warshall은 음수 가중치 간선이 있어도 동작한다. 단, 음수 사이클이 존재하면 최단 경로가 정의되지 않으므로 탐지가 필요하다.
음수 사이클 탐지
Floyd-Warshall 수행 후 dp[i][i] < 0인 정점이 있으면 음수 사이클이 그래프에 존재한다는 뜻이다.
for i in range(1, N + 1):
if dp[i][i] < 0:
print(f"음수 사이클 존재: 정점 {i} 포함")
원래 dp[i][i] = 0으로 초기화했는데, 음수 사이클이 있으면 i → … → i 경로가 음수 합이 되어 dp[i][i]가 0보다 작아진다.
경로 복원 (Path Reconstruction)
최단 거리뿐만 아니라 실제 경로도 추적하려면 next[i][j] 배열을 관리한다.
def floyd_warshall_with_path(N, edges):
INF = float('inf')
dp = [[INF] * (N + 1) for _ in range(N + 1)]
nxt = [[None] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
dp[i][i] = 0
nxt[i][i] = i
for u, v, w in edges:
if w < dp[u][v]:
dp[u][v] = w
nxt[u][v] = v
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
if dp[i][k] + dp[k][j] < dp[i][j]:
dp[i][j] = dp[i][k] + dp[k][j]
nxt[i][j] = nxt[i][k] # i→j는 i→k 경로를 먼저 따라감
return dp, nxt
def get_path(nxt, i, j, dp):
INF = float('inf')
if dp[i][j] == INF:
return []
path = [i]
while i != j:
i = nxt[i][j]
path.append(i)
return path
경유지 k를 거쳐 i→j를 지나갈 때, nxt[i][j] = nxt[i][k]로 업데이트한다. i에서 k까지 가는 첫 번째 다음 정점이 i에서 j까지 가는 첫 번째 다음 정점이 되기 때문이다.
이행적 폐쇄 (Transitive Closure)
최단 거리가 필요 없고 도달 가능 여부만 파악할 때는 boolean 배열로 간소화할 수 있다.
def transitive_closure(N, edges):
reach = [[False] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
reach[i][i] = True
for u, v in edges:
reach[u][v] = True
for k in range(1, N + 1):
for i in range(1, N + 1):
for j in range(1, N + 1):
reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
return reach
활용 사례
- 도시 간 최단 거리 테이블 — V개 도시 간의 모든 최단 경로를 미리 계산해 쿼리 응답
- 네트워크 라우팅 — 라우터 간 최소 비용 경로를 한 번에 계산
- 최대 용량 경로 (Widest Path) —
min대신max를 사용해 병목 대역폭 최대화 - Minimax Path — i → j 경로 중 최대 간선 가중치를 최소화하는 경로
- 소셜 네트워크 도달성 — 이행적 폐쇄를 통해 영향력 범위 계산
구현 시 주의사항
INF 오버플로 문제 (C++ 등에서)
Python은 임의 정밀도 정수라 float('inf')를 쓰면 안전하지만, C++에서는 INF = 1e9처럼 큰 값을 쓸 때 INF + INF가 오버플로될 수 있다.
// C++ 예시: 오버플로 방지
const long long INF = 1e18;
if (dp[i][k] != INF && dp[k][j] != INF)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
루프 순서 고정
경유지 k가 가장 바깥 루프여야 한다. i, j 순서는 바꿔도 무방하다.
자기 자신 초기화
dp[i][i] = 0 초기화를 빠뜨리면 음수 사이클 탐지뿐만 아니라 경로 계산 전체가 틀어진다.
정리
Floyd-Warshall 핵심 요약:
목적 : 모든 쌍 최단 경로
복잡도: O(V³) 시간, O(V²) 공간
점화식: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
음수 : 간선 허용, 사이클 불가 (dp[i][i] < 0 → 사이클 존재)
경유지 루프(k)가 반드시 가장 바깥에 위치해야 함
