벨만-포드 알고리즘: 음수 가중치와 음수 사이클을 다루는 최단경로

음수 가중치가 있을 때 최단경로를 계산하는 방식

벨만-포드 알고리즘은 음수 가중치 간선이 포함된 그래프에서 단일 시작점 최단경로를 구한다. 다익스트라 알고리즘이 처리하지 못하는 음수 가중치를 다루며, 최단경로 자체가 정의되지 않는 음수 사이클도 탐지해 보고할 수 있다.

가중 방향 그래프 G(V, E), 가중치 w(u, v) ∈ ℤ/ℝ, 시작점 s가 주어졌을 때 각 정점 v ∈ V의 최단거리 dist[v]와 경로 복원용 pred[v]를 계산한다. 음수 사이클이 없다면 간선 완화를 |V|-1회 반복한 뒤 최단거리가 수렴한다. 이후 한 번 더 검사했을 때 완화가 가능하면, 시작점에서 도달 가능한 음수 사이클이 있다는 뜻이다.

음수 사이클이 존재하면 최단경로는 정의할 수 없으므로 탐지 후 예외 처리해야 한다.

거리 갱신과 사이클 검증이 이어지는 흐름

초기에는 dist[s]=0, 나머지 거리는 ∞, 모든 pred[·]는 ⊥로 둔다. 이어서 모든 간선 (u, v, w)를 순회하며 dist[u]+w < dist[v]이면 거리와 선행 정점을 갱신한다. 이 과정을 |V|-1회 수행하되, 어느 반복에서도 갱신이 일어나지 않으면 일찍 끝낼 수 있다.

마지막 검증 패스에서는 모든 간선을 다시 확인한다. 이때도 거리를 더 줄일 수 있으면 음수 사이클을 판정한다.

⤢✕

시간 복잡도는 O(VE)다. 조기 종료가 일어나면 경험적으로 O(kE)가 되며, k는 실제 최단경로의 최대 간선 수다. 공간 복잡도는 O(V)다. 정점 수 V가 큰 대규모 희소 그래프에서는 비용이 커질 수 있고, 음수 사이클을 만나면 실패 처리 정책도 필요하다.

파이썬 구현에서 유지할 상태

다음 구현은 Python 3.10+를 전제로 한다. 그래프는 edges = [(u, v, w), ...] 형태의 간선 리스트이며, 정점 수는 n, 인덱스는 0..n-1이라고 가정한다.

from math import inf

def bellman_ford(n: int, edges: list[tuple[int, int, float]], source: int):
    dist = [inf] * n
    pred = [-1] * n
    dist[source] = 0.0

    # |V|-1번 릴랙세이션
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != inf and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u
                updated = True
        if not updated:  # 조기 종료
            break

    # 음수 사이클 탐지
    for u, v, w in edges:
        if dist[u] != inf and dist[u] + w < dist[v]:
            raise ValueError("reachable negative-weight cycle detected")

    return dist, pred

def reconstruct_path(pred: list[int], target: int):
    path = []
    v = target
    while v != -1:
        path.append(v)
        v = pred[v]
    return list(reversed(path))

# 사용 예시
if __name__ == "__main__":
    n = 5
    edges = [
        (0, 1, 6), (0, 3, 7),
        (1, 2, 5), (1, 3, 8), (1, 4, -4),
        (2, 1, -2), (3, 2, -3), (3, 4, 9),
        (4, 0, 2), (4, 2, 7)
    ]
    dist, pred = bellman_ford(n, edges, 0)
    print("dist:", dist)
    print("path to 2:", reconstruct_path(pred, 2))

음수 사이클을 발견하면 구현은 예외를 발생시킨다. 운영 환경에서는 사이클에 연루된 정점 집합을 추출하고 로그를 남기는 처리가 권장된다. 불연결 그래프의 도달 불가 정점은 dist=∞로 유지되므로, 경로를 복원할 때 분기 처리가 필요하다.

