다익스트라(Dijkstra) 알고리즘 완벽정리 (우선순위 큐 응용)

우리가 낯선 길을 갈 때 스마트폰에서 내비게이션 앱을 켜고 목적지를 입력하면, 단 1초도 지나지 않아 수백만 개의 도로 네트워크 속에서 '가장 빠르고 덜 막히는 최단 경로'를 화면에 그려줍니다. 도대체 컴퓨터는 그 복잡한 지도 데이터 속에서 어떻게 최단 거리를 순식간에 계산해 내는 것일까요? 이 경이로운 기술의 중심에는 1956년 천재 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 고안한 '다익스트라 알고리즘(Dijkstra Algorithm)'이 자리 잡고 있습니다. 하나의 시작점으로부터 다른 모든 정점까지의 최단 경로를 구하는 이 알고리즘은, 단순한 반복문에서 시작해 '우선순위 큐(Priority Queue)'를 만나며 완벽한 성능 최적화를 이루어냈습니다. 오늘 이 글에서는 다익스트라 알고리즘의 동작 원리와 O(E log V)라는 놀라운 시간 복잡도를 달성한 우선순위 큐의 응용 기법을 완벽하게 파헤쳐 봅니다.

1. 다익스트라 알고리즘이란? (단일 출발지 최단 경로)

다익스트라 알고리즘은 '가중치가 있는 방향/무방향 그래프'에서 특정 하나의 시작점(Source)을 기준으로, 나머지 모든 정점(Vertex)으로 가는 최소 비용(최단 거리)을 계산하는 알고리즘입니다. 내비게이션에서 '현재 내 위치(시작점)'에서 목적지까지의 경로를 찾는 원리와 정확히 일치합니다.

1-1. 다익스트라의 절대적인 전제 조건: "음수 가중치는 안 된다"

이 알고리즘을 사용하기 전에 반드시 확인해야 할 치명적인 조건이 하나 있습니다. 그래프를 구성하는 모든 간선(Edge)의 가중치가 0 또는 양수(+)여야만 한다는 것입니다. 만약 거리가 '-10km'처럼 음수(Negative Weight)인 간선이 하나라도 존재한다면, 다익스트라 알고리즘은 엉뚱한 결과를 내뱉고 실패하게 됩니다. 그 이유는 다익스트라 알고리즘이 "한 번 방문 처리가 끝나서 확정된 노드의 최단 거리는, 이후에 어떤 경로를 거치더라도 더 짧아질 수 없다"라는 탐욕적(Greedy) 전제를 깔고 동작하기 때문입니다. 음수가 존재하면 이 대전제가 박살 나게 됩니다.

2. 다익스트라의 핵심 원리: 그리디(Greedy)와 동적 계획법(DP)의 만남

다익스트라 알고리즘은 매 순간 '가장 비용이 적게 드는(가장 가까운) 노드'를 선택한다는 점에서 탐욕 알고리즘(Greedy)의 성격을 띠며, 이전에 계산해 둔 '최단 거리 테이블'을 계속해서 갱신하고 재사용한다는 점에서 동적 계획법(Dynamic Programming)의 성격을 동시에 가집니다.

2-1. 단계별 동작 메커니즘 시뮬레이션

초기화: 출발 노드를 설정하고, 출발 노드의 거리는 0으로, 나머지 모든 노드의 거리는 '무한대(Infinity)'로 설정하여 최단 거리 테이블을 만듭니다.
노드 선택: 아직 방문하지 않은 노드들 중에서, 현재 최단 거리 테이블에 기록된 값이 가장 작은(가장 가까운) 노드를 선택하여 방문 처리합니다.
인접 노드 거리 갱신(Relaxation): 선택된 노드와 연결된 이웃 노드들을 확인합니다. "현재까지 알려진 이웃 노드의 거리"보다, "방금 선택된 노드를 거쳐서 이웃 노드로 가는 거리"가 더 짧다면 최단 거리 테이블을 새로운 값으로 갱신(업데이트)합니다.
반복: 모든 노드를 방문할 때까지 2번과 3번의 과정을 끝없이 반복합니다.

이 과정을 모두 마치고 나면, 완성된 테이블에는 출발지로부터 모든 노드까지의 가장 짧은 거리가 완벽하게 기록되어 있게 됩니다.

3. 최적화의 마법: 우선순위 큐 (Priority Queue)와 힙 (Heap)

초기 다익스트라 알고리즘은 2번 단계인 '가장 거리가 짧은 노드 찾기'를 수행할 때, 매번 배열 전체를 처음부터 끝까지 순차 탐색(Linear Search)했습니다. 이 경우 노드가 $V$개라면 탐색에 $O(V)$가 걸리고, 이를 $V$번 반복하므로 총 시간 복잡도는 $O(V^2)$이 됩니다. 노드가 10만 개라면 100억 번의 연산이 필요해 시스템이 뻗어버립니다. 이를 획기적으로 개선한 것이 바로 우선순위 큐(최소 힙)의 도입입니다.

3-1. 시간 복잡도를 $O(E \log V)$로 끌어올리다

가장 짧은 거리를 가진 노드를 찾기 위해 배열을 뒤지는 대신, 거리가 갱신될 때마다 그 정보(거리, 노드 번호)를 우선순위 큐에 집어넣습니다(Push). 최소 힙(Min-Heap)으로 구성된 우선순위 큐는 내부적으로 항상 가장 거리가 짧은 노드를 루트(Top)에 유지해 줍니다.


// 우선순위 큐를 활용한 다익스트라 로직 (Java-like pseudo code)
PriorityQueue pq = new PriorityQueue<>();
pq.offer(new Node(startNode, 0));
distance[startNode] = 0;

while(!pq.isEmpty()) {
    Node current = pq.poll(); // O(log V) 만에 가장 가까운 노드 추출
    
    // 이미 처리된 적이 있는(더 짧은 거리가 기록된) 노드라면 무시
    if(distance[current.id] < current.dist) continue;
    
    // 인접 노드 거리 갱신
    for(Edge edge : adjList[current.id]) {
        int cost = distance[current.id] + edge.weight;
        if(cost < distance[edge.to]) {
            distance[edge.to] = cost;
            pq.offer(new Node(edge.to, cost)); // 갱신된 정보 큐에 삽입
        }
    }
}

우선순위 큐에서 가장 짧은 거리를 뽑아내는 데 걸리는 시간은 $O(\log V)$에 불과합니다. 각 간선($E$)마다 큐에 데이터를 넣고 빼는 연산을 수행하므로, 최종적인 시간 복잡도는 $O(E \log V)$라는 경이로운 속도로 단축됩니다. 이는 수백만 개의 간선이 얽힌 현실 세계의 도로망 데이터를 실시간으로 처리할 수 있는 강력한 원동력이 됩니다.

[핵심 요약]
1. 다익스트라(Dijkstra) 알고리즘은 하나의 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 그래프 탐색 알고리즘입니다.
2. 매 순간 가장 가까운 노드를 선택하고 거리를 갱신하는 그리디 + DP 방식을 띠며, 반드시 가중치가 양수(+)일 때만 정상 동작합니다.
3. 최소 값을 찾기 위해 우선순위 큐(Min-Heap)를 활용하면 배열 순차 탐색의 $O(V^2)$ 성능을 $O(E \log V)$로 획기적으로 끌어올릴 수 있습니다.

tech-korea