일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- lv3
- brute-force search
- lv2
- String
- priority queue
- knapsack problem
- prefix sum
- Tree
- combinatorics
- *
- Sorting Algorithm
- minimum spanning tree
- segment tree
- floyd-warshall algorithm
- depth-first search
- disjoint-set data structure
- flood fill
- binary search algorithm
- shortest path problem
- lv4
- LV0
- breadth-first search
- longest increasing subsequence
- fenwick tree
- LV1
- greedy algorithm
- parametric search
- number theory
- bit masks
- dynamic programming
- Today
- 7
- Total
- 61,627
codedoc
플로이드, 다익스트라 알고리즘 비교 본문
정점 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 |