다익스트라 알고리즘 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

다익스트라 알고리즘이 해결하는 문제

너비 우선 탐색은 간선 수가 가장 적은 경로를 찾지만, 도로, 네트워크 링크, 항공편은 길이, 비용, 지연 시간이 제각각입니다. 다익스트라 알고리즘은 이런 가중치 그래프에서 단일 출발점 최단 경로 문제를 풉니다. 시작 노드가 주어지면 다른 모든 노드까지의 최소 총비용과 그 비용을 만드는 경로를 찾습니다.

에츠허르 다익스트라(Edsger W. Dijkstra)는 1959년 논문 "A note on two problems in connexion with graphs"에서 이 알고리즘을 발표했습니다.

핵심 아이디어

1. 시작 노드의 거리를 0으로, 나머지 노드의 거리는 모두 무한대로 설정합니다.
2. 확정되지 않은 노드 중 거리가 가장 작은 노드를 고릅니다. 이제 그 노드의 거리는 확정입니다.
3. 가중치 w인 나가는 간선 u → v마다 완화를 수행합니다. dist[u] + w < dist[v]이면 dist[v] = dist[u] + w로 갱신하고 u를 v의 부모로 기억합니다.
4. 도달 가능한 모든 노드가 확정될 때까지 2번과 3번을 반복합니다.

가장 작은 거리가 왜 확정일까요? 그 노드로 가는 다른 경로는 모두 거리가 이미 그 이상인 노드를 거쳐야 하고, 가중치가 음수가 아니면 남은 간선은 비용을 더할 뿐이기 때문입니다.

단계별 예제

간선이 A→B (4), A→C (1), C→B (2), B→D (1), C→D (5), D→E (3)인 방향 그래프입니다. A에서 시작합니다.

B는 처음에 직접 간선으로 거리 4를 얻지만 C를 거치면서 3으로 개선됩니다. E까지의 최단 경로는 A → C → B → D → E이고 총비용은 1 + 2 + 1 + 3 = 7입니다.

heapq를 사용한 파이썬 구현

파이썬의 heapq 모듈은 이진 최소 힙을 제공합니다. "키 감소" 연산 대신 거리가 개선될 때마다 새 (distance, node) 쌍을 넣고, 꺼냈을 때 오래된 쌍은 건너뜁니다. 이를 지연 삭제(lazy deletion)라고 합니다.

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

특정 목표까지의 경로를 얻으려면 부모 링크를 따라 시작 노드까지 거슬러 올라갑니다.

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

한 목표까지의 거리만 필요하다면 그 목표가 힙에서 꺼내지는 즉시 멈춰도 됩니다. 그 시점에 그 노드의 거리는 확정이기 때문입니다.

시간 복잡도와 공간 복잡도

공간 복잡도는 그래프, 거리 맵과 부모 맵, 힙을 합쳐 O(V + E)입니다.

변형과 흔한 실수

• if d > dist[u]: continue 검사를 빼먹어도 틀리지는 않지만, 오래된 항목까지 처리하게 되어 크게 느려질 수 있습니다.
• (distance, node)가 아니라 노드만 넣으면 힙의 순서가 의미를 잃습니다.
• 노드가 서로 비교할 수 없는 객체라면 거리가 같을 때 heapq가 노드끼리 비교하려다 TypeError를 일으킵니다. 고유한 카운터를 넣어 (distance, counter, node)를 사용하세요.
• A* 탐색은 우선순위에 휴리스틱을 더한 다익스트라입니다. 남은 거리를 잘 추정할 수 있으면 더 적은 노드를 탐색합니다.
• 양방향 다익스트라는 시작점과 목표점에서 동시에 탐색하다가 두 탐색이 만나면 멈춥니다.

언제 쓰는지와 실제 활용

• 라우팅: OSPF, IS-IS 같은 링크 상태 라우팅 프로토콜은 다익스트라 알고리즘에 기반한 최단 경로 우선 계산을 수행합니다.
• 지도와 내비게이션: 실제 서비스는 다익스트라 방식의 탐색 위에 전처리를 더해 사용합니다.
• 코딩 인터뷰 문제: 네트워크 지연 시간, 최저가 항공권(경유 횟수 제한), 격자에서 최소 노력 경로, 그래프에서 "최소 총비용"을 묻는 모든 문제.