다익스트라 알고리즘은 음수가 아닌 간선 가중치를 가진 그래프에서 한 시작점의 최단 거리를 구하는 알고리즘이다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
원리
현재 잠정 거리가 가장 작은 정점을 선택하고 이웃으로 가는 거리를 완화한다. 우선순위 큐를 이용해 다음 정점을 효율적으로 고른다.
예시
A→B가 2, A→C가 7, B→C가 3이면 C까지의 거리는 직접 가는 7보다 B를 거치는 5가 짧다.
주의할 점
음수 간선이 있으면 거리 확정 논리가 깨질 수 있다. 중복 항목을 큐에 넣는 구현은 꺼낸 값이 현재 거리보다 오래된 것인지 검사한다.