플로이드-워셜 알고리즘 #플로이드 [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

플로이드-워셜 알고리즘은 그래프에서 최단 경로를 찾는 알고리즘 중의 하나이다.

특히, 모든 정점으로부터의 최단 거리를 계산 가능하기 때문에 유용하다.

2. 상세

다이나믹 프로그래밍 방식을 이용한다.

"dp[i][j][k] 를 k개 까지의 정점만을 통해 i로부터 j 까지의 최단 거리." 라고 정의하면, 점화식이 하나 만들어지는데 아래와 같다.

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

위 점화식은 i에서부터 j로 k번 정점을 통해서 가는 것과 k번 정점을 통하지 않는 것 중에 더 작은 값을 의미한다.

모든 i, j, k에 대해 위 점화식을 반복하면 모든 쌍의 최단 경로를 구할 수 있다. 따라서 시간복잡도는 O(V^3). (V는 정점의 개수)

3. 구현

그냥 위 점화식을 구현하면 된다. C++로 구현한 것은 아래와 같다.

for(int k = 0; k < N; ++k)
{
	for(int i = 0; i < N; ++i)
	{
		for(int j = 0; j < N; ++j)
		{
			dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
		}
	}
}

for문이 k, i, j 순서임을 기억하면 외우기는 매우 쉽다!

위 점화식과 약간 다른데, 2차원으로 배열의 차원을 낮춘 것이다. 마지막 k-1 열은 어차피 새로운 값으로 덮어 씌워지므로 상관이 없으므로 지운 것이다.

4. 같이 보기

최단 경로

그래프

알고리즘 프로젝트