[JS] - 플로이드 , 다익스트라 알고리즘

플로이드: 각 정점간 최단경로를 구할 때

다익스트라: 시작점으로 부터 나머지 정점까지 최단거리를 구할 때

공간복잡도

플로이드: V^2
다익스트라: V^2(인접행렬), V+E(인접리스트)

시간복잡도

플로이드: V^3
다익스트라: V^2(인접행렬), ElogV(인접리스트 + 우선순위 큐) -> VlogV (피보나치힙이나 이진검색트리 사용, 하지만 이런 자료구조들은 상수가 커서 잘 안씀.)

장단점

• 플로이드 알고리즘 소스가 훨씬 더 간결하다.

• 플로이드 알고리즘은 간선 수가 많으면 다익스트라 알고리즘보다 빠를 수가 있음.

• 시작점으로부터 각 정점까지 최단거리만 구해도 될 때, 보통 다익스트라 알고리즘이 압도적으로 빠름.

• 그래프에 음의 가중치 간선이 있으면(물론 음의 싸이클은 없어야 한다) 다익스트라 알고리즘은 못 쓰지만 플로이드 알고리즘은 사용할 수 있다.

사용전략

1. 정점간 최단경로를 모두 구해야 한다.
   1-1. 간선이 매우 많다(V^2=E): 플로이드 알고리즘이 우수함.
   1-2. 간선이 많지 않다: 플로이드 알고리즘은 V^3, 다익스트라 알고리즘은 VElogV 경우에 따라 다름
2. 시작점으로부터 나머지 정점까지 최단거리만 구해도 된다.
   2-1. 간선이 매우 많다(V^2=E): 인접행렬을 이용하는 다익스트라 알고리즘을 사용한다.
   2-2. 간선이 많지 않다: 인접리스트를 이용하는 다익스트라 알고리즘을 사용한다.
3. 최단경로를 구하는 것이 전체 시간에 큰 영향을 끼치지 않는다: 소스가 간결한 플로이드 알고리즘을 사용한다.
4. 그래프 간선에 음의 가중치가 존재한다: 다익스트라 알고리즘은 무조건 사용하지 못한다. 다른 최단경로 알고리즘과 비교한다.