dist와 pred는 1차원 배열로 관리하고, 간선 리스트는 배치·스트리밍 처리에 유리하다. 희소 그래프에 적합하며, 대규모 데이터에서는 간선 청크 처리와 I/O 파이프라인 설계를 고려할 수 있다. 부동소수점을 사용할 때는 정밀도 문제도 검토해야 한다. 금융이나 로그 변환에서는 ε-비교 적용이 필요하다.

릴랙세이션이 수렴하는 조건

릴랙세이션은 최단거리의 상계를 반복해서 낮추는 동적 계획법적 접근이다. 최장 경로가 최대 |V|-1개 간선을 포함한다는 성질을 이용해 수렴을 보장한다.

V-1회 수렴한 뒤에도 추가 완화가 가능하면 음수 사이클로 판단한다. 이 경우 계산을 중단하고 가중치 산정 로직, 환율 테이블, 정책 파라미터 같은 원인 데이터를 검증하는 프로세스를 시작할 수 있다.

반복 중 갱신이 없으면 조기 종료해 평균 성능을 개선한다. 반대로 음수 사이클이 있으면 pred 트리가 불안정해질 수 있으므로, 경로 복원 로직에는 사이클 검출 보호 장치가 필요하다.

음수 가중치가 문제의 일부인 곳

거리 벡터 프로토콜인 RIP 등은 벨만-포드와 같은 계열의 메커니즘을 사용한다. 지연이나 손실률을 가중치로 모델링하면 경로 선택과 장애 우회 정책을 반영할 수 있다.

환율 아비트라지 탐지에서는 환율 r(u,v)를 w(u,v) = -log r(u,v)로 변환한 뒤 음수 사이클을 찾아 무위험 차익 가능성을 식별한다. 이때 호가 시간동기, 수수료 반영 같은 데이터 품질과 수치 안정성을 함께 관리해야 한다.

차이 제약식 x_v - x_u ≤ w(u,v)는 그래프로 옮길 수 있다. 이를 통해 음수 사이클에 따른 불가능성을 검증하고 최적 시간을 계산한다. 프로젝트 관리, 타이밍 분석(EDA), 구성 관리 정책의 일관성 검증도 이 범주에 속한다.

리스크·평판 점수 그래프에서는 부정 신호를 패널티로 표현해 음수 가중치 모델에서 최단경로 기반 스코어를 전파할 수 있다. 사이클이 있으면 정책적 상한이나 클리핑을 도입하고 탐지 규칙을 운영한다.

비용과 운영상 얻는 신호

음수 가중치를 지원하고 음수 사이클을 탐지할 수 있다는 점은 대체 알고리즘과 비교되는 기능적 차이다. V=10^4, E=10^5인 희소 그래프에서는 최악 O(VE)=10^9 완화 연산이 발생한다. 조기 종료를 적용하고 k=8이라고 가정하면 ≈8×10^5 수준이다.

메모리 사용량은 O(V)다. 정점 10^6 기준으로 dist와 pred를 합산하면 double 16MB+로 수십 MB 내에서 관리할 수 있다.

음수 사이클을 명시적으로 보고하므로 실패 모드가 분명해지고, 운영 가시성과 디버깅이 수월해진다. 데이터 품질 이상 징후도 구조적으로 포착할 수 있어 사후 검증과 롤백 프로세스를 연결하기 좋다.

다익스트라와 선택 기준이 갈리는 지점

지표	벨만-포드	다익스트라
성능	O(VE), 조기 종료로 평균 개선	O(E log V) (우선순위 큐)
확장성	대규모 V에서 비용 증가, 배치·스트리밍로 보완	대규모 희소 그래프에 우수
일관성(음수 가중치)	지원, 음수 사이클 탐지	비지원(음수 간선 시 오동작)
안정성(오류/사이클)	음수 사이클 명시적 검출	검출 기능 부재
운영 편의	구현 단순, 디버깅 용이	구현 복잡도 높음(힙/우선순위 큐)

음수 가중치가 관여하는 라우팅, 금융 아비트라지, 차이 제약 검증에서는 벨만-포드가 기본 해법이 된다. 대규모 그래프에서는 비용이 커질 수 있지만, 조기 종료·스트리밍 처리·배치 분할을 통해 실무 적용 가능성을 확보할 수 있다.