32. Floyd's 알고리즘(DP 방식으로 최단 경로 찾기 알고리즘)

1. 개요

 Floyd(플로이드) 알고리즘은 진짜 쉬움.

 가장 간단히 최단 경로를 찾는 알고리즘.

 간단한 가공으로 음의 가중치 역시 계산 가능. (경로 끊김 표시만 잘 처리한다면)

 3중 반복문으로 풀이.

 걸리는 시간 O(V^3)임. (엣지의 개수에 영향 받지 않으므로 정점이 적다면 사용해볼만 함)

 물론 평균 속도는 다익스트라 알고리즘이 월등함.

 

 알고리즘의 운행은 2차원 행렬을 다시 정점 수만큼 운행.

 즉, 2차원 행렬 운행 시간 * V만큼 운행 => O(V^2) * O(V) = O(V^3)

 점화식

 T[i, j] = min( T<k-1>[i, j] , T<k-1>[i, k] +T<k-1>[k, j] )

 점화식 의미

 현재까지 계산된 정점 i에서 j로 가는 시간보다 정점 k를 거쳐서 가는 길이 더 작다면 교체.

 

 즉, 계속 3개의 정점들을 비교하면 됨.

 (의문점)

 경로는 수없이 많은데 왜 3개만 비교하는 이유: DP 방식이기 때문에.

 즉, 현재 계산할 경로는 이미 이전에 계산한 결과로 비교하기 때문에.

 관념적으로는 3개의 정점만 비교하는 것이지만, 결국 V*V*V라는 것은 모든 정점을 다 비교.

 그렇기에 이전 계산의 결과는 정점 i에서 정점 j까지 오는 모든 길을 비교한 것이 됨.

2. 문제

3. 코드

3-1) 플로이드 알고리즘

3-2) 출력

     (맨 아래 행렬을 잘 조사하면 저 값이 최단 거리라는 것을 알 수 있다)

4. 정리

 플로이드 알고리즘은 정점의 크기가 작을 때, 최단 거리를 찾는데 사용된다.

 다익스트라 알고리즘과 비교하면, 

 플로이드 O(V^3) VS 다익스트라 O(ElogV)

 성능을 고려한다면 무조건 다익스트라를 쓰자.

 만약 E(엣지)의 수가 월등히 많다면 플로이드도 좋다.

 하지만 성능보다 간결한 코드와 메모리 리소스에 대한 이슈를 해결하려 한다면 플로이드도 한번 생각해보자.