다익스트라 알고리즘으로 단일 시작점 최단 경로 계산하기

시작점 하나에서 비용을 확정하는 방식

다익스트라 알고리즘은 그래프의 시작 정점 s에서 모든 정점 v까지의 최단거리 dist[v]를 계산하고, 그 결과로 최단 경로 트리(Shortest Path Tree)를 만드는 탐욕적(greedy) 알고리즘이다. 네트워크 라우팅의 OSPF와 경로 탐색에서 표준 절차로 쓰인다.

출발 시점에는 dist[s]=0으로 두고, 나머지 정점의 거리는 dist[v]=∞로 가정한다. 이후 간선을 따라 더 작은 누적 비용이 발견될 때마다 거리를 이완(relaxation)하고 전임자 prev를 갱신한다.

이 방식의 전제는 모든 간선 가중치가 w ≥ 0이라는 점이다. 음수 간선이 섞이면 이미 확정한 거리보다 더 짧은 경로가 뒤늦게 나타날 수 있으므로 올바른 결과를 보장하지 못한다.

우선순위 큐가 거리 갱신을 이끄는 과정

미방문 정점 가운데 현재 추정거리 dist가 가장 작은 정점을 먼저 선택한다. 그 정점의 인접 간선을 이완한 뒤 거리와 전임자를 갱신하며, 선택된 정점은 최단거리가 확정되어 다시 방문할 필요가 없다.

희소 그래프에서는 인접 리스트와 최소 힙(우선순위 큐)을 함께 쓰는 구성이 적합하다. 이 경우 시간복잡도는 O(E log V)다. 인접 행렬과 배열로 구현하면 O(V^2)가 되며, 밀집 그래프이거나 V가 작을 때는 구현이 단순하다는 장점이 있다.

도달할 수 없는 정점은 dist=∞ 상태로 남는다. 같은 비용의 경로가 여러 개라면 그중 하나가 확정되며, prev를 따라가면 선택된 경로를 복원할 수 있다. 단일 목적지만 필요하다면 목표 정점이 확정된 순간 종료할 수 있다. 다중 시작점은 가상 초원천(super source)을 추가해 처리하며, 가중치가 동적으로 바뀌는 경우에는 부분 재계산 또는 재실행 전략이 필요하다.

거리 이완과 확정 상태의 흐름

⤢✕

라우팅과 경로 탐색에서의 적용

OSPF는 링크 상태 데이터베이스를 구축한 뒤 각 라우터가 자체적으로 SPT를 계산한다. 토폴로지가 바뀌면 SPF를 다시 계산하며, 링크 비용에는 대역폭·지연 기반 메트릭을 적용할 수 있다. 이때 수렴 시간과 CPU 부하의 트레이드오프를 관리해야 한다.

지도와 물류 경로에서는 도로망을 그래프로 두고 거리, 시간, 통행료 같은 비용을 기준으로 최단 경로를 계산한다. 실시간 교통 정보를 반영하려면 가중치를 다시 적용한 뒤 알고리즘을 재실행한다. 다중 목적지 배차 문제에는 반복 실행 또는 다중 소스 기법을 적용할 수 있다.

게임과 로보틱스에서는 그리드나 네비게이션 메시에서 이동 경로를 탐색한다. A*는 다익스트라 알고리즘에 휴리스틱을 더한 확장이며, 장애물이나 가중치가 동적으로 변하는 환경에서는 빠른 재계산이 요구된다.

성능과 운영상의 특성

희소 그래프에서는 O(E log V) 시간복잡도로 동작하며, 메모리가 적정하다면 수백만 간선 규모에서도 실용적으로 처리할 수 있다. 음수 가중치가 없다는 조건 아래 최적 경로를 보장하고, 결정적인 결과를 만들어 재현성도 확보한다.

구현 자체가 비교적 단순하고 관련 라이브러리 지원도 넓다. 전임자 배열을 함께 관리하면 비용뿐 아니라 실제 이동 경로를 쉽게 복원할 수 있다.

Python으로 구현한 최단 경로 계산

전제조건: Python 3.9+, 표준 라이브러리 heapq 사용. 그래프는 인접 리스트(dict: 노드 → [(이웃, 가중치)]) 구조 가정.

from heapq import heappush, heappop
from math import inf

def dijkstra(graph, start):
    # 음수 가중치 검증
    for u, edges in graph.items():
        for v, w in edges:
            if w < 0:
                raise ValueError("Dijkstra 불가: 음수 가중치 존재")

    dist = {v: inf for v in graph}
    prev = {v: None for v in graph}
    dist[start] = 0

    pq = []
    heappush(pq, (0, start))

    while pq:
        d, u = heappop(pq)
        if d > dist[u]:
            continue  # 오래된 항목 무시
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, inf):
                dist[v] = nd
                prev[v] = u
                heappush(pq, (nd, v))
    return dist, prev

def reconstruct_path(prev, target):
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return list(reversed(path))

# 사용 예시
if __name__ == "__main__":
    G = {
        "A": [("B", 2), ("C", 5)],
        "B": [("C", 1), ("D", 2)],
        "C": [("D", 3)],
        "D": [("E", 1)],
        "E": []
    }
    dist, prev = dijkstra(G, "A")
    print("dist:", dist)                 # 각 정점까지의 누적 최단거리
    print("A->E path:", reconstruct_path(prev, "E"))

인접 리스트와 최소 힙을 사용한 이 구현의 시간복잡도는 O(E log V)이며, 공간복잡도는 O(V + E)다.

그래프 표현과 우선순위 큐 선택

구현 선택	성능(시간)	확장성(메모리)	일관성(정확성)	안정성(제약 대응)	운영 편의
인접 행렬 + 배열 선택	O(V^2)	높음	최적 결과 보장	음수 간선 불가, 밀집 그래프 적합	매우 쉬움
인접 리스트 + 이진 힙(권장)	O(E log V)	중간	최적 결과 보장	음수 간선 불가, 희소 그래프 강점	보통
인접 리스트 + 피보나치 힙	O(E + V log V) 이론	중간	최적 결과 보장	구현 복잡, 상수항 큼	어려움

다익스트라 알고리즘을 선택할 때는 음수 가중치가 없는지 먼저 확인해야 한다. 조건이 맞는다면 인접 리스트와 최소 힙을 사용하고, 단일 목적지에서는 조기 종료를 적용하며, prev 배열로 경로 복원까지 함께 처리하는 구성이 실용적이다.