Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘

모든 쌍의 최단 경로를 구하는 방법을 찾고 싶다면, 다익스트라(Dijkstra) 알고리즘을 모든 정점(Vertex)에 대한 최단경로를 구하거나 다익스트라가 제한되는 경우(음의 가중치가 존재하는 경우)에는 벨만-포드(Bellman-Ford) 알고리즘을 모든 정점(Vertex)에 대해서 사용하면 된다.

플로이드-워셜(Floyd-Warshall) 알고리즘은 앞서 말한 두 알고리즘과는 다르게 처음부터 모든 정점 사이의 최단 경로를 구하는 알고리즘이다.

위 그림은 i에서 j로 가는 방법을 표현한 것으로, k를 경유하는 경우와 그렇지 않은 경우에 대한 것이다.

위 문자의 의미는 1부터 k까지만 경유할 수 있는 상황에서 i에서 j까지 갈 수 있는 모든 경로 중, 가장 짧은 경로의 거리로, 동적계획법(Dynamic Programming)의 부분해에 해당한다. 특정 경로만 경유할 수 있는 상황에서 A에서 B까지의 모든 경로 중 가장 짧은 경로의 거리를 계산해 나가는 방법은 동적계획법의 점화식 정립 과정이라고 생각하면 된다.

위 그림을 다시 살펴보자, 이런 상황이 주어졌을 때 두 가지 경우를 따져볼 수 있다. k를 경유할 때와 그렇지 않을 때의 누적 가중치 값을 비교해 작은 경로를 채택하는 것이 답일 것이다.

위 그림을 바탕으로 한 점화식은 다음과 같으며, 이것이 플로이드-워셜 알고리즘의 핵심이다.

의사 코드(Pseudo Code)

Input

2차원 배열 D, D[i][j]는 i->j의 가중치, 경로가 없는 경우에는 D[i][j]=INF(무한)으로 정의하며, D[i][i]=0

Output

모든 쌍의 최단 경로 정보를 담은 배열 D

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)
    D[i][j]=min(D[i][k]+D[k][j], D[i][j])

소스 코드(Source Code)

#include <iostream>
#define INF 1000000000
using namespace std;
int graph[100][100], n;
void Floyd()
{
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (graph[i][k] + graph[k][j] < graph[i][j])
					graph[i][j] = graph[i][k] + graph[k][j];
}
int main(void)
{
	int b, v1, v2, w;
	cin >> n;

	// 배열값을 INF로 초기화
	// 경로 정보가 갱신되지 않으면 경로가 없는 것으로 간주
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			graph[i][j] = INF;
	// D[i][i]=0
	for (int i = 0; i < n; i++)
		graph[i][i] = 0;

	// 경로 정보 입력, v1->v2, weight(w)
	cin >> b;
	for (int i = 0; i < b; i++)
	{
		cin >> v1 >> v2 >> w;
		if (graph[v1 - 1][v2 - 1] > w)
			graph[v1 - 1][v2 - 1] = w;
	}

	Floyd();

	// 경로가 없는 경우 INF를 출력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (graph[i][j] == INF)
				cout << 'INF ';
			else
				cout << graph[i][j] << ' ';
		}
		cout << '\n';
	}
}

시간 복잡도(Time Complexity)

O(V^3), V는 정점 수

공간 복잡도(Space Complexity)

O(V^2), V는 정점 수

응용 분야

네비게이션, GIS 네트워크 분석, VLSI 디자인 등