특정 출발점이 아닌 '그래프 상의 모든 정점 간 최단 거리'를 한꺼번에 구해야 하는 상황이 있습니다. 예를 들어 지하철 노선도의 모든 역 사이의 거리를 계산하거나 소셜 네트워크의 사용자 간 최단 연결 고리를 분석할 때입니다. 이때 가장 유용하게 사용되는 기법이 바로 플로이드-워셜(Floyd-Warshall) 알고리즘입니다. 본 포스팅에서는 모든 쌍의 최단 경로를 산출하는 이 강력한 알고리즘의 원리를 상세히 기술하겠습니다[cite: 410, 422].
1. 플로이드-워셜의 원리와 동적 계획법
[cite: 11, 33]
플로이드-워셜 알고리즘은 '거쳐가는 정점'을 기준으로 최단 경로를 갱신합니다. 임의의 정점 $i$에서 $j$로 가는 최단 경로는 중간에 어떤 정점 $k$를 거쳐가는 것이 더 빠른지, 아니면 기존 경로가 더 빠른지를 비교하며 점진적으로 개선해 나갑니다. 이는 작은 문제들의 해를 모아 큰 문제의 해를 구하는 동적 계획법(Dynamic Programming)의 전형적인 사례입니다[cite: 237, 242, 288].
1-1. 알고리즘 점화식의 이해
알고리즘의 동작을 결정짓는 핵심 점화식은 다음과 같습니다. 모든 정점 $k$에 대하여 각 정점 쌍 $(i, j)$의 거리를 갱신합니다.
$D[i][j] = \min(D[i][j], D[i][k] + D[k][j])$
이 식은 $i$에서 $j$로 바로 가는 비용과 $k$를 경유하여 가는 비용 중 최솟값을 선택한다는 논리적 함의를 담고 있습니다.
2. 3중 반복문 구조와 시간 복잡도의 특성
[cite: 11, 33]
플로이드-워셜 알고리즘은 구현이 매우 직관적이라는 장점이 있습니다. 2차원 배열(인접 행렬)을 생성한 뒤, 3중 for문을 사용하여 모든 정점을 중간 정점으로 설정하며 거리를 업데이트합니다. 하지만 정점의 개수가 $N$일 때 3중 반복문이 수행되므로 시간 복잡도는 $O(N^3)$에 달합니다[cite: 288].
2-1. 적절한 사용 환경
$O(N^3)$의 복잡도는 노드 수가 많아질수록 기하급수적으로 연산량이 증가함을 의미합니다. 따라서 보통 노드 수가 500개 이하인 '밀집 그래프' 환경에서 가장 효과적으로 활용됩니다. 반면 노드 수는 많고 간선이 적은 희소 그래프에서는 다익스트라를 반복 수행하는 것이 더 유리할 수 있습니다.
3. 실무에서의 활용 및 음수 가중치 처리
[cite: 11, 33]
이 알고리즘은 벨만-포드와 마찬가지로 음수 가중치 간선이 포함되어 있어도 정상 동작합니다. 단, 음수 사이클이 있는 경우에는 정확한 값을 낼 수 없으므로 주의가 필요합니다. 실무에서는 버스 환승 경로 정보 시스템, 통신 네트워크의 라우팅 테이블 생성, 그리고 복잡한 선행 관계를 가진 데이터 구조의 연결성 확인 등에 폭넓게 사용됩니다[cite: 288, 289].
1. 올페어 최단 경로: 한 번의 실행으로 그래프 내 모든 지점 간의 최단 거리를 산출합니다.
2. 동적 계획법: 중간 노드 $k$를 거쳐가는 경로를 탐색하며 2차원 거리 행렬을 갱신합니다.
3. 적용 분야: 노드 수가 적은 네트워크망의 전수 조사에 최적화되어 있으며 구현이 매우 간결합니다.