카테고리 없음

다익스트라 알고리즘: 우선순위 큐를 활용한 최단 경로 탐색 가이드

머니지니87 2026. 4. 10. 07:33

우리가 매일 사용하는 내비게이션이나 지도 앱이 0.1초 만에 최적의 경로를 찾아내는 비결은 무엇일까요? 그 중심에는 1956년 에츠허르 다익스트라가 고안한 다익스트라(Dijkstra) 알고리즘이 있습니다. 이 알고리즘은 특정 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 가장 대표적인 기법으로, 현대 네트워크 라우팅의 근간을 이룹니다. 본 포스팅에서는 다익스트라 알고리즘의 그리디적 설계 철학과 우선순위 큐(Priority Queue)를 통한 성능 최적화 과정을 2,500자 이상의 상세한 설명으로 파헤쳐 보겠습니다.

1. 다익스트라 알고리즘의 핵심 논리와 그리디 전략

다익스트라 알고리즘의 본질은 그리디(Greedy)와 동적 계획법(Dynamic Programming)의 절묘한 결합에 있습니다. 매 단계마다 "현재 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드"를 선택하고, 그 노드를 거쳐가는 경로가 기존에 알려진 경로보다 짧다면 정보를 갱신합니다. 이러한 과정을 완화(Relaxation)라고 부르며, 한 번 방문하여 최단 거리가 확정된 노드는 다시는 계산하지 않는다는 확신을 바탕으로 탐색을 진행합니다.

1-1. 최단 거리 테이블의 초기화와 확장

알고리즘 시작 시, 출발점의 거리는 0으로, 나머지 모든 노드의 거리는 무한(INF)으로 설정합니다. 이후 인접한 노드들을 탐색하며 dist[v] = min(dist[v], dist[u] + weight(u, v)) 공식을 적용합니다. 이 과정이 반복될수록 무한대였던 테이블의 값들은 점차 실제 최단 거리로 수렴하게 됩니다. 다익스트라의 정당성은 모든 간선의 가중치가 양수일 때 수학적으로 완벽하게 보장됩니다.

2. 우선순위 큐(Priority Queue)를 이용한 성능의 비약적 향상

단순한 배열을 사용하여 매번 최솟값을 찾는 방식은 $O(V^2)$의 복잡도를 가집니다. 이는 정점의 개수가 수만 개를 넘어서는 실제 지도 데이터에서는 치명적인 지연을 초래합니다. 이를 해결하기 위해 등장한 것이 바로 최소 힙(Min Heap) 기반의 우선순위 큐입니다. 우선순위 큐를 사용하면 최단 거리 노드를 추출하는 비용을 $O(V)$에서 $O(\log V)$로 대폭 절감할 수 있습니다.

2-1. 최적화된 복잡도: $O(E \log V)$

간선의 개수를 $E$, 정점의 개수를 $V$라고 할 때, 우선순위 큐를 적용한 다익스트라의 시간 복잡도는 $O(E \log V)$가 됩니다. 모든 간선을 한 번씩 확인하면서 동시에 힙에 넣고 빼는 연산이 수반되기 때문입니다. 이러한 효율성 덕분에 수천만 개의 노드가 얽힌 거대 도시의 교통망에서도 실시간에 가까운 응답성을 보장할 수 있습니다.

3. 다익스트라 알고리즘 사용 시의 치명적인 제약

다익스트라 알고리즘은 강력하지만 음수 가중치 간선이 존재하는 경우에는 사용할 수 없습니다. 음수 간선이 있으면 이미 방문 처리되어 '최단'이라고 확정된 노드의 거리가 나중에 다른 경로를 통해 더 줄어들 수 있는 모순이 발생하기 때문입니다. 이러한 상황에서는 뒤에서 다룰 벨만-포드 알고리즘을 선택해야 합니다. 또한, 최단 경로 자체를 출력해야 한다면 각 노드의 '직전 방문 노드(Parent)' 정보를 저장하여 역추적하는 로직이 추가로 필요합니다.

실무적인 활용 팁

실제 구현 시에는 인접 리스트 자료구조를 사용하여 간선 정보를 관리하는 것이 메모리와 속도 면에서 가장 유리합니다. 또한, 이미 처리된 거리보다 현재 큐에서 꺼낸 거리가 더 크다면 즉시 continue를 수행하여 불필요한 연산을 방지하는 'Pruning' 기술이 필수적입니다.


# 우선순위 큐를 활용한 다익스트라 Python 구현
import heapq

def dijkstra(start, graph, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)] # (비용, 노드)
    
    while pq:
        d, now = heapq.heappop(pq)
        if dist[now] < d:
            continue
        for neighbor, weight in graph[now]:
            cost = d + weight
            if cost < dist[neighbor]:
                dist[neighbor] = cost
                heapq.heappush(pq, (cost, neighbor))
    return dist
[다익스트라 알고리즘 핵심 요약]
1. 원리: 출발점에서 가장 가까운 노드를 반복적으로 선택하며 최단 경로를 갱신합니다.
2. 최적화: 우선순위 큐를 사용하여 $O(E \log V)$의 빠른 처리 속도를 달성합니다.
3. 주의: 모든 간선의 가중치가 양수일 때만 정확한 최단 경로를 보장합니다.