CS학습2026년 8월 25일

Dijkstra: 우선순위 큐로 구현하는 단일 출발점 최단 경로

데이크스트라(Dijkstra) 알고리즘은 음수 가중치가 없는 그래프에서 하나의 출발점으로부터 모든 노드까지의 최단 경로를 구하는 그리디(greedy) 알고리즘이다. 우선순위 큐(priority queue)를 이용해 매 단계마다 확정되지 않은 노드 중 최소 거리 노드를 뽑아 처리하는 방식으로 동작한다. 최소 힙(min-heap)을 사용하면 O((V+E) lo

송민성5분 읽기

1. 개념

데이크스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프(weighted graph)에서 하나의 시작 노드로부터 다른 모든 노드까지의 최단 경로(shortest path)를 구하는 알고리즘이다. 1959년 에츠허르 다익스트라(Edsger Dijkstra)가 고안했으며, 모든 가중치가 0 이상이라는 조건이 성립할 때만 정확한 답을 보장한다.

핵심 아이디어는 "지금까지 확정된 최단 거리 중 가장 작은 노드를 선택하면, 그 노드로 가는 경로는 더 이상 갱신될 필요가 없다"는 그리디(greedy) 성질을 이용하는 것이다.

2. 왜 사용하는가

너비 우선 탐색(BFS)은 모든 엣지의 가중치가 동일할 때만 최단 경로를 보장한다. 가중치가 서로 다른 그래프에서 최단 경로를 구하려면 가중치를 고려한 알고리즘이 필요하다. 벨만-포드(Bellman-Ford) 알고리즘도 이 문제를 풀 수 있지만 시간복잡도가 O(VE)로 더 느리다. 데이크스트라는 음수 가중치가 없다는 조건 하에 더 빠르게 동작하므로, 조건이 맞는 대부분의 실무 상황(도로 거리, 네트워크 지연시간 등은 음수가 될 수 없다)에서 우선적으로 선택된다.

3. 동작 원리

시작 노드의 거리를 0으로, 나머지 모든 노드의 거리를 무한대(∞)로 초기화한다.
우선순위 큐에 (거리, 노드)를 넣고 시작 노드부터 꺼낸다.
큐에서 최소 거리를 가진 노드를 꺼낸다. 이미 확정된 노드라면 건너뛴다.
해당 노드의 모든 인접 노드에 대해, "현재까지의 거리 + 엣지 가중치"가 기존에 기록된 거리보다 작으면 갱신한다(이 과정을 완화, relaxation이라 부른다).
갱신된 거리와 노드를 큐에 다시 삽입한다.
큐가 빌 때까지 2~5를 반복한다.

우선순위 큐를 쓰지 않고 배열에서 매번 선형 탐색으로 최소값을 찾으면 O(V²)이 되고, 최소 힙을 쓰면 O((V+E) log V)로 개선된다. 밀집 그래프(dense graph)에서는 배열 방식이, 희소 그래프(sparse graph)에서는 힙 방식이 유리할 수 있다.

4. 코드 예제

python

import heapq
from collections import defaultdict
from typing import Dict, List, Tuple

def dijkstra(
    graph: Dict[str, List[Tuple[str, int]]],
    start: str
) -> Dict[str, float]:
    """
    graph: {노드: [(인접노드, 가중치), ...]} 형태의 인접 리스트
    start: 시작 노드
    반환값: 시작 노드로부터 각 노드까지의 최단 거리 딕셔너리
    """
    distances: Dict[str, float] = defaultdict(lambda: float("inf"))
    distances[start] = 0

    # (거리, 노드) 튜플을 힙에 저장. 힙은 첫 번째 요소 기준으로 정렬된다.
    priority_queue: List[Tuple[float, str]] = [(0, start)]
    visited = set()

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)

        # 이미 확정된 노드는 건너뛴다 (중복 삽입으로 인한 오래된 항목 처리)
        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph.get(current_node, []):
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return dict(distances)


if __name__ == "__main__":
    graph = {
        "A": [("B", 4), ("C", 1)],
        "B": [("D", 1)],
        "C": [("B", 2), ("D", 5)],
        "D": [],
    }

    result = dijkstra(graph, "A")
    print(result)
    # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

