플로이드 워샬 알고리즘

1. 모든 쌍 최단경로

💁🏻‍♀️ 다음 각 정점 사이의 최단 경로는 얼마일까❓

• brute-force 접근 방법

  • 한 정점에서 다른 정점으로의 모든 경로를 구한 뒤, 그들 중에서 최단 경로를 찾는다.
  • 정점 i에서 출발하여 처음에는 도착할 수 있는 정점의 가지 수는 n-2개이고, 그 중에 하나를 선택하면, 그 다음에 도착할 수 있는 정점의 가지 수는 n-3개 이고, 이렇게 계속 계산하면, 총 경로의 개수는 (n-2)(n-3) … 1 = (n-2)! 이 된다. ⇒ 비효율적!

• 이 문제를 해결하려면, 각 정점을 시작 정점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행하면 된다.

• 플로이드의 알고리즘 시간복잡도는 O($n^3$)으로 다익스트라의 시간복잡도와 동일하다.

• 그러나 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다.

💁🏻‍♀️ 모든 쌍 최단 경로알고리즘

D[i][j] = 정점i에서 정점 j로의 최소비용
AllPairsShortest(D[][])
	For k in 1 → n
		For i in 1 → n (단, i != k)
			For j in 1 → n (단, i != k, i != j)
				D[i][j] ← min(D[i][k] + D[k][j] , D[i][j])

• Line 1의 for-루프는 k가 1에서 n까지 변하는데, 이는 경유 가능한 정점을 1부터 n까지 확장 하는 것
• Line 2~3 : 점들의 각 쌍을 하나씩 고려하기 위한 루프
• Line 4 : 각 정점의 쌍 i-j에 대해 i에서 j까지의 거리가 k를 포함하여 경유하는 경로의 거리, 즉, D[i][k] + D[k][j]와 정점 {1, 2, … k-1} 만을 경유 가능한 점들로 고려하여 계산된 최단 경로의 거리 D[i][j] 가 짧은지를 결정하여 D[i][j]를 갱신한다.

2. 플로이드 워샬 알고리즘 수행 과정

💁🏻‍♀️ 배열 D의 원소들이 k가 1부터 5까지 증가함에 따라서 갱신되는 것을 살펴보자.

---

• 시간복잡도
  • 플로이드 알고리즘의 시간복잡도는 위의 예제처럼 보았듯이 각 k에 대해서 모든 i, j쌍에 대해 계산되므로 $n * n * n = n^3$ 회 계산이 이루어지고, 각 계산은 O(1) 시간이 걸린다.
  • 따라서 시간복잡도는 $O(n^3)$이다.