다익스트라 알고리즘은 코딩테스트에서 정말 중요한 알고리즘입니다. 이 알고리즘은 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 문제를 해결하며, 오늘날 네트워크 라우팅부터 지도 앱까지 다양한 분야에서 핵심적인 역할을 하고 있습니다.
다익스트라 알고리즘의 기본 원리와 작동 방식
다익스트라 알고리즘의 핵심 아이디어는 시작점으로부터 각 정점까지의 최단 거리를 점진적으로 확장해 나가는 것입니다. 이 알고리즘은 '탐욕(Greedy)' 전략을 기반으로 하며, 항상 현재까지 발견된 가장 가까운 정점을 먼저 선택하여 최적의 결과를 보장합니다.
알고리즘의 작동 방식은 다음과 같습니다:
- 시작 정점에서 자기 자신까지의 거리는 0으로, 나머지 모든 정점까지의 거리는 무한대로 초기화합니다.
- 모든 정점을 '미방문' 상태로 표시합니다.
- 현재 정점을 시작 정점으로 설정합니다.
- 현재 정점에서 인접한 모든 정점에 대해, 현재 정점을 경유하여 도달하는 거리를 계산합니다.
- 계산된 거리가 이전에 알려진 거리보다 작으면, 해당 정점까지의 최단 거리를 업데이트합니다.
- 현재 정점을 '방문 완료'로 표시합니다.
- '미방문' 상태인 정점 중 시작 정점으로부터 가장 가까운 정점을 다음 현재 정점으로 선택합니다.
- 모든 정점이 '방문 완료' 상태가 되거나, 더 이상 도달할 수 없는 정점이 없을 때까지 4~7단계를 반복합니다.
다익스트라 알고리즘의 시간 복잡도는 우선순위 큐(Priority Queue)를 사용하면 O(E log V)로 최적화할 수 있습니다. 여기서 E는 간선의 수, V는 정점의 수입니다. 이러한 효율성 덕분에 대규모 네트워크에서도 빠르게 최단 경로를 찾을 수 있어, 현대 내비게이션 시스템과 네트워크 라우팅 프로토콜의 기반이 되었습니다.
아래는 다익스트라의 파이썬 구현입니다. 왼쪽은 다익스트라, 오른쪽은 인접리스트로 구현한 그래프입니다.
다익스트라 알고리즘의 증명
다익스트라 알고리즘이 항상 최단 경로를 찾는다는 사실은 수학적 귀납법을 통해 증명할 수 있습니다. 이 증명은 알고리즘의 핵심 특성인 '최적 부분 구조(Optimal Substructure)'와 '탐욕적 선택 속성(Greedy Choice Property)'에 기반합니다.
먼저, 다익스트라 알고리즘의 핵심 불변식(invariant)은 "각 반복마다 방문 완료된 정점들에 대한 최단 거리는 이미 확정되었다"는 것입니다. 이를 증명하기 위해 다음과 같은 귀납적 접근을 사용합니다:
기본 단계: 시작 정점 s의 최단 거리는 0으로 확정됩니다. 이는 자명합니다.
귀납 단계: k개의 정점이 방문 완료되어 그들의 최단 거리가 확정되었다고 가정합시다. 알고리즘의 다음 단계에서 선택되는 정점 u는 미방문 정점 중 시작점으로부터 가장 가까운 정점입니다. 이 정점 u의 현재 거리가 실제 최단 거리가 아니라고 가정해 봅시다.
그렇다면 u까지의 실제 최단 경로 상에는 아직 방문하지 않은 다른 정점 v가 존재해야 합니다. 그러나 모든 간선의 가중치가 음수가 아니므로, s에서 v까지의 거리는 s에서 u까지의 거리보다 크거나 같아야 합니다. 따라서 u는 여전히 미방문 정점 중 가장 가까운 정점이라는 모순이 발생합니다.
이러한 모순은 우리의 가정이 틀렸음을 의미하므로, u까지의 현재 계산된 거리는 실제 최단 거리입니다. 이 과정을 모든 정점이 방문될 때까지 반복하면, 알고리즘이 종료될 때 모든 정점에 대한 최단 거리가 올바르게 계산됩니다.
중요한 점은 이 증명이 모든 간선의 가중치가 음수가 아닐 때만 유효하다는 것입니다. 음수 가중치 간선이 존재하면 다익스트라 알고리즘은 최단 경로를 보장하지 못하며, 이런 경우 벨만-포드(Bellman-Ford) 알고리즘과 같은 다른 접근법이 필요합니다.
다익스트라 알고리즘의 최적화 기법
다익스트라 알고리즘의 효율적인 구현은 적절한 자료구조의 선택에 크게 좌우됩니다. 가장 기본적인 구현 방식은 방문하지 않은 정점 중 최소 거리를 가진 정점을 찾기 위해 배열을 사용하는 것입니다. 이 방식의 시간 복잡도는 O(V²)로, 밀집 그래프(dense graph)에서는 효율적일 수 있지만 대부분의 실제 상황에서는 최적화가 필요합니다.
가장 널리 사용되는 최적화 기법은 우선순위 큐(Priority Queue)를 활용하는 것입니다. 최소 힙(Min Heap)이나 이진 힙(Binary Heap)과 같은 자료구조를 사용하면, 최소 거리를 가진 정점을 O(log V) 시간에 찾을 수 있어 전체 알고리즘의 시간 복잡도를 O(E log V)로 개선할 수 있습니다.
코딩테스트를 목적으로 한다면 큰 의미는 없는 기법이지만 추가적인 최적화 기법으로는 다음과 같은 방법들이 있습니다:
- 양방향 검색(Bidirectional Search): 시작점과 목표점에서 동시에 검색을 시작하여 두 검색이 만나는 지점을 찾는 방식으로, 특히 단일 목적지 검색에서 효율적입니다.
- A* 알고리즘: 휴리스틱 함수를 사용하여 목표 방향으로 검색을 유도함으로써 다익스트라 알고리즘을 확장한 방법입니다.
- 줄임 그래프(Contraction Hierarchies): 전처리 단계에서 그래프를 계층화하여 실행 시간을 크게 단축시키는 기술로, 특히 도로 네트워크와 같은 대규모 그래프에서 유용합니다.
이러한 최적화 기법들은 실제 응용 환경에 따라 선택적으로 적용할 수 있으며, 특히 대규모 네트워크나 실시간 경로 탐색이 필요한 상황에서 큰 성능 향상을 가져올 수 있습니다.
다익스트라 알고리즘은 그 단순함과 효율성으로 인해 컴퓨터 과학의 기념비적인 발명 중 하나로 평가받고 있습니다. 오늘날 GPS 내비게이션, 네트워크 라우팅, 게임 개발 등 다양한 분야에서 핵심적인 역할을 담당하고 있으며, 최적화 기법들의 발전과 함께 그 활용 범위는 계속해서 확장되고 있습니다.