요약

유명한 전산학자인 E. W. Dijkstra가 고안한 그래프 상의 최단경로 문제를 풀기 위한 알고리즘이다. 특징은 다음과 같다.

• 그래프 상의 하나의 정점을 기준으로, 나머지 정점들에 대한 최단 경로를 구할 때 사용된다(Single-source shortest-paths).
• 음수 가중치를 가진 사이클 경로가 존재할 경우 사용할 수 없다.
• 일반적인 알고리즘 책에 나온 구현을 따르면 O(|V|²)의 시간 복잡도로 구현이 되어있으나, 인접 리스트와 우선 순위 큐를 사용할 경우 O(|E|log|V|)의 시간 복잡도로 구현 할 수 있다. 여기서 |V|는 정점의 개수, |E|는 간선의 개수를 뜻한다.