Floyd_Warshall Algorithm :: 플로이드-와샬 알고리즘

---

---

Floyd_Warshall Algorithm

플로이드 와샬 알고리즘

 

 

플로이드 와샬 알고리즘은 (이하 FW)  출발점에서 도착점까지의 이동하는 모든 경로 중에서 가장 짧은 것을 찾아내는 알고리즘이다. 

결론부터 말하면 시간 복잡도는 V의 세제곱이다. 즉 무지 효율이 떨어지는 알고리즘이라 할 수 있다. 

 

하지만, 다익스트라 와 같은 알고리즘과 다른 것은 이 알고리즘은 중간의 경유지를 확인하고 알 수 있다는 것인데, 

 

크게 단위는 

 

먼저 주어진 노드들의 값과 거리들을 표/행렬 형태로 정리 한다. 

각 해당 노드 자신은 0 으로 , 거리가 없는 노드는 무한대로 표시한다. 

 

이렇게 한 것을 흔히 맵이라고 하는 듯하다. 

 

맵을 완료 하면, 

 

직전 정점 행렬을 생성해야 한다. 

이것을 주로 파이라고 하는데, 

파이 테이블(행렬)은 해당 노드들의 최단 경로 작업을 하면서 나온 값들을 자동으로 저장하여 

 

최종적으로 최단 값을 산출 할 수 있게 도와주는 간접 변수 행렬같은 느낌이다. 

간접적으로 영향을 주어 해당 최단 경로 찾는 것에 도움을 주는 느낌이다. 

 

D(0)이라는 행렬이 최조, 맵핑된 행렬이라 한다면, 

파이(0)도 최초의 파이 행렬 맵핑 결과이다. 

 

여기서 이제 출발점과 도착점의 좌표를 사용자가 물어본다. 

i, j라고 한다면, 

 

처음 알고리즘은 모든 경로들을 되는 경우의 수대로 만들고 계산하기 시작한다. 

 

i -> j의 경로인데 

 

발견된, 경유지들 a, b,c가 있다 치면, 

 

i -> a-> j

i -> b-> j

i -> c ->j 

와 같은 경유지들이 생기고, 

 

FW은 이러한 경로들의 비교하기 시작하는데, 

 

여기서 진행하면서 나온 값들을 파이(a), 파이(b) , 파이(c) 테이블 식으로 저장해가며 진행하고

진행이 완료되면, 이 중에서 제일 작은 값이 저장된다. 

 

이렇게 하면, 

중간 경유지가 없는 경우 

즉, i -> j의 경우가 있을 수 있으니

 

이 값 , ij 와  ia+aj / ib+bj / ic+cj 의 값들을 비교하여 제일 작은 값 min()을 유추해 내는 것이 FW알고리즘이다.