모든 정점에서 모든 정점으로 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용한다.
다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다.
플로이드 와샬도 마찬가지로 기본적으로 다이나믹 프로그래밍 기술에 의거한다.
플로이드 와샬 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다.
-
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해하는 경우에 사용할 수 있는 알고리즘
-
소스코드가 다익스트라에 비해 매우 짧아 구현이 쉽다.
-
다익스트라의 경우 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 이후 해당 노드를 거쳐가는 경로를 확인하여 최단 거리 테이블을 갱신하는 방식으로 동작한다. <-> 플로이드 와샬 알고리즘 또한 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만, 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다
-
플로이드 와샬은 2차원 테이블에 최단 거리 정보를 저장한다. (모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문이다.) <-> 다익스트라는 한 지점에서 다른 지점까지의 최단 거리이기 때문에 1차원 리스트에 저장한다.