[Daily morning study] 다익스트라와 벨만-포드 최단 경로 알고리즘

#daily morning study

Image


최단 경로 문제

그래프에서 두 정점 사이의 가중치 합이 최소인 경로를 찾는 문제다. 대표적인 알고리즘으로 다익스트라(Dijkstra)와 벨만-포드(Bellman-Ford)가 있으며, 각각 적용 가능한 조건과 시간 복잡도가 다르다.


다익스트라 알고리즘

핵심 아이디어

탐욕적(Greedy) 접근을 사용한다. 아직 방문하지 않은 정점 중 현재까지의 거리가 가장 짧은 정점을 선택해 인접한 정점들의 거리를 갱신한다. 음수 가중치가 없을 때만 올바르게 동작한다.

동작 원리

  1. 시작 정점의 거리를 0, 나머지를 무한대(∞)로 초기화
  2. 미방문 정점 중 거리 최솟값을 가진 정점 u 선택
  3. u의 모든 인접 정점 v에 대해 dist[u] + weight(u, v) < dist[v]이면 거리 갱신 (relax)
  4. u를 방문 완료로 표시
  5. 모든 정점을 방문할 때까지 2~4 반복

한 번 방문 완료된 정점의 거리는 최종값이다. 음수 가중치가 있으면 이 보장이 깨진다.

우선순위 큐를 이용한 구현

단순 배열로 최솟값을 선형 탐색하면 O(V²)이지만, 최소 힙(Min-Heap)을 사용하면 O((V + E) log V)로 개선된다.

import heapq

def dijkstra(graph, start, n):
    # graph[u] = [(v, weight), ...]
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (distance, vertex)

    while heap:
        d, u = heapq.heappop(heap)

        # 이미 더 짧은 경로로 처리됐으면 스킵
        if d > dist[u]:
            continue

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist

복잡도

구현 방식시간 복잡도
단순 배열 (선형 탐색)O(V²)
이진 힙 (heapq)O((V + E) log V)
피보나치 힙O(V log V + E)

밀집 그래프(E ≈ V²)에서는 배열 방식이, 희소 그래프에서는 힙 방식이 유리하다.


벨만-포드 알고리즘

핵심 아이디어

동적 계획법(DP) 접근을 사용한다. 모든 간선을 V-1번 반복해서 완화(relax)하면, 최대 V-1개의 간선을 거치는 최단 경로를 모두 구할 수 있다. 음수 가중치 간선을 허용하며, 음수 사이클 존재 여부도 감지할 수 있다.

동작 원리

  1. 시작 정점의 거리를 0, 나머지를 ∞로 초기화
  2. 모든 간선 (u, v, w)에 대해 dist[u] + w < dist[v]이면 dist[v] 갱신
  3. 2를 V-1번 반복 (정점 수 - 1)
  4. V번째 반복에서도 갱신이 발생하면 음수 사이클이 존재

V-1번 반복 이유: V개 정점의 최단 경로에서 간선은 최대 V-1개를 사용한다. 각 반복마다 적어도 하나의 간선을 더 고려하므로 V-1번이면 충분하다.

구현

def bellman_ford(edges, start, n):
    # edges = [(u, v, weight), ...]
    dist = [float('inf')] * n
    dist[start] = 0

    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        # 더 이상 갱신이 없으면 조기 종료
        if not updated:
            break

    # 음수 사이클 감지
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # 음수 사이클 존재

    return dist

복잡도

  • 시간: O(V × E)
  • 공간: O(V)

두 알고리즘 비교

항목다익스트라벨만-포드
음수 가중치불가가능
음수 사이클 감지불가가능
시간 복잡도O((V+E) log V)O(V·E)
단일 출발 최단 경로가능가능
접근 방식그리디동적 계획법

음수 가중치가 있으면 다익스트라가 왜 틀리는가

예시 그래프:

  • A → B: 2
  • A → C: 3
  • C → B: -2

다익스트라는 A에서 B로 거리 2를 확정 후 C를 처리한다. 그러나 A → C → B = 3 + (-2) = 1이 더 짧다. B가 이미 방문 완료로 표시됐기 때문에 더 짧은 경로를 무시한다. 벨만-포드는 모든 간선을 반복적으로 완화하므로 이 경우도 올바른 결과를 낸다.


활용 사례

다익스트라

  • 네비게이션 최단 경로 (도로 가중치는 항상 양수)
  • 네트워크 라우팅 프로토콜 (OSPF)
  • 게임 맵의 경로 탐색

벨만-포드

  • 금융 차익 거래 감지 (음수 사이클 = 차익 기회)
  • BGP 라우팅에서 거리 벡터 계산
  • 네트워크 비용 모델에 음수 가중치가 포함될 때

SSSP vs APSP

  • SSSP (Single-Source Shortest Path): 단일 출발지 → 모든 정점. 다익스트라, 벨만-포드가 여기에 해당.
  • APSP (All-Pairs Shortest Path): 모든 쌍의 최단 거리. 플로이드-워셜(O(V³))이 대표적.

SSSP를 V번 실행해도 APSP를 구할 수 있지만, 플로이드-워셜이 구현이 단순하고 밀집 그래프에서 실용적이다.


경로 복원

최단 거리뿐 아니라 경로 자체가 필요할 때 parent 배열을 함께 관리한다.

# 다익스트라에 경로 복원 추가
parent = [-1] * n

# relax 시점에 parent 갱신
if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    parent[v] = u
    heapq.heappush(heap, (dist[v], v))

# 경로 추적
def get_path(parent, target):
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    return path[::-1]