'휴지통/알고리즘' 카테고리의 글 목록

휴지통/알고리즘

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

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

2022. 5. 22. 10:00

이 글은 Floyd-Warshall(플로이드-워셜; 플로이드-와샬) 알고리즘이 무엇인지, 그리고 Floyd-Warshall 알고리즘의 원리를 PS/CP에서 어떤 식으로 응용하는지에 대한 내용을 대략적으로 정리해둔 글이다.

1. Multiple-source multiple-destination shortest path problem

먼저 Floyd-Warshall 알고리즘을 살펴보기 전에 이 알고리즘을 적용할 문제가 무엇인지부터 살펴보자.

N개의 노드(V개의 버텍스)가 존재하고 에지에 거리 가중치가 존재하는 (방향)그래프 G를 생각해보자. 이 그래프 위의 한 점에서 모든 G 위의 각 노드까지의 거리를 구하는 문제를 single-source multiple-destination shortest path problem이라고 부른다. 이 문제의 해법으로는 거리 가중치가 음이 아닌 경우 O(ElgV)에 동작하는 Dijkstra(데이크스트라; 다익스트라) 알고리즘이, 거리 가중치가 음수일 수 있는 경우 O(VE)에 동작하는 Bellman-Ford 알고리즘이 잘 알려져있다.

한편 G 위의 모든 가능한 두 노드 사이의 최단 거리를 구하는 문제도 생각해볼 수 있는데, 이와 같은 문제를 multiple-source multiple-destination shortest path problem이라고 부른다. 이 문제는 각 노드별로 거리 가중치의 음수 존재 여부에 따라 Dijkstra 알고리즘 또는 Bellman-Ford 알고리즘을 한번씩 이용해 해결할 수도 있지만, 이보다 시간복잡도가 낮은 알고리즘이 존재한다. 바로 Floyd-Warshall 알고리즘이다.

Floyd-Warshall 알고리즘은 multiple-source multiple-destination shortest path problem의 해를 O(N^3)에 구하는 알고리즘이다. Floyd-Warshall 알고리즘은 거리 가중치가 음이 아닌, 굉장히 sparse한(에지의 밀도가 낮은) 그래프에서는 위의 V번 Dijkstra 알고리즘을 이용하는 O(VElgV) 해법보다 비효율적일 수 있으나, 에지가 많아질수록(V^2개에 가까워질수록) 좋은 효율을 보여준다. 또한 거리 가중치가 음수일 수 있다면 O(V^2E)에 작동하는, Bellman-Ford를 반복하는 해법보다 Floyd-Warshall이 더 빠르게 작동한다는 것을 알 수 있다.

이제 Floyd-Warshall 알고리즘을 알아보자.

2. Floyd-Warshall 알고리즘

Floyd-Warshall 알고리즘은 각 두 노드 사이를 잇는 최단경로를 DP를 이용하여 계산해나간다.

편의상 G의 모든 노드에 index를 1부터 N까지 하나씩 붙이자. 또한 G에는 음의 cycle이 없다고 가정하고 알고리즘을 설명할 것이다. 음의 cycle이 있는 경우는 아래의 연습문제에서 스스로 생각해보자.

집합 S(i,j,k)를 "중간에 경유하는(i와 j를 제외한) 모든 노드의 index가 k 이하인 경로"들의 집합이라 정의하자. 그리고 함수 dp(i,j,k)를 S에 속한 경로의 길이의 최솟값으로 정의하자. 다르게 쓰면 dp(i,j,k)는 노드 i에서 출발하여 1 이상 k 이하의 번호만을 가진 노드만을 거쳐 노드 j로 이동하는 최단경로의 길이를 의미한다. 단, S(i,j,k)가 공집합이라면 dp(i,j,k)는 무한대(INF)로 정의하자.

dp(i,j,0)은 그래프 G의 노드 i에서 노드 j를 직접 잇는 에지의 길이(의 최솟값)을 의미한다는 점을 확인하자. (존재하지 않는다면 그 값은 무한대일 것이다.) 또한 dp(i,j,N)은 G 위에서의 i에서 j까지의 최단거리를 의미함을 확인하자.

S(i,j,k)에 속하는 모든 경로는 (1)k를 포함하지 않는 경로와 (2)k를 포함하는 경로의 두 종류로 나눌 수 있다. 따라서, dp(i,j,k)는 (1)번 종류의 경로의 길이의 최솟값과 (2)번 종류의 경로의 길이의 최솟값, 두 값 중 작은 값임을 알 수 있다.

(1)번 종류 경로들은 k를 포함하지 않으므로, 중간 경유 노드로 k-1 이하의 index를 가지는 노드들만을 이용한다. 따라서 (1)번 종류 경로의 길이의 최솟값은 dp(i,j,k-1)과 같다.

(2)번 종류 경로들은 i에서 k까지의 부분경로와 k에서 j까지의 부분경로로 나눠 생각할 수 있다. 물론 각 부분경로들 또한 모든 중간 경유 노드의 index가 k 이하가 된다. 여기서 k는 각 부분경로의 끝점이 되었으므로, 각 부분경로들의 모든 중간 경유 노드의 index는 k-1 이하이다.

한편 (2)번 종류 경로들의 길이는 두 부분경로의 길이의 합으로 구할 수 있다. 이 값의 최솟값은 두 부분경로의 길이의 최솟값을 각각 구해 합하는 것으로 구할 수 있다. 따라서 (2)번 종류 경로의 길이의 최솟값은 dp(i,k,k-1) + dp(k,j,k-1)과 같다.

