- Dijkstra

- 최단 경로(shortest path) 알고리즘


- 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

- distance[w] = min(distance[w], distance[u] + weight[u][w])

- 시간복잡도
  : 선형탐색일 경우 

  : 이진 힙을 이용하면 실행 시간은 O((m+n)\log n) 시간이 되고, 피보나치 힙을 통해 O(m + n \log n) 시간까지 개선할 수 있다.



'Algorithm' 카테고리의 다른 글

알고리즘 - 위상 정렬  (0) 2015.11.14
알고리즘 - 플로이드  (0) 2015.11.14
알고리즘 - 다익스트라  (0) 2015.11.14
알고리즘 - 프림  (0) 2015.11.13
알고리즘 - 크루스칼  (0) 2015.11.13
알고리즘 - 너비 우선 탐색  (0) 2015.11.13

+ Recent posts