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

 대표적인 최단 경로 알고리즘 중에서 3번째 플로이드 워셜 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라나 벨만-포드와 다르게 1:N이 아닌 N:N 의 최단 시간을 찾을 수 있다. 최악 시간 복잡도는 O(|V|^3) 이다. 플로이드 워셜 알고리즘은 처음에 간선들의 정보와 자기 자신으로의 경로는 0이라는 정보만 주고, 모든 정점들의 경유를 하나씩 열면서 직접 가는 것보다 경유하는게 더 짧은지를 확인한다. 플로이드 워셜은 음수 사이클이 없는 그래프에서 음수 가중치가 있어도 사용할 수 있다. C++로 구현한 코드는 다음과 같다.

#define INF 1000000000

int n;
vector<vector<pair<int, int>>> edges;

vector<vector<int>> floyd_warshall()
{
	vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));
	 
	// 초기화 단계
	for (int i = 1; i <= n; i++)
	{
		dist[i][i] = 0;

		for (int j = 0; j < edges[i].size(); j++)
		{
			int next = edges[i][j].first;
			int cost = edges[i][j].second;

			dist[i][next] = cost;
		}
	}
	
	// 각 정점쌍에 대한 최단 시간 계산
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (dist[i][k] != INF && dist[k][j] != INF)
				{
					if (dist[i][j] > dist[i][k] + dist[k][j])
					{
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}
	}

	return dist;
}

 31번째 줄의 if문은 음수 가중치가 존재하는 경우에는 필수적이다. 벨만-포드 알고리즘에서와 마찬가지로, dist[i][j] 와 dist[i][k] 가 INF이고, dist[k][j] 가 음수라면 원래 개념적으로는 if문이 실행되지 않아야 하지만 값으로 보면 맞는 조건문이 되기 때문이다. 그래서 음수 가중치가 존재한다면 비교를 수행할 dist[i][k] 와 dist[k][j] 는 반드시 INF가 아니여야 한다.

 

 

 

참고

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98