앞서 우리는 다익스트라(Dijkstra) 알고리즘을 통해 '어느 한 출발 도시'에서 '나머지 모든 도시'로 가는 최단 경로를 구하는 방법을 배웠습니다. 하지만 현실의 비즈니스 요구사항은 훨씬 가혹합니다. 만약 서울에서 부산을 가는 최단 거리뿐만 아니라, "지도상에 존재하는 대전, 대구, 광주 등 모든 도시에서 출발하여 또 다른 모든 도시로 도착하는 최단 거리를 하나의 표(Matrix)로 싹 다 뽑아주세요"라는 요청이 들어오면 어떻게 해야 할까요? 다익스트라 알고리즘을 N번 반복해서 돌릴 수도 있겠지만, 코드가 몹시 지저분해지고 로직이 복잡해집니다. 이럴 때 불과 세 줄의 반복문만으로 마법처럼 모든 정점 간의 최단 경로를 한 번에 계산해 내는 우아한 알고리즘이 바로 '플로이드-워셜(Floyd-Warshall)'입니다.
1. 플로이드-워셜 알고리즘이란? (All-Pairs Shortest Path)
플로이드-워셜은 그래프에 존재하는 '모든 정점'에서 '모든 정점'으로 가는 최단 거리를 구하는 궁극의 길찾기 알고리즘입니다. 다익스트라가 그리디(Greedy) 방식에 기반한다면, 플로이드-워셜은 철저하게 동적 계획법(DP)의 원리를 따릅니다. 또한, 다익스트라가 절대 소화하지 못하는 '음수 가중치(-)' 간선이 존재하더라도 정상적으로 최단 거리를 구해낼 수 있다는 엄청난 장점을 지니고 있습니다. (단, 무한 루프에 빠지는 음수 사이클이 없다는 전제하에 가능합니다.)
2. 알고리즘의 심장: "거쳐 가는 정점(K)"의 마법
플로이드-워셜 알고리즘의 아이디어는 문장 한 줄로 요약될 만큼 매우 심플합니다. "A에서 B로 곧장 다이렉트로 가는 길보다, 중간에 K라는 정점을 한 번 거쳐서 가는 길이 혹시 더 빠르지 않을까?" 바로 이 질문을 모든 노드에 대해 던지는 것입니다.
2-1. 2차원 최단 거리 배열과 점화식
모든 노드 간의 거리를 담아야 하므로 2차원 배열 dist[i][j]를 선언합니다. 초기에는 자신에게 가는 거리는 0, 직접 연결된 길은 그 비용, 길이 없는 곳은 무한대(Infinity)로 채워 넣습니다.
그리고 대망의 핵심 점화식을 수행합니다.
// 점화식: i에서 j로 가는 거리와, i에서 k를 거쳐 j로 가는 거리를 비교하여 최솟값 갱신dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])2-2. 3중 반복문의 우아한 구조
플로이드-워셜의 실제 코드는 컴퓨터 공학을 통틀어 가장 간결하고 아름다운 형태 중 하나로 꼽힙니다. 단 3개의 중첩된 for문으로 구현됩니다.
// K: 거쳐 가는 중간 노드 (가장 바깥쪽 루프여야 함이 절대적으로 중요!)for (int k = 1; k <= N; k++) {// I: 출발 노드for (int i = 1; i <= N; i++) {// J: 도착 노드for (int j = 1; j <= N; j++) {// k를 거쳐가는 게 더 빠르다면 거리 갱신if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}여기서 초보자들이 99% 확률로 저지르는 실수가 있습니다. 바로 '거쳐 가는 노드인 K'를 가장 바깥쪽 루프에 두지 않고 안쪽에 두는 것입니다. 플로이드-워셜은 "1번 노드를 거쳐 갈 때의 모든 맵을 갱신하고, 그 결과를 바탕으로 2번 노드를 거쳐 갈 때를 갱신하는 식"으로 DP가 쌓여나가야 합니다. K가 안쪽으로 들어가면, 아직 갱신되지도 않은 과거의 데이터를 참조하게 되어 완전히 엉터리 거리가 계산됩니다.
3. 시간 복잡도의 압박과 실무적 한계 (O(V^3))
코드가 이토록 짧고 구현이 쉬우며 모든 경로를 구해주는 완벽한 알고리즘이지만, 치명적인 단점이 하나 있습니다. 바로 3중 반복문에서 비롯되는 O(V^3)이라는 무지막지한 시간 복잡도입니다. 정점(노드)의 개수가 $V$일 때, 100개면 100만 번, 500개면 1억 2,500만 번의 연산을 수행해야 합니다.따라서 코딩 테스트나 실무 아키텍처 설계 시, 플로이드-워셜은 전체 노드의 개수가 최대 500개 이하일 정도로 매우 규모가 작은 그래프 환경에서만 사용해야 한다는 엄격한 제한을 스스로 걸어두어야 합니다. 노드가 수만 개를 넘어가는 일반적인 지도 데이터에서는 다익스트라나 A* 알고리즘을 반복 적용하는 것이 훨씬 현명한 선택입니다.
for문이라는 매우 간결하고 우아한 형태를 띱니다.3. 중간 기착지 K를 반드시 가장 바깥쪽 반복문에 두어야 하며, 시간 복잡도가 O(V^3)으로 매우 무거워 노드 개수가 적을 때만 사용 가능합니다.