두 종류의 경로의 길이를 종합하면, dp(i,j,k)는 min(dp(i,j,k-1), dp(i,k,k-1) + dp(k,j,k-1))와 같다는 것을 알 수 있다.

이제, 위의 점화식을 이용하여 모든 i와 j에 대해 dp(i,j,N)을 계산하면 모든 노드의 쌍에 대한 최단거리를 구할 수 있다. 메모이제이션(memoization)을 이용하면 모든 가능한 3-tuple (i,j,k)에 대하여 dp(i,j,k)를 각각 한 번씩만 계산하게 되므로 시간복잡도는 O(N^3)이 된다.

3. Floyd-Warshall 알고리즘의 구현

Floyd-Warshall 알고리즘의 개념은 위와 같지만 노드 i에서 j까지의 최단거리를 실제로 함숫값을 재귀적으로 구하는 구현(top-down DP)보다 더욱 간단한 구현 방법이 존재한다. 바로 반복문을 이용한 bottom-up DP이다. 그 방법은 다음과 같다.

2차원 배열 dist[N+1][N+1]을 준비하자. 이 배열의 dist[i][j]의 값이 dp(i,j,k)들로 채워져 있을 때, dist[i][j]의 값들을 dp(i,j,k+1)로 바꾸는 것이 가능하다면 dp[i][j]의 값이 dp(i,j,0)들로 채워져있는 배열을 dp(i,j,N)들로 채워져있는 배열로 바꾸는 것 또한 가능해진다.

dp(i,j,k+1) = min(dp(i,j,k), dp(i,k+1,k) + dp(k+1,j,k)) 관계식을 이용하면 (새로운 dist[i][j]) = min(dist[i][j], dist[i][k+1] + dist[k+1][j])와 같이 표현할 수 있다는 것을 알 수 있다. 이 때, dist[i][k+1] 또는 dist[k+1][j]들은 이 과정에서 값이 변하지 않고, 그 외 dist[i][j]들은 새로운 dist[i][j]의 값을 구할 때에만 값을 참조한다는 점을 관찰하자.

위의 관찰을 이용하면, dp(i,j,k)의 값들로 채워져있는 2차원 배열의 각 성분 dist[i][j]들을 각각 순서에 상관없이 min(dist[i][j], dist[i][k+1] + dist[k+1][j])로 다시 계산하면 dp(i,j,k+1)의 값들로 채워져있는 2차원 배열을 얻게 된다는 것을 알 수 있다.

따라서, 단순하게 3중 반복문을 이용해 Floyd-Warshall 알고리즘을 구현할 수 있다. 아래는 이해를 돕기 위한 예시 C++ 소스코드이다. 직접 돌려보고 위의 내용을 한번씩 다시 확인해보자.

// NODE: 전체 노드 개수 + 1 (1-based index)
#define NODE 5
#define INF 0x3f3f3f3f
#include <iostream>
using namespace std;

// 초기 dist[i][j]: 노드 i에서 j로 바로 이어지는 에지의 길이(의 최솟값), 그러한 에지가 없다면 INF
int dist[NODE][NODE] = {
	{0, 0, 0, 0, 0},
	{0, 0, 4, 3, INF},
	{0, INF, 0, 1, INF},
	{0, INF, INF, 0, 2},
	{0, -1, 7, INF, 0 }
};

void floyd_warshall() {
	for (int k = 1; k < NODE; k++) {
		cout << "---\n";
		cout << "k: " << k << '\n';
		for (int r = 1; r < NODE; r++) {
			for (int c = 1; c < NODE; c++) {
				dist[r][c] = min(dist[r][c], dist[r][k] + dist[k][c]);
				if (dist[r][c] == INF) cout << 'X' << ' ';
				else cout << dist[r][c] << ' ';
			}
			cout << '\n';
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << "k: 0\n";
	for (int r = 1; r < NODE; r++) {
		for (int c = 1; c < NODE; c++) {
			if (dist[r][c] == INF) cout << 'X' << ' ';
			else cout << dist[r][c] << ' ';
		}
		cout << '\n';
	}

	floyd_warshall();

	cout << "---\n";
	cout << "X: i에서 j로 가는 경로가 없음";
}

4. 연습문제 추천

이제 개념 연습문제를 풀면서 Floyd-Warshall 알고리즘을 더 깊이 이해하고 PS/CP 연습문제를 풀면서 다양한 상황에서 Floyd-Warshall 알고리즘 또는 그 원리를 적용하는 연습을 해보자. ★이 붙은 문제는 꼭 풀어보고 넘어가자.

4.1. 개념 연습문제

★(1) 음의 가중치를 갖는 간선이 있는 방향그래프가 음의 사이클을 가지는 경우, 몇몇 노드 사이의 최단거리가 음의 무한대가 될 수도 있다. Floyd-Warshall 알고리즘으로 음의 무한대의 거리까지 처리하는 방법을 생각해보자. (negative cycle detection)

★(2) Floyd-Warshall 알고리즘의 과정을 변형해 각 두 노드 i와 j가 주어졌을 때 i와 j 사이의 최단거리 뿐만이 아닌 경유하는 경로를 그대로 출력하는 방법을 생각해보자. (경로 역추적)

(3) 노드가 N개이고 에지에 가중치가 있는 방향그래프에서 만약 노드 i에서 노드 j로 가는 경로가 존재한다면 그 중 "경유한 에지의 가중치들 중 가장 큰 값"의 최솟값을, 없다면 없다는 정보를 모든 노드쌍에 대하여 구하는 효율적인 방법을 생각해보자. (all-pairs minimax path problem)