벨만-포드 알고리즘 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

벨만-포드가 해결하는 문제

다익스트라 알고리즘은 빠르지만 간선 가중치가 음수가 아니어야 합니다. 환불, 환전에서의 이득, 0 아래로 내려갈 수 있는 에너지 비용처럼 가중치가 자연스럽게 음수인 문제도 있습니다. 벨만-포드는 이런 그래프를 올바르게 처리하고, 음수 사이클(계속 돌수록 비용이 한없이 줄어드는 순환 경로) 때문에 최단 경로가 존재하지 않는 경우도 알려 줍니다.

이 알고리즘의 이름은 1950년대에 각자 그 변형을 발표한 리처드 벨먼(Richard Bellman)과 레스터 포드 주니어(Lester Ford Jr.)에서 따왔습니다.

핵심 아이디어

1. 시작 노드의 거리를 0으로, 나머지는 무한대로 설정합니다.
2. V − 1번 반복합니다. 가중치 w인 모든 간선 u → v에 대해 dist[u] + w < dist[v]이면 dist[v]를 갱신합니다.
3. 모든 간선을 한 번 더 훑습니다. 그래도 거리가 개선되는 간선이 있다면 음수 사이클이 있다고 보고합니다.

왜 V − 1라운드일까요? 사이클 없는 최단 경로는 간선을 최대 V − 1개 사용합니다. k라운드가 끝나면 최단 경로가 간선 k개 이하인 모든 노드는 이미 올바른 거리를 갖게 되므로, V − 1라운드면 모든 단순 경로를 다 덮습니다.

단계별 예제

노드 4개와 간선 S→A (4), S→B (5), B→A (−3), A→C (3)로 이루어진 방향 그래프입니다. 매 라운드 간선은 이 순서대로 처리합니다.

1라운드에서 A는 먼저 S→A로 4가 되었다가 B→A를 거쳐 2로 개선되고, C는 개선된 값을 사용합니다. 다익스트라 알고리즘이라면 B를 보기 전에 A를 4로 확정해 버리는데, 바로 음수 간선이 일으키는 실수입니다.

파이썬 구현

벨만-포드는 단순한 간선 리스트 위에서 동작하므로 코드가 짧습니다.

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

가중치 −6인 간선 C → B를 추가하면 B → A → C → B 사이클의 총 가중치가 −3 + 3 − 6 = −6이 되므로, 추가 패스에서 이를 찾아냅니다.

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

dist[u] != INF 검사는 아직 도달하지 못한 노드에서 나가는 간선을 건너뜁니다. 파이썬에서는 float("inf") + w도 여전히 무한대이므로 이 검사는 주로 불필요한 작업을 줄여 줍니다. 무한대를 큰 정수로 표현하는 언어에서는 오버플로와 잘못된 갱신을 막아 줍니다.

시간 복잡도와 공간 복잡도

노드 1,000개와 간선 10,000개인 그래프에서는 완화가 최대 약 1,000만 번 일어나므로, 모든 가중치가 음수가 아니라면 다익스트라가 훨씬 빠릅니다.

변형과 흔한 실수

• 조기 종료: 한 라운드 전체에서 아무것도 바뀌지 않으면 멈춥니다. 안전하며 실제로는 훨씬 빨라지는 경우가 많습니다.
• SPFA(Shortest Path Faster Algorithm): 큐를 사용해 거리가 바뀐 노드에서 나가는 간선만 다시 완화합니다. 대체로 빠르지만 최악의 경우는 같은 O(V × E)입니다.
• 홉 제한 경로: 이전 라운드 거리의 복사본을 사용해 정확히 k라운드만 실행하면 간선 k개 이하의 최저 비용 경로를 얻습니다. "경유 k회 이내 최저가 항공권" 문제가 이렇게 풀립니다.
• 사이클 자체 찾기: 부모 맵을 유지합니다. 추가 패스에서 노드 v가 갱신되면 부모를 V번 따라가 사이클 안에 들어간 다음, 같은 노드로 돌아올 때까지 걸어가면 됩니다.

언제 쓰는지와 실제 활용

• 간선 가중치가 음수일 수 있거나 음수 사이클을 탐지해야 할 때 벨만-포드를 사용하세요. 그렇지 않다면 다익스트라를 선호합니다.
• RIP 같은 거리 벡터 라우팅 프로토콜은 분산 벨만-포드 아이디어를 사용합니다. 각 라우터가 이웃의 추정값으로 자신의 거리 추정값을 반복해서 갱신합니다.
• 환율 차익거래: 가중치를 -log(rate)로 두면 음수 사이클은 처음보다 돈이 늘어난 채로 끝나는 환전 순서가 됩니다.
• 존슨 알고리즘은 벨만-포드를 한 번 실행해 그래프의 가중치를 재조정한 뒤, 모든 노드에서 다익스트라를 실행해 모든 쌍의 최단 경로를 구합니다.
• 차분 제약(x - y <= c 같은 부등식 체계)은 최단 경로 문제로 풀 수 있으며, 음수 사이클이 있으면 해가 없다는 뜻입니다.