플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 그래프 이론에서 모든 정점간의 최단 경로를 찾기 위한 알고리즘이다. 이 알고리즘은 두 개의 단계로 이루어진다.

 

 

위 그래프를 예로 들어 초기 배열을 만들어보자.

 

 

그리고 각 노드를 경유지로 지정한다. 즉 지금은 인접노드만 가지고 있지만 1 → 2 → 3 이러한 경우도 계산한다는 뜻이다.

먼저 1번 노드를 경유한다고 가정하자. 그렇다면 1행은 스킵하고 2행을 진행한다.

 

 

DP[4][2] = DP[4][1] + DP[1][2] 이므로 다음과 같은 점화식을 얻을 수 있다.

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

 

위 점화식을 해석하면

• 정점 i 와 j의 최소 거리는 원래 지정되어 있던 값과 노드 k를 경유했을 때의 최소값이다.

그러므로 k도 1부터 N 까지 모두 경유해봐야한다.

이러면 각 정점에서 각 정점까지의 최소거리 DP 배열을 얻을 수 있다.

그리고 이것을 코드로 표현해보면

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

위 방법은 시간 복잡도가 O(N^3)으로 상당히 좋지 않다 때문에 제한적인 상황에서만 사용 가능하다.

• 그리고 플로이드 워셜을 그저 최단거리 저장으로 사용하지 않고, 둘을 이어주는가 안이어주는가를 확인하는 방법 또한 가능하다.
  • 그러니까, i - j 는 이어져있지 않지만 i -k - j 는 이어져있는지 아닌지를 확인할 수 있다는 의미이다.
  • 이런 식으로 응용할 수 있는 사고방식과 경험이 필요하다.