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

Floyd-Warshall(플로이드-워샬 알고리즘)은 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘입니다. 시간 복잡도는 O(V^3)을 가지죠.

 

이 알고리즘은 음의 사이클이 없는 그래프에 대해서 모든 정점 사이의 최단거리를 구하는 것이 가능합니다. 그래프의 간선 중 음의 가중치가 존재해도 잘 실행되죠.

 

모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 됩니다. 이 2차원 배열을 이용하여 플로이드-워셜 알고리즘은 동적계획법으로 최적의 값을 계산합니다. 

 

이 알고리즘의 기본 컨셉은 정점 i, j사이 모든 경유지를 탐색해서 그 중 최단 경로를 찾아내는 것입니다. 그래프의 정점이 1~V까지이면, 경유지 K는 이 모든 정점들을 경유지로 하는 경로를 탐색합니다.

 

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

 

 

플로이드 워셜 알고리즘의 로직은 다음과 같습니다.

 

1. 2차월 배열을 만들고 그래프의 간선의 정보를 저장한다. (* 두 정점이 직접적으로 연결되어 있지 않으면 INF(무한대)값, 자기 자신으로 가는 거리는 0으로 한다.)

2. 경유지 1~V 까지 순회하여 2차원 테이블을 업데이트 한다.

 

 

위 그래프를 토대로 각 정점간의 거리를 저장한 2차원 배열을 만들어 보겠습니다.

 

초기 테이블은 위 1. 에서 지시한 부분과 같이 테이블을 초기화하였습니다.

 

경유지가 1을 지날 경우를 나타낸 2차원 테이블입니다. 그래프 상에서 1을 지나는 경로가 없기 때문에 초기 상태와 동일합니다.

 

경유지가 2를 지날 경우를 나타낸 2차원 테이블입니다. 그래프 상에서 2를 지나는 경로 (1 -> 2 -> 4) 가 (1->4) 의 경로보다 더 짧기 때문에 그래프 상에서 (1,4) 부분이 업데이트 된 것을 볼 수 있습니다.

 

그리고 최종적으로 K=4까지 경유지 탐색을 마쳤을 떄 2차원 테이블입니다. 임의의 정점 i,j까지의 최단 경로가 모두 저장되어 있는 상태입니다.

 

플로이드 워셜 알고리즘을 코드로 나타내면 다음과 같습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning(disable:4996)

const int INF = 987654321;

int main(void)
{
	int N;
	cin >> N;

	// 그래프 행렬 초기화 
	int dp[100][100];
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> dp[i][j];
			if (dp[i][j] == 0) dp[i][j] = INF;
		}
	}

	// 경유지 0~N-1까지 순회
	for (int k = 0; k < N; ++k) {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (dp[i][k] != INF && dp[k][j] != INF)
					dp[i][j] = min(dp[i][k] + dp[k][j], dp[i][j]);
			}
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
}

출처: https://engkimbs.tistory.com/371?category=688855 [새로비]