[동적계획알고리즘] 플로이드-워셜 알고리즘

---

그래프의 모든 정점 사이의 최단 거리를 구하는 것이 목표인 알고리즘이다. 다익스트라 알고리즘은 시작 정점에서 모든 정점의 최단 경로를 구하는 알고리즘인데 반해, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점의 경로르 구하는 알고리즘이다. (와 무슨 소리지)

 

이렇게 말하면 전혀 알지 못할 알고리즘이다. 그런데 생각해보면 정말 간단하다. 동적계획 알고리즘의 기본 틀을 그래프에 적용한 것이다.

 

우리가 찾고자 하는 것은 모든 노드를 잇는 최단 경로이다. 그런데 노드에서 노드로 가는 경로는 여러 개의 노드를 거쳐 갈 수도 있다. 당연함. 그렇게 생긴 그래프임. 

 

그렇다면 경유해서 가는 게 비용이 적은지, 직행으로 가는 게 비용이 적은지 고려하면 비교가 가능하다.

 

알고리즘)

allPairShortest
input : 2차원 배열 D
output : 모든 노드의 최단 경로 거리를 저장한 2차원 배열 D
// 간선이 없다면 infinite / 자기 자신을 향해서는 D=0
1. for k=1 to n
2. 	for i=1 to n
3. 		for j=1 to n
4. 			D[i,j] = min{ D[i,k] + D[k,j] , D[i,j] }
// (i,j)에는 경유한 경로와 직행인 경로 중 min 값을 저장하게 된다.

초기의 D는 각 노드에서 갈 수 있는 경로의 비용을 저장한 배열로 나타난다.

 

 

 

 

각 k에 대해서 모든 i,j쌍이 계산돼야 한다. 그래서 n*n*n 회 계산이 이뤄진다.

O(nnn)