- Dijkstra
- 최단 경로(shortest path) 알고리즘
- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
- distance[w] = min(distance[w], distance[u] + weight[u][w])
- 시간복잡도
: 선형탐색일 경우
: 이진 힙을 이용하면 실행 시간은 시간이 되고, 피보나치 힙을 통해 시간까지 개선할 수 있다.
'Algorithm' 카테고리의 다른 글
알고리즘 - 위상 정렬 (0) | 2015.11.14 |
---|---|
알고리즘 - 플로이드 (0) | 2015.11.14 |
알고리즘 - 프림 (0) | 2015.11.13 |
알고리즘 - 크루스칼 (0) | 2015.11.13 |
알고리즘 - 너비 우선 탐색 (0) | 2015.11.13 |