다익스트라(Dijkstra) 알고리즘은 단일 출발점에서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 1956년 Edsger Dijkstra가 고안했으며, 음수 가중치가 없는 가중치 그래프에서 작동한다. 네비게이션, 네트워크 라우팅에 활용된다.
동작 원리
그래프 (가중치):
A --1-- B --3-- D
| |
4 2
| |
C --1-- E
시작: A
dist = {A:0, B:∞, C:∞, D:∞, E:∞}
1. A 방문: B=1, C=4 갱신
2. B 방문 (최소 거리=1): D=4, E=3 갱신
3. E 방문 (최소 거리=3): C=min(4, 4)=4 (변화 없음)
4. C 방문 (최소 거리=4)
5. D 방문 (최소 거리=4)
결과: A→B:1, A→C:4, A→D:4, A→E:3
구현
python
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('D', 3), ('E', 2)],
'C': [('E', 1)],
'D': [], 'E': []
}
print(dijkstra(graph, 'A'))
시간 복잡도
- •힙 사용: O((V + E) log V)
- •배열 사용: O(V²)
한계: 음수 가중치 불가
음수 가중치가 있으면 벨만-포드를 사용.
관련 개념
- •그래프 — 다익스트라가 동작하는 자료구조
- •힙 — 우선순위 큐 구현
- •BFS — 비가중치 최단 경로
- •벨만-포드 — 음수 가중치 최단 경로
참고문헌
- •Dijkstra, E.W. (1959). A note on two problems in connexion with graphs
