모든 쌍 최단 경로

최단 경로를 찾는 방법은 다익스트라 알고리즘을 수행하면 된다 이때 $O(n^3)$이 소요된다. n은 점의 개수이다.

플로이드-워셜 알고리즘

모든 쌍 최단 경로를 찾는 방법으로, 시간 복잡도는 다익스트라 알고리즘을 $n-1$회 사용할 때와 동일하나, 매우 간단한 방법으로 효율적이다.

다이나믹 프로그래밍 방법을 이용하여 문제를 해결하나, 해당 방법을 해결하기 위해서는 먼저 부분 문제들을 찾아야한다. 이를 위해 일단 그래프의 점의 수가 적을 때, 그래프에 3개의 점이 있는 경우 바로 각 점에 접근하는 방법과 한 점을 거쳐서 진행하는 방법 중 짧은 방법을 선택하면 된다.

해당 방법을 이용하여 부분문제들을 합쳐서 진행한다면 원래 찾고자 하는 경로를 전부 찾을 수 있다.

Pseudo Code

입력: 2차원 배열 D, 단 D[i,j]=간선(i,j)의 가중치, 만일 간선 (i,j)이 존재하지 않는다면, 
      D[i,j]= inf, 모든 i에 대하여 D[i,j]=0이다.
출력: 모든 쌍의 최단 경로의 거리를 저장한 2차원 배열 D
1. for k = 1 to n
2. 	for i=1 to n (단 i!=k)
3. 		for j=1 to n (단, j!=k,j!=i)
4. 			D[i,j] = min{D[i,k]+D[k,j],D[i,j]}

• line 1의 for 루프는 k가 1에서 n까지 변하는데, 이는 경유 가능한 점을 1부터 n까지 확장시키기 위한 것
• line2~3은 점들의 각 쌍, 1-1,1-2,1-3,...,n-n을 하나씩 고려하기 위한 루프이다. 단, i=j라든가 i=k 또는 j=k의 경우에는 수행하지 않는다.
• line4에서는 각 점의 쌍 i-j에 대해 i에서 j까지의 거리가 k를 포함하여 경유하는 경로의 거리, 즉 D[i,k]+D[k,j]와 점들만을 경유 가능한 점들로 고려하여 계산된 최단 경로의 거리 중에서 짧은 거리로 갱신한다.

수행과정

k=1 일때

k=1일때의 예제로 다른 점들도 동일하게 수행하면 된다.

시간복잡도

각 k에 대해서 모든 i,j쌍에 대해 계산되므로 총$n*n*n=n^3$회 계산이 이루어지고 각 계산은 1씩 소요되므로 $O(n^3)$이다.