다익스트라 알고리즘으로 단일 출발점 최단경로 구하기

최소 거리 정점을 확정하며 경로를 넓힌다

다익스트라 알고리즘은 가중치가 비음수인 유향 또는 무향 그래프에서 하나의 출발 정점으로부터 모든 정점까지의 최단경로를 구한다. 아직 방문하지 않은 정점 가운데 현재까지 알려진 거리 dist가 가장 작은 정점을 선택한 뒤, 그 정점에서 이어지는 간선을 완화(Relaxation)하는 탐욕적 방식이다.

간선 가중치가 음수이면 이 선택은 최단경로를 보장하지 못한다. 그런 그래프에는 Bellman-Ford 등의 대안이 필요하다. 계산 결과는 각 정점까지의 최단 거리 배열과 경로 복원에 쓰는 이전 정점(predecessor) 맵으로 남는다.

인접 리스트와 이진 힙을 함께 쓰면 시간 복잡도는 O(E log V)다. 인접 행렬을 사용하면 O(V^2)가 된다.

그래프와 큐가 맡는 역할

입력은 V개의 정점과 E개의 가중 간선으로 구성되며, 유향·무향 그래프 모두에 적용할 수 있다. 모든 간선은 w ≥ 0을 가정한다. 입력 단계에서는 NaN이나 Infinity 가중치를 방어하는 로직을 두는 편이 낫다.

희소 그래프에서는 인접 리스트가 메모리와 성능 면에서 유리하다. 반대로 밀집 그래프라면 행렬 표현을 고려할 수 있다. 미확정 정점 중 최소 거리 정점을 찾는 일은 최소 힙 기반 우선순위 큐가 담당한다.

초기 상태에서는 dist[source]=0으로 두고 나머지는 무한대로 설정한다. 이전 정점 값은 predecessor=None으로 시작한다. 큐에서 정점 u를 꺼낸 뒤 인접 간선 (u, v, w)를 확인하며 더 짧은 경로가 발견되면 dist[v]와 predecessor[v]를 갱신하고 큐에 넣는다.

단일 목적지만 필요하다면 대상 정점이 큐에서 추출된 시점에 종료할 수 있다. decrease-key 대신 같은 정점을 중복으로 push하고, 방문 여부를 확인하는 방식도 구현을 단순하게 만든다. 대규모 그래프에서는 다익스트라와 2-레벨 힙, 비드라이렉션 최적화, 전처리(Contraction Hierarchies)를 결합할 수 있다.

⤢✕

라우팅부터 비용 누적 경로까지

OSPF는 SPF 계산에 이 알고리즘을 표준으로 채택한다. 링크 상태가 변하면 증분 재계산을 통해 수렴 시간을 줄일 수 있다.

도로망에서는 시간, 거리, 통행료를 가중치로 두고 최단경로를 탐색한다. A* 휴리스틱이 없는 환경에서는 기준선 알고리즘 역할을 한다. 게임과 로보틱스의 그리드 또는 네비게이션 메시에서는 균일 비용 탐색으로 쓸 수 있으며, 휴리스틱을 0으로 둔 A*와 동등하게 동작해 디버깅 기준선이 된다.

빌드 파이프라인이나 ETL DAG에서도 단계별 비용 누적이 가장 작은 경로를 결정하는 데 적용할 수 있다.

다른 최단경로 알고리즘과의 차이

알고리즘	시간 복잡도(대표)	음수 가중치 지원	목표 지향 탐색	전쌍 최단경로 적합성	비고
Dijkstra	O(E log V)	불가	불가	반복 실행 필요	단일 출발 최적
Bellman-Ford	O(VE)	가능	불가	반복 실행 필요	음수 사이클 검출 가능
A*	O(E) 평균(휴리스틱 품질 의존)	불가	가능(휴리스틱 필요)	부적합	휴리스틱 일관성 필요
BFS(무가중)	O(V+E)	해당 없음	제한적	반복 실행 필요	가중치 동일 시 사용
Floyd–Warshall	O(V^3)	가능	불가	적합	밀집 그래프, 전쌍 계산 용이

Python 구현

전제조건은 Python 3.9+와 표준 라이브러리 heapq이며, 그래프는 인접 리스트(dict of list) 형태를 가정한다.

# Python 3.9+
# 그래프 형식 예:
# G = {
#   'A': [('B', 2), ('C', 5)],
#   'B': [('C', 1)],
#   'C': []
# }

import heapq
from math import inf

def dijkstra(graph, source, target=None):
    # 음수 가중치 방어
    for u, edges in graph.items():
        for v, w in edges:
            if w < 0:
                raise ValueError("Negative edge weight detected; use Bellman-Ford")

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

    # (거리, 정점) 튜플 저장; decrease-key 대신 중복 push 허용
    pq = [(0, source)]
    visited = set()

    while pq:
        du, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)

        if target is not None and u == target:
            break  # 조기 종료

        # 인접 정점 완화
        for v, w in graph.get(u, []):
            alt = du + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heapq.heappush(pq, (alt, v))

    return dist, prev

def reconstruct_path(prev, source, target):
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        if cur == source:
            break
        cur = prev[cur]
    path.reverse()
    return path if path and path[0] == source else []

# 사용 예시
if __name__ == "__main__":
    G = {
        'A': [('B', 2), ('C', 5)],
        'B': [('C', 1), ('D', 4)],
        'C': [('D', 1)],
        'D': []
    }
    dist, prev = dijkstra(G, 'A', target='D')
    path = reconstruct_path(prev, 'A', 'D')
    print("dist[D] =", dist['D'])   # 4
    print("path =", path)           # ['A', 'B', 'C', 'D']

운영에서 확인할 조건

입력에는 정점 존재 여부, 가중치 타입과 범위, 연결성을 점검하는 검증이 필요하다. 음수 가중치가 검출되면 예외를 처리하고 대안을 안내해야 하며, 연결되지 않은 노드의 dist는 ∞로 남는다.

수백만 노드 그래프는 분할 그래프, 계층 그래프, 전처리(landmarks, CH)로 확장할 수 있다. 운영 중에는 큐 크기, 완화 횟수, 조기 종료 비율을 기록해 성능 병목을 파악한다. 탐욕 선택과 삼각부등식 하에서 최적성이 보장되며, 휴리스틱을 쓰지 않으므로 탐색 편향도 없다.

희소 그래프에서는 O(E log V) 성능을 기대할 수 있고, 단일 목적지 쿼리에 조기 종료를 적용하면 그래프 구조에 따라 평균 20~60% 개선될 수 있다. 인접 리스트와 힙 구조는 수백만 노드 그래프를 처리할 수 있으며, 외부 메모리와 분산 전처리로 추가 확장이 가능하다. 가중치 모델링이 일관되면 최적 경로를 보장하면서 예측 가능한 운영이 가능하다.