경로 자체를 복원하려면 이전 노드를 기록하는 previous 딕셔너리를 추가로 유지하면 된다.

python

def dijkstra_with_path(
    graph: Dict[str, List[Tuple[str, int]]],
    start: str,
    end: str
) -> Tuple[float, List[str]]:
    distances = defaultdict(lambda: float("inf"))
    distances[start] = 0
    previous: Dict[str, str] = {}
    priority_queue = [(0, start)]
    visited = set()

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        if current_node in visited:
            continue
        visited.add(current_node)

        if current_node == end:
            break

        for neighbor, weight in graph.get(current_node, []):
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    # 경로 복원
    path = []
    node = end
    while node in previous:
        path.append(node)
        node = previous[node]
    path.append(start)
    path.reverse()

    return distances[end], path

5. 시간 복잡도 또는 성능 특성

배열 기반 최소값 탐색: O(V²) — V는 노드 개수. 밀집 그래프에서는 오히려 효율적일 수 있다.
최소 힙 기반: O((V + E) log V) — E는 엣지 개수. 희소 그래프에서 유리하다.
피보나치 힙(Fibonacci heap) 사용 시: O(E + V log V)까지 개선 가능하지만, 구현 복잡도 대비 실무 이득이 크지 않아 거의 쓰이지 않는다.
공간 복잡도: O(V + E), 인접 리스트와 거리 배열, 우선순위 큐를 저장하는 데 필요하다.
음수 가중치가 있으면 그리디 선택이 깨져 잘못된 결과가 나올 수 있다. 이 경우 벨만-포드 알고리즘을 사용해야 한다.

6. 실무 사용 사례

지도/내비게이션 서비스: 도로 네트워크에서 두 지점 간 최단 거리 또는 최소 시간 경로를 계산한다. 실제 서비스는 A* 알고리즘처럼 휴리스틱(heuristic)을 추가해 탐색 범위를 줄이는 변형을 쓰는 경우가 많다.
네트워크 라우팅: OSPF(Open Shortest Path First) 같은 라우팅 프로토콜이 데이크스트라 알고리즘을 기반으로 최소 비용 경로를 계산한다.
게임 개발: 게임 맵에서 유닛의 이동 경로를 계산할 때 사용하며, 대규모 맵에서는 A*로 확장해 성능을 개선한다.
작업 스케줄링: 의존 관계가 있는 작업들 사이의 최소 비용 실행 순서를 구하는 데 응용된다.

7. 주의할 점

음수 가중치가 하나라도 있으면 정확한 결과를 보장하지 못한다. 이미 확정한 노드의 거리가 나중에 더 작아질 수 있기 때문이다.
우선순위 큐에 같은 노드가 여러 번 들어갈 수 있으므로, 큐에서 꺼낼 때 visited 집합으로 이미 처리된 노드인지 확인해야 한다. 이 처리를 빠뜨리면 불필요한 연산이 누적되거나 잘못된 갱신이 발생할 수 있다.
모든 노드까지의 거리가 필요한 것이 아니라 특정 목적지까지만 필요하다면, 목적지 노드를 큐에서 꺼내는 순간 조기 종료(early termination)해 성능을 아낄 수 있다.
그래프가 매우 크고 목적지가 명확하다면 A* 알고리즘처럼 휴리스틱을 활용하는 방식이 더 적합할 수 있다.
Python의 heapq는 최소 힙만 지원하므로 최대값을 다루려면 가중치에 음수를 붙이는 트릭이 필요하다는 점도 기억해두면 좋다.

8. 핵심 정리

데이크스트라 알고리즘은 음수 가중치가 없는 그래프에서 단일 출발점 최단 경로를 구하는 그리디 알고리즘이다. 매 단계 확정되지 않은 노드 중 최소 거리 노드를 선택해 인접 노드의 거리를 완화(relaxation)하는 과정을 반복한다. 우선순위 큐(최소 힙)를 사용하면 O((V+E) log V)로 동작하며, 지도 서비스나 네트워크 라우팅처럼 가중치가 항상 양수인 실무 문제에 널리 쓰인다. 음수 가중치가 있는 경우에는 벨만-포드 알고리즘을 대신 사용해야 한다.