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

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

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

그래프에서 모든 꼭지점 사이의 최단 경로의 거리를 구하는 알고리즘이다.

동적 계획법 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최소 비용을 구한다.

여기에 경유지를 기록하면 최소 비용 경로까지 구할 수 있다. 

플로이드-워셜 알고리즘은 다음과 같은 접근으로 설계되었다.

- 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.

- 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다.

이는 중첩된 부분문제로 볼 수 있으며 동적 계획법을 적용하여 효과적으로 접근할 수 있다. 한편 비용을 구하는 김에, 어떤 경유지를 지나서 최소 비용을 만들었는지 기록해두면, 최소 비용 뿐만 아니라 최소 비용 경로까지도 구할 수 있다.

의사코드

Floyd-warshall(G){
	for i <- 1 to n
		for j <- 1 to n
			d[i, j] <- Wij;
			π[i, j] <- NIL;
	
	for k <- 1 to n	// 중간 점검 집합 {1, 2, ..., k}
		for i <- 1 to n
			for j <- 1 to n
				if d[i, j] > d[i, k] + d[k, j] then
					d[i, j] = d[i, k] + d[k, j];
					π[i, j] = k;
}

PRINT-PATH(s, t, π){	// s에서 t까지 가는 경로가 존재한다는 가정하에 
	if π[s, t] = NIL then	// 최단 경로상의 중간 노드들(s와 t 자신은 제외)을 출력
		return;
	PRINT-PATH(s, π[s, t], t);
	print(π[s, t]);
	PRINT-PATH(π[s, t], t);
}

시간복잡도 : O(n^3)

예제를 통해 구현 : 소스 코드(Java)