Floyd-Warshall 알고리즘

Floyd-Warshall 알고리즘

모든 정점 쌍 사이의 최단 경로를 찾는 동적 프로그래밍 기반 알고리즘

목적: 모든 쌍 최단 경로, 음수 가중치 가능

특징: 동적 프로그래밍, 3중 루프, 음수 가중치 가능, 간단 구현

동작 상세

점화식: dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

• •k: 경유 가능한 정점 집합 {0, 1, ..., k}
• •공간 최적화: dp[k-1]을 dp[k]로 덮어쓰기 가능 → O(V²) 공간

루프 순서의 중요성: 반드시 k가 최외곽 루프여야 함 (경유 정점 확장 순서 보장)

시간 복잡도: O(V³) - 3중 루프

공간 복잡도: O(V²) - 거리 행렬

음수 사이클 탐지: 알고리즘 수행 후 dist[i][i] < 0인 정점 i가 있으면 음수 사이클 존재

장점: 모든 쌍 최단 경로, 음수 가중치 가능, 구현이 매우 단순 (3중 for문), 작은 그래프에서 효율적

단점: O(V³) 느림, 메모리 O(V²), 대규모 그래프(V>수백) 비효율, 간선이 적어도 V³ 수행

Dijkstra×V와의 선택 기준

• •밀집 그래프(E ≈ V²): Floyd-Warshall O(V³) ≈ Dijkstra×V, 구현 단순한 Floyd 유리
• •희소 그래프(E << V²): Dijkstra×V가 O(V(V+E)logV)로 더 효율적
• •음수 가중치 존재: Floyd-Warshall 또는 Bellman-Ford×V 필요

적용사례: 작은 그래프 모든 쌍 경로, 네트워크 분석, 거리 행렬 계산, 이행적 폐쇄(Transitive Closure)

비교: Floyd-Warshall(모든쌍/O(V³)/단순) vs Dijkstra×V(모든쌍/O(V(V+E)logV)/양수만)

연관: 동적 프로그래밍, 최단 경로, Bellman-Ford, 모든 쌍, 이행적 폐쇄