플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘입니다. 주요 특징은 다음과 같습니다.
- 모든 정점 → 모든 정점의 최단 거리를 구합니다.
- 음수 가중치 간선을 포함한 그래프에서도 사용 가능합니다. (단, 음수 사이클은 없어야 합니다.)
- 동적 계획법(Dynamic Programming) 원리를 기반으로 합니다.
- 시간 복잡도는 입니다. (V: 정점의 개수)
처음 이 알고리즘을 접했을 때, "부분 경로의 최단 경로가 전체 최단 경로를 이룬다"라는 개념이 낯설게 느껴졌습니다. 이 글을 통해 그 개념을 확실히 이해하고 넘어가 보겠습니다.
💡 핵심 아이디어: "거쳐가는 게 더 빠를까?"
플로이드-워셜의 본질은 아주 간단한 질문을 모든 노드 쌍에 대해 반복하는 것입니다.
"A에서 B로 바로 가는 것" 과 "중간에 K를 거쳐 가는 것" 중 어느 것이 더 빠를까?
이 알고리즘은 모든 노드를 출발점(S), 도착점(E), 그리고 경유지(K)로 지정하여, 가능한 모든 경로를 체계적으로 확인하며 최단 거리를 점진적으로 갱신해 나갑니다.
이 아이디어는 다음과 같은 점화식으로 표현됩니다.
D[S][E] = min(D[S][E], D[S][K] + D[K][E])
- D[S][E]: S에서 E까지의 기존 최단 거리
- D[S][K] + D[K][E]: S에서 K를 거쳐 E까지 가는 새로운 경로의 거리
즉, "기존 경로 vs K 경유 경로" 중 더 짧은 값을 새로운 최단 거리로 계속해서 덮어쓰는 것입니다.✨ "아하!" 포인트: K는 경유지의 '개수'가 아니다!
여기서 가장 많이 헷갈리는 부분은 3중 반복문의 가장 바깥쪽 K입니다. "중간 노드가 1개일 때, 2개일 때... 순서대로 찾는 건가?" 라고 생각하기 쉽지만, 사실은 다릅니다.
K는 "중간에 거쳐가도 좋다고 허용된 노드의 집합" 을 의미합니다.
- K=1 일 때: "1번 노드만 경유지로 사용했을 때"의 최단 거리를 계산하여 테이블 전체를 업데이트합니다.
- K=2 일 때: "K=1의 결과가 이미 반영된 테이블을 가지고, 추가로 2번 노드를 경유지로 사용했을 때"의 최단 거리를 계산합니다.
이것이 바로 동적 계획법의 핵심입니다. 이전 단계의 계산 결과(최적해)를 다음 단계에서 그대로 활용하여 점진적으로 최종 해답을 찾아 나가는 것이죠. K=2의 계산은 K=1의 결과를 이미 포함하고 있으므로, S → 1 → 2 → E와 같은 복잡한 경로도 자연스럽게 계산됩니다.
🗺️ 예제로 따라가기
아래 그래프 예시를 통해 알고리즘의 진행 과정을 살펴보겠습니다.
[초기 테이블]
| S\E | 1 | 2 | 3 | 4 | 5 |
| :-- | :-: | :-: | :-: | :-: | :-: |
| 1 | 0 | 8 | 3 | ∞ | ∞ |
| 2 | ∞ | 0 | ∞ | -4 | 15 |
| 3 | ∞ | ∞ | 0 | 13 | ∞ |
| 4 | ∞ | ∞ | ∞ | 0 | 2 |
| 5 | ∞ | ∞ | ∞ | 5 | 0 |
[K=2 일 때] (1 → 2 → 4) 경로 발견
D[1][4]= min(∞,D[1][2]+D[2][4]) = min(∞, 8 + (-4)) = 4
[K=4 일 때] (1 → 4 → 5), (2 → 4 → 5) 등 새로운 경로 대거 발견
D[1][5]= min(23,D[1][4]+D[4][5]) = min(23, 4 + 2) = 6D[2][5]= min(15,D[2][4]+D[4][5]) = min(15, -4 + 2) = -2
[최종 결과 테이블]
| S\E | 1 | 2 | 3 | 4 | 5 |
| :-- | :-: | :-: | :-: | :-: | :-: |
| 1 | 0 | 8 | 3 | 4 | 6 |
| 2 | ∞ | 0 | ∞ | -4 | -2 |
| 3 | ∞ | ∞ | 0 | 13 | 15 |
| 4 | ∞ | ∞ | ∞ | 0 | 2 |
| 5 | ∞ | ∞ | ∞ | 5 | 0 |
최종적으로 1번에서 5번까지의 최단 거리는 6이며, 이는 1 → 2 → 4 → 5 경로가 누적된 업데이트를 통해 찾아진 결과입니다.
맺음말
플로이드-워셜 알고리즘의 핵심은 K를 '허용된 경유지 집합의 확장' 으로 이해하는 것에 있습니다. 점진적으로 최단 거리 테이블을 완성해나가는 동적 계획법의 아름다움을 잘 보여주는 알고리즘이라고 할 수 있습니다. 이 글로 플로이드-워셜에 대한 막연한 어려움이 해소되었기를 바랍니다.
