Floyd-Warshall algorithm

목차 (클릭 시 이동)

 

Floyd-Warshall 알고리즘

Floyd-Warshall 알고리즘은 음의 순환이 없는 가중치 그래프에서 정점들 간 최단 거리를 찾는 알고리즘이다. 음의 가중치를 갖는 그래프에도 적용 가능하다.

한 번의 수행으로 각 정점들 서로 간의 최단 거리를 찾는다.

구현

알고리즘을 실행하기 위해 인접 리스트를 2차원 배열로 작성하면 편하다.

 

int main() {
	int n = 5; // # of vertices
	int edges[][3] = {
		{1, 2, 2},
		{2, 3, 6},
		{3, 2, 7},
		{4, 3, 1},
		{4, 5, 3},
		{5, 1, 1},
		{5, 2, 4},
	};
	// n + 1 to match the index with the number of vertex
	vector<vector<int>> adj(n + 1, vector<int>(n + 1, 0));

	// Initialize adjacency matrix
	for (const auto& e: edges) {
		int s = e[0], d = e[1], w = e[2];
		adj[s][d] = w;
	}

	vector<vector<int>> dist = FloydWarshall(adj);
	return 0;
}

2차원 배열 인접 정보를 인자로 넘기며 최단 경로 검색을 시작한다. 함수의 시작과 함께 2차원 인접 배열을 통해 최단 경로 정보를 갱신하며 저장할 2차원 배열을 선언한다.

 

vector<vector<int>> FloydWarshall(const vector<vector<int>>& adj) {
	int n = adj.size();
	vector<vector<int>> dist(n, vector<int>(n, 0));

	// Initialize dist with adj
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < n; ++j) {
			if (i == j) dist[i][j] = 0;
			else if(adj[i][j]) dist[i][j] = adj[i][j];
			else dist[i][j] = INF;
		}
	}
	...

자기 자신으로의 거리는 0, 서로 다른 정점으로는 인접 배열에 저장된 거리로, 서로 연결되지 않은 정점으로는 Infinity 로 초기화한다.

준비된 배열을 통해본격적인 알고리즘을 시작한다. 다음의 중첩 반복문이 Floyd-Warshall 알고리즘의 핵심이다.

 

	...
	for (int k = 1; k < n; ++k) {
		for (int i = 1; i < n; ++i) {
			for (int j = 1; j < n; ++j) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	return dist;
}

dist[i][j] 즉, 정점 사이의 거리를 dist[i][j] 와 dist[i][k] + dist[k][j] 중 짧은 거리로 갱신한다.

즉, dist matrix 에 기록된 i 와 j 가 연결된 거리와 어떤 정점 k 를 거쳐 가는 거리를 비교한다. k 를 전체 정점을 대상으로 순차적으로 진행하는데 정리하자면 어떤 두 정점 사이의 거리를 모든 정점 각각을 거쳐가는 거리와 비교해서 갱신하는 것 이다.

반복문이 중첩된 순서를 생각하며 알고리즘을 이해해보자. 거쳐가는 정점인 k 의 반복이 가장 바깥인데, 어떤 k 를 거치는 경로를 찾을 모든 두 정점을 시도한 뒤 다음 k 를 거치는 모든 두 정점 사이의 경로를 찾는다는 의미이다.

만약 k 의 반복이 가장 안쪽이라면, 어떤 두 정점이 중간에 거칠 수 있는 모든 다른 정점을 시도한 뒤 다른 두 정점에 대해서도 똑같이 거칠 수 있는 모든 정점을 시도한다는 의미가 된다.

후자의 경우가 왜 최단 경로를 찾지 못 하는지 (k 의 반복이 왜 바깥에 있어야 하는지) 간단한 예시로 확인해 보자.

이와 같은 그래프가 있을 때, 1 에서 2 로의 경로를 찾는 과정을 상상해보자.

i = 1, j = 2 일 때, dist[i][j] 를 계산하는 과정일 것 이다. 그런데 이를 계산하는 시점에는

dist[1][3] + dist[3][2] = Infinity
dist[1][4] + dist[4][2] = Infinity

이기 때문에 경로를 찾을 수 없다. (dist[1][4] 혹은 dist[3][2] 까지는 반복문이 아직 돌지 않아 Infinity 의 상태이기 때문.)

 

추후에 dist[1][4] 혹은 dist[3][2] 의 거리가 갱신되겠지만, 그 이후에 dist[1][2] 에 대한 계산을 하지 않으므로 거리는 Infinity 로 남는다.

 

만약 올바른 알고리즘대로 수행한다면 k = 3 일 때, dist[1][4] 가 갱신된다. 이후, k = 4 에서 dist[1][2] = dist[1][4] + dist[4][2] 를 계산하므로 최소 비용의 경로를 찾을 수 있다.

위에서 얘기한 "헷갈리는 말"을 다시 가져와 설명하자면, k 의 반복이 안쪽에서 일어날 때는 어떤 두 정점의 거리를 모든 k 들을 거치는 것으로 갱신한 뒤 다음 두 정점에 대해서 확인하기 때문에 이후에 발견한 새로운 정보(더 짧은 경로)에 대해서는 이미 이전에 계산해버린 두 정점의 거리에 적용하지 못 하게 된다. (예시에서 dist[1][4] 의 거리는 추후에 밝혀지지만 다시 dist[1][2]로 돌아가 새로운 정보를 사용할 수 없다.)

반면에, k 의 반복이 바깥에서 일어날 때는 어떤 k 를 모든 두 정점 쌍이 거쳤을 때 찾을 수 있는 새로운 정보를다음 k 에 대해 모든 두 정점 쌍을 확인할 때 활용할 수 있으므로 최소 비용의 경로를 갱신할 수 있다.

C++ 코드

시간 복잡도

|V| 가 정점의 개수일 때, 알고리즘 실행에 필요한 matrix 를 준비하는데 O(|V|^2) 의 시간이 들지만, 알고리즘을 실제로 수행하는 과정이 지배적인 시간 복잡도를 보이므로 무시할 수 있다.

 

	for (int k = 1; k < n; ++k) {
		for (int i = 1; i < n; ++i) {
			for (int j = 1; j < n; ++j) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

위의 핵심적인 코드 조각에서 i 와 j 로 두 정점을 조합하는데 |V|^2 만큼 계산하고, k를 통해 정점의 개수만큼 다시 반복하므로 총 O(|V|^3) 의 시간 복잡도를 가진다.

추가 정보

1. Floyd-Warshall 알고리즘은 Bellman-Ford 알고리즘처럼 탐색하는 그래프에 음의 순환이 존재하는지 알 수 있다.

 

알고리즘의 수행이 끝난 후 dist 배열의 대각선 정보인 "자기 자신으로의 거리" 가 음수인 정점이 있다면 음의 순환이 존재하는 것이다.

2.dist[i][k] + dist[k][j] 하는 과정에서 프로그램 상 정의한 Infinity 가 더해질 수 있다. 자신의 하드웨어와 사용 언어에 따라 Infinity 로 정의한 값의 합이 사용하는 자료형의 범위를 넘어가지 않도록 하자.

0x3f3f3f3f 혹은 987654321 등의 Infinity 를 정의하면 충분히 크면서도 두 Infinity 의 합이 범위를 초과하지 않는다.