다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra's algorithm) 또는 데이크스트라 알고리즘은 가중치가 있는 그래프에서 한 정점(vertex)에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 1956년 네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라가 고안했다.
이 알고리즘은 경로의 각 간선(edge) 가중치가 음수가 아닐 때만 정상적으로 동작한다. 따라서 현실 세계의 도로 네트워크(내비게이션)나 컴퓨터 네트워크의 라우팅 프로토콜(OSPF 등)처럼 거리가 음수일 수 없는 상황에서 최단 경로를 찾는 데 널리 사용된다.
개요
다익스트라 알고리즘은 그리디 알고리즘의 일종으로, 매 단계마다 현재까지 계산된 최단 거리를 바탕으로 방문하지 않은 노드 중 가장 가까운 노드를 선택하고, 해당 노드를 거쳐가는 새로운 경로의 거리를 계산하여 기존의 거리보다 짧을 경우 갱신하는 방식으로 동작한다.
알고리즘은 출발점으로부터 각 노드까지의 최단 거리를 저장하는 배열(또는 리스트)을 유지하며, 이 값을 점차적으로 개선해 나간다. 모든 노드를 방문하면 알고리즘이 종료되고, 출발점에서 모든 노드까지의 최단 경로가 완성된다.
알고리즘의 동작 원리
- 초기화:
- 출발 노드의 거리는 0으로 설정하고, 나머지 모든 노드의 거리는 무한대(∞)로 초기화한다.
- 모든 노드를 '미방문' 상태로 둔다.
- '미방문' 노드들만을 관리하는 집합(또는 우선순위 큐)을 준비한다.
- 반복:
- '미방문' 노드 중에서 현재까지 계산된 거리가 가장 짧은 노드를 선택하여 현재 노드로 지정한다.
- 현재 노드를 '방문 완료' 상태로 변경한다.
- 현재 노드와 인접한 모든 '미방문' 노드에 대해, 현재 노드를 거쳐가는 경로의 거리를 계산한다.
- `(현재 노드까지의 거리 + 인접 노드까지의 간선 가중치)`
- 계산된 거리가 해당 인접 노드의 기존 거리 값보다 작으면, 거리 값을 새로운 값으로 갱신한다.
- 모든 노드가 '방문 완료' 상태가 되거나, '미방문' 노드 집합이 빌 때까지 위 과정을 반복한다.
시간 복잡도
다익스트라 알고리즘의 시간 복잡도는 '미방문' 노드 중 최단 거리 노드를 어떻게 찾느냐에 따라 달라진다.
- 선형 탐색: 모든 노드를 순차적으로 확인하여 최단 거리 노드를 찾는 방식. 시간 복잡도는 O(V²)이다 (V는 정점의 개수).
- 우선순위 큐 (Priority Queue): 힙 자료구조 등을 이용한 우선순위 큐를 사용하면 최단 거리 노드를 더 효율적으로 찾을 수 있다. 이때의 시간 복잡도는 O((E + V) log V) 또는 간선이 충분히 많을 경우 O(E log V)이다 (E는 간선의 개수). 현대의 대부분 구현은 우선순위 큐를 사용한다.
특징 및 한계
- 장점: 개념이 비교적 간단하며, 그리디 접근법으로 최적의 해를 보장한다.
- 한계: 간선의 가중치가 음수인 그래프에서는 올바른 최단 경로를 찾지 못할 수 있다. 음수 가중치가 포함된 그래프에서는 벨먼-포드 알고리즘을 사용해야 한다.
응용 분야
- 내비게이션 시스템: GPS 등에서 두 지점 간의 최단 운전 경로를 계산하는 데 사용된다.
- 네트워크 라우팅: OSPF, IS-IS와 같은 라우팅 프로토콜에서 데이터 패킷이 이동할 최적의 경로를 결정한다.
- 물류 및 공급망 관리: 운송 비용과 시간을 최소화하는 배송 경로를 최적화한다.
- 게임 개발: 인공지능 캐릭터가 맵 상에서 목적지까지 가장 빠르게 이동하는 경로를 찾는 데 활용된다.