다익스트라 알고리즘이란?
다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 하나의 시작 노드로부터 모든 다른 노드까지의 최단 경로를 구하는 알고리즘입니다. 1956년 에츠허르 다익스트라가 고안했으며, 내비게이션의 경로 탐색이 바로 이 알고리즘의 응용입니다.
왜 중요한가?
다익스트라는 코딩 테스트와 실무 모두에서 핵심적인 알고리즘입니다.
- •실무 활용: 내비게이션, 네트워크 라우팅, 게임 AI 길찾기
- •코딩 테스트 단골: 삼성, 카카오, 네이버 등 대기업 코딩 테스트 출제 빈도 높음
- •확장성: 벨만-포드, A* 알고리즘 등 고급 알고리즘의 기반
동작 원리
다익스트라는 그리디(Greedy) 전략을 사용합니다. 매 단계에서 현재까지 발견된 최단 거리가 가장 짧은 노드를 선택합니다.
1단계. 시작 노드의 거리를 0으로, 나머지를 무한대로 초기화합니다.
2단계. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택합니다.
3단계. 선택한 노드의 인접 노드들의 거리를 업데이트합니다.
- •새 거리 = 현재 노드 거리 + 간선 가중치
- •새 거리 < 기존 거리이면 업데이트
4단계. 모든 노드를 방문할 때까지 2~3단계를 반복합니다.
시간복잡도
| 구현 방식 | 시간복잡도 |
|---|---|
| 배열 탐색 | O(V²) |
| 우선순위 큐 (힙) | O((V + E) log V) |
노드가 많을 때는 반드시 우선순위 큐(최소 힙)를 사용해야 합니다. 우선순위 큐를 사용하면 "거리가 가장 짧은 노드"를 O(log V)에 꺼낼 수 있습니다.
핵심 제약 조건
음수 가중치가 있으면 사용할 수 없습니다. 다익스트라는 한 번 확정된 최단 거리가 변하지 않는다는 가정(그리디)에 기반합니다. 음수 가중치가 있으면 이 가정이 깨집니다.
음수 가중치가 있는 그래프에서는 벨만-포드 알고리즘을 사용합니다.
다른 최단 경로 알고리즘과 비교
| 알고리즘 | 음수 가중치 | 시간복잡도 | 용도 |
|---|---|---|---|
| 다익스트라 | 불가 | O((V+E) log V) | 단일 출발점 |
| 벨만-포드 | 가능 | O(V × E) | 단일 출발점 + 음수 |
| 플로이드-워셜 | 가능 | O(V³) | 모든 쌍 최단 경로 |
실전 팁
- •우선순위 큐에서 꺼낸 노드의 거리가 이미 확정된 거리보다 크면 건너뛰기 (시간 절약)
- •경로 복원이 필요하면 prev 배열에 이전 노드를 기록
- •2차원 격자 그래프에서도 좌표를 노드로 변환하여 적용 가능
알고노트에서 직접 확인하세요
다익스트라 알고리즘이 노드를 하나씩 확정하며 최단 거리를 갱신하는 과정을 알고노트에서 시각적으로 확인할 수 있습니다. 그래프의 가중치를 바꿔가며 어떻게 경로가 달라지는지 실험해보세요.