플로이드-워셜 알고리즘이란?
플로이드-워셜(Floyd-Warshall) 알고리즘은 가중치 그래프에서 모든 정점 쌍 사이의 최단 경로를 한 번에 구하는 대표적인 동적 계획법(Dynamic Programming) 기반 알고리즘입니다. 알고리즘을 수행하면 그래프 안의 어떤 노드에서 다른 모든 노드까지의 최소 거리가 담긴 행렬이 생성됩니다.
다익스트라 알고리즘이 하나의 시작 정점을 기준으로 최단 거리를 구하는 것과 달리, 플로이드-워셜은 단 한 번의 실행만으로 모든 정점 쌍의 최단 거리를 계산할 수 있다는 점이 큰 강점입니다.
동작 원리
처음에 결과 행렬은 그래프의 비용(cost) 행렬과 동일하게 초기화됩니다. 이후 각 정점 k를 중간 경유지로 삼아, 'i → k → j'로 이동하는 경로의 거리가 기존의 i → j 직접 거리보다 짧은지 확인하고, 더 짧다면 해당 값을 갱신합니다. 이 과정을 모든 정점에 대해 반복하면 최종적으로 모든 정점 쌍의 최단 거리 행렬이 완성됩니다.
이 알고리즘의 시간 복잡도는 O(V³)이며, 여기서 V는 그래프의 정점 개수입니다. 공간 복잡도는 거리 정보를 저장하는 2차원 행렬로 인해 O(V²)입니다.
입력과 출력
입력: 그래프의 비용 행렬 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
알고리즘 (의사 코드)
floydWarshall(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
현재 비용 행렬 출력
EndC++ 구현 예제
#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 floydWarshall() {
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++) {
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() {
floydWarshall();
}실행 결과
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³), 공간 복잡도는 O(V²)로, 정점 수가 많은 희소 그래프에는 부적합하고 정점 수가 적은 밀집 그래프에 적합합니다.
- 구현이 매우 단순하며, 음의 가중치를 가진 간선도 처리할 수 있습니다(단, 음의 사이클이 존재하면 결과가 유효하지 않습니다).