플로이드-워셜 알고리즘이란?
모든 쌍 최단 경로(All-Pair Shortest Path) 알고리즘은 흔히 플로이드-워셜(Floyd-Warshall) 알고리즘이라는 이름으로도 널리 알려져 있으며, 가중치 그래프에서 임의의 두 정점 사이의 최단 경로를 한 번에 구하는 대표적인 동적 계획법 기반 알고리즘입니다. 이 알고리즘을 수행하면 그래프 내 어떤 노드에서 다른 모든 노드까지의 최소 거리를 담고 있는 행렬(matrix)이 결과물로 생성됩니다.
동작 방식은 다음과 같습니다. 처음에 출력 행렬은 그래프의 비용 행렬(cost matrix)과 동일하게 설정됩니다. 이후 각 정점 k를 '중간 정점'으로 삼아 i에서 j로 가는 경로를 점검하면서, k를 거쳐 가는 경로가 더 짧다면 행렬의 값을 갱신합니다. 이 과정을 모든 정점에 대해 반복하면 최종적으로 모든 쌍의 최단 거리가 완성됩니다.
이 알고리즘의 시간 복잡도는 O(V³)이며, 여기서 V는 그래프의 정점 개수를 의미합니다. 세 겹의 반복문을 사용하기 때문에 정점 수가 매우 많은 그래프에는 부적합하지만, 음수 가중치 간선이 있어도 올바르게 동작하고 구현이 매우 간단하다는 큰 장점이 있습니다. 단, 음수 사이클(negative cycle)이 존재하는 그래프에서는 최단 거리가 정의되지 않으므로 주의해야 합니다.
입출력 예시
입력 − 그래프의 비용 행렬 (∞는 해당 정점 사이에 직접 연결된 간선이 없음을 의미)
0 3 6 ∞ ∞ ∞ ∞
3 0 2 1 ∞ ∞ ∞
6 2 0 1 4 2 ∞
∞ 1 1 0 2 ∞ 4
∞ ∞ 4 2 0 2 1
∞ ∞ 2 ∞ 2 0 1
∞ ∞ ∞ 4 1 1 0
출력 − 모든 정점 쌍 사이의 최단 경로 거리를 나타내는 행렬
0 3 5 4 6 7 7
3 0 2 1 3 4 4
5 2 0 1 3 2 3
4 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0
예를 들어 0번 정점에서 2번 정점까지의 직접 비용은 6이지만, 1번 정점을 경유하면 3 + 2 = 5가 되므로 결과 행렬에는 5가 기록됩니다. 이처럼 중간 정점을 활용한 더 짧은 경로가 발견될 때마다 값이 갱신되는 것이 핵심입니다.
알고리즘 의사코드
floydWarshal(cost)
입력 − 주어진 그래프의 비용 행렬
출력 − 임의의 정점에서 다른 정점까지의 최단 경로 거리를 저장한 행렬
Begin
for k := 0 to n-1, do
for i := 0 to n-1, do
for j := 0 to n-1, do
if cost[i,k] + cost[k,j] < cost[i,j], then
cost[i,j] := cost[i,k] + cost[k,j]
done
done
done
display the current cost matrix
End
C++ 구현 예제
#include<iostream>
#include<iomanip>
#define NODE 7
#define INF 999
using namespace std;
// 그래프의 비용 행렬
int costMat[NODE][NODE] = {
{0, 3, 6, INF, INF, INF, INF},
{3, 0, 2, 1, INF, INF, INF},
{6, 2, 0, 1, 4, 2, INF},
{INF, 1, 1, 0, 2, INF, 4},
{INF, INF, 4, 2, 0, 2, 1},
{INF, INF, 2, INF, 2, 0, 1},
{INF, INF, INF, 4, 1, 1, 0}
};
void floydWarshal(){
int cost[NODE][NODE]; // 노드 간 최단 거리를 저장할 행렬
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
cost[i][j] = costMat[i][j]; // 비용 행렬을 새 행렬에 복사
for(int k = 0; k<NODE; k++){ // k를 중간 정점으로 사용
for(int i = 0; i<NODE; i++)
for(int j = 0; j<NODE; j++)
if(cost[i][k]+cost[k][j] < cost[i][j])
cost[i][j] = cost[i][k]+cost[k][j];
}
cout << "The matrix:" << endl;
for(int i = 0; i<NODE; i++){
for(int j = 0; j<NODE; j++)
cout << setw(3) << cost[i][j];
cout << endl;
}
}
int main(){
floydWarshal();
}
실행 결과
The matrix:
0 3 5 4 6 7 7
3 0 2 1 3 4 4
5 2 0 1 3 2 3
4 1 1 0 2 3 3
6 3 3 2 0 2 1
7 4 2 3 2 0 1
7 4 3 3 1 1 0
마무리
플로이드-워셜 알고리즘은 다익스트라 알고리즘을 모든 정점에 대해 반복 실행하는 것과 달리 하나의 통합된 절차로 전체 최단 거리 행렬을 구할 수 있으며, 공간 복잡도는 O(V²)로 비용 행렬 하나면 충분합니다. 특히 간선 밀도가 높은 밀집 그래프(dense graph)나 음수 가중치가 포함된 그래프에서 유용하게 활용되며, 네트워크 라우팅, 지도 경로 탐색, 교통 시스템 분석 등 다양한 분야에서 널리 사용되고 있습니다.