[알고리즘] 플로이드-와샬 (Floyd-Warshall) 로 최단거리 구하기 (C++로 구현하기)

플로이드-와샬 알고리즘이란?

다익스트라, 벨만포드 알고리즘과 더불어 대표적인 최단거리 찾기 알고리즘이다.

플로이드-와샬 알고리즘은 그 중에서도 모든 정점끼리의 최단거리를 한번에 계산할 때 사용한다.

 

즉, 다익스트라 알고리즘은 어떤 정점 A에서 다른 정점들까지의 최단거리를 계산한다면,

플로이드-와샬 알고리즘은 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산한다는 것이다.

 

다익스트라 알고리즘은 특정 정점을 중심으로 식을 계산시켜 나간다면,

플로이드-와샬 알고리즘은 계산을 위해 거쳐가는 정점을 중심으로 계산해나간다는 것이다.

 

또한, 플로이드-와샬 알고리즘의 중요한 특징 중 하나는

동적 계획법을 이용하여 최단 거리를 계산해나간다는 것이다.

 

 

동작 원리

위와 같은 초기 상황이 주어졌다고 가정하자.

일반적인 배열을 사용하여 주어진 노드와 에지를 표현한다면 다음과 같을 것이다.

 

이제 거쳐가는 정점을 중심으로 거리를 계산시켜 나갈 수 있다.

가장 먼저 노드 0 을 거쳐갈 때를 생각해보자.

 

 

위의 (1 → 2) 로 갈때의 최단거리를 생각해보자.

노드 0 을 거쳐간다고 했으므로, 우리는

(1 → 0) → (0 → 2) 와 (1 → 2) 의 값을 비교하면 된다.

의 경우를 보면 된다.

여기에서는 

(1 → 0) → (0 → 2) : 7 + (무한)

(1 → 2)                : 9 (기존값)

이므로, 거쳐가는 거리인 7 + (무한) 의 값이 더 크므로 갱신되지 않는다.

 

그렇다면 다음의 경우를 보자.

 

 

여기에서는 

(1 → 0) → (0 → 3) 과 (1 → 3) 을 비교해보면

(1 → 0) → (0 → 3) : 7 + 8

(1 → 2)               : (무한) (기본값)

이므로, 거쳐가는 거리가 더 짦음을 알 수 있으므로, 다음과 같이 갱신된다.

 

 

이와 같은 방식으로, 모든 지점에 대해서 갱신해주면 된다.

각각의 거쳐가는 정점들에 대해서, 그래프를 전체적으로 갱신하므로

O(N ^ 3)의 시간복잡도를 가지게 된다.

 

 

 

구현 (C++)

#include <iostream>

#define	INF		1000000000
#define NODE	4

using namespace std;

int graph[NODE][NODE] = {
	{0, 5, INF, 8},
	{7, 0, 9, INF},
	{2, INF, 0, 4},
	{INF, INF, 3, 0}
};

void floyd_washall()
{
	int dp[NODE][NODE];
	for (int i = 0; i < NODE; i++)
		for (int j = 0; j < NODE; j++)
			dp[i][j] = graph[i][j];

	// k : 거쳐가는 노드
	for (int k = 0; k < NODE; k++)
		// i : 출발지 노드
		for (int i = 0; i < NODE; i++)
			// j : 도착지 노드
			for (int j = 0; j < NODE; j++)
				if (dp[i][k] + dp[k][j] < dp[i][j])
					dp[i][j] = dp[i][k] + dp[k][j];

	for (int i = 0; i < NODE; i++)
	{
		for (int j = 0; j < NODE; j++)
		{
			if (dp[i][j] == INF) cout << "-1 ";
			else cout << dp[i][j] << " ";
		}
		cout << '\n';
	}
}

int main(void)
{
	floyd_washall();

	return 0;
}