플로이드, 다익스트라 알고리즘 비교

정점 V개 간선 E개가 있을 때

용도

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

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

공간복잡도

플로이드: 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. 그래프 간선에 음의 가중치가 존재한다: 다익스트라 알고리즘은 무조건 사용하지 못한다. 다른 최단경로 알고리즘과 비교한다.

프로그래밍 경시 상황을 바탕으로 정리한 것이다.

실제로 사용할 때는 언어간 차이나 코드 효율성의 차이로 인해 사용전략이 바뀔 수 있다.

저작자표시

'정리' 카테고리의 다른 글

문제분류 및 정리  (0)	2016.02.07
국내 프로그래밍 온라인 채점 사이트 비교  (0)	2016.02.06
BFS탐색, 다익스트라 알고리즘 비교  (0)	2016.01.17
플로이드, 다익스트라 알고리즘 비교  (1)	2016.01.17