플로이드 와샬 알고리즘

최단 경로를 구하는 알고리즘이다.

 

다익스트라 알고리즘과 비교하면 좋은데, 다익스트라 알고리즘의 경우에는 하나의 정점에서

출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

 

하지만, 만약 모든 정점에서 모든 정점으로의 최단 경로를 구한다면,

즉,

1 : N 이 아니라 N : N 의 최단 경로를 구할 때는 플로이드 와샬 알고리즘을 쓴다는 것이다.

다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 

' 거쳐가는 정점 ' 을 기준으로 알고리즘을 수행한다.

 

기본적으로 다이나믹 프로그래밍에 의거한다.

 

시간 복잡도는 O(V^3)이다.

 

즉, 특별한 경우가 아닌 이상 쓸일은 잘 없겠다.