플로이드 워셜 알고리즘이란? - 원리를 바탕으로

1. 플로이드 워셜

- 임의의 한 지점에서 다른 임의의 지점까지의 최단 거리를 구하는 알고리즘

   (모든 지점에 대해 구할 수 있음: dist[V][V])

- 중간 지점을 통해서 최단거리를 갱신하는 알고리즘

- O(N^3)의 시간 복잡도: 3중 for문

- 사용가능한 시점:  시간 초과 제한에 걸리지 않을 때( 정점의 수가 약 500개 이하정도)

- 다이나믹 프로그래밍 사용 : dist[i][j] = i에서 j 로 가는 거리라고 할 때,
i -j의 최단경로가 i-k-j라면 i-k와 k-j도 최단경로이다.

점화식: dist[i][j](최단) = dist[i][k] + dist[k][j]

- code

for k <- 1 to N
	for i <- 1 to N
	  for j <- 1 to N
		if(dist[i][j] > dist[i][k] + dist[k][j])
		dist[i][j] = dist[i][k] + idst[k][j]

2. 이해하기:

3중 for문이기만해서 쉽다고 생각하지만, 다이나믹 프로그래밍도 이해해야하고
for문의 순서에서 k가 왜 가장 위에 있는지 이해도 해야한다. 
쉽지 않은 문제다. (사실 직관적으로는 i, j, k 순서같기도 하고 헷갈리는 문제가 있다.)

그래서 이걸 알아보려고 한다.

먼저 이중배열을 시각화해서 i(행)을 출발점, j(열)을 도착점으로 해석한다.

 

 

K = 1일 떄  [i][1], [1][j]는 각각 (i,1) , (1, j)곳에서 합을 구하고 (i,j) 보다 작으면 갱신한다.

 

초록색 행이 i행,노란색 열이 j행이고, 하늘색이 k=1인 행과 열이다. 

disti][1] 과 dist[1][j]는 하늘색과 초록, 하늘색과 노랑이 만나는 위치이다. 

 

빨간색으로 체크한 두 칸의 합이 더 작다면,  빨간색 네모로 칠한 [i][j] 부분을 갱신하면 되는 진행과정인 것이다. 

 

 

 

i, j 를 모두 순회하고 나면, 아래 하늘색으로 칠한 k를 이용한 순회는 끝이 난다. 

 

그러면 우리가 중간 지점으로서 활용한 구간은 이렇게 칠해진 구간에 해당한다.

 

 

- 그런데 k가 3중 for문 가장 안쪽에 있다면? 
아직 갱신이 제대로 되지 않은 곳에서 (i,6), (6,j) 를 더해서 갱신해봤자 INF이거나 이상한 값이 나올 것이다. 

K=2일 때도 생각해보면
다음 처럼 중간지점을 고려하여 다른 노드들의 최단경로를 갱신한다.

 

이렇게 중간지점을 사용하려는 K값을 순차적으로 먼저 접근해야 다이나믹 프로그래밍의 전제, 
즉 i-j-k의 최단 거리는 i-k사이의 최단거리, k-j 사이의 최단거리의 합이다라는 것이 성립하게 된다.

 (dist = 최단거리를 담는 공간)

 

 

3. 결론

그리하여 플로이드 워셜 알고리즘은 k, i, j 순서로 접근하게 된다는 것을 완벽하게 이해하게 된다!

이제 결론적으로 이 알고리즘을 사용할 때는

- 모든 노드간의 최단 거리를 구하고 싶을 때

- 노드가 500개 이하일때

라는 것을 기억만 한다면, 적절한 때에 응용하여 잘 사용할 수 있을 것이다.