본문 바로가기
카테고리 없음

벨만-포드 알고리즘: 음수 가중치와 사이클 완벽 해결법

by kguidebook0001 2026. 4. 7.

우리는 앞서 다익스트라 알고리즘이 음수 가중치 앞에서 무력해지는 모습을 보았습니다. 하지만 현실의 세계에는 비용이 절감되거나 에너지가 충전되는 등 '음수 가중치'를 고려해야 하는 특수한 상황이 분명 존재합니다. 이러한 한계를 극복하고 그래프 내의 모든 최단 경로를 찾아내는 우직하고 강력한 해법이 바로 벨만-포드(Bellman-Ford) 알고리즘입니다. 본 포스팅에서는 벨만-포드가 어떻게 음수 가중치를 처리하며, 특히 무한 루프를 유발하는 '음수 사이클'을 어떻게 감지하는지 그 정교한 매커니즘을 파헤쳐 보겠습니다.

1. 벨만-포드 알고리즘의 철학: 모든 간선의 전수 조사

벨만-포드 알고리즘의 접근 방식은 다익스트라보다 훨씬 신중합니다. 다익스트라가 '가장 가까운 곳'을 믿고 나아가는 확신형이라면, 벨만-포드는 "모든 간선을 다 확인해보기 전까지는 믿지 않는다"는 전수 조사형입니다. 최단 경로는 사이클이 없다면 최대 $V-1$개의 간선을 가질 수 있다는 자명한 사실에 근거하여, 모든 간선을 총 $V-1$번 반복적으로 확인하며 거리를 갱신합니다.

1-1. 왜 V-1번 반복하는가?

그래프에 정점이 $V$개 있을 때, 시작점에서 특정 정점까지 가는 최단 경로는 중복 방문이 없다면 최대 $V-1$개의 간선을 지나게 됩니다. 따라서 모든 간선에 대해 거리를 갱신하는 '완화' 작업을 $V-1$번 수행하면, 이론적으로 모든 정점에 대한 최단 거리가 확정될 수밖에 없습니다. 이는 수학적으로 견고하게 증명된 벨만-포드의 정당성입니다.

2. 음수 사이클(Negative Cycle)의 감지와 처리

벨만-포드 알고리즘의 진정한 가치는 단순히 음수 간선을 처리하는 데 있지 않습니다. 바로 '음수 사이클'의 존재 여부를 명확히 판별할 수 있다는 점이 독보적입니다. 음수 사이클이란 경로를 돌면 돌수록 전체 가중치가 계속 줄어들어 최단 거리가 음의 무한대로 발산하는 구조를 말합니다. 이런 경우 컴퓨터는 영원히 최단 경로를 찾지 못하게 됩니다.

2-1. V번째 반복의 마법

벨만-포드는 $V-1$번의 반복이 끝난 후, 마지막으로 한 번 더(V번째) 모든 간선을 확인합니다. 만약 이 V번째 확인 과정에서도 거리 값이 줄어드는 노드가 발견된다면, 이는 해당 그래프에 음수 사이클이 존재한다는 움직일 수 없는 증거가 됩니다. 이러한 자가 진단 기능 덕분에 금융 시스템의 차익 거래 탐지나 복잡한 물리 엔진의 경로 검증에 벨만-포드가 필수적으로 사용됩니다.

3. 성능의 트레이드-오프와 실무적 고려사항

범용성을 얻은 대신 벨만-포드는 '속도'라는 비용을 지불했습니다. 모든 라운드마다 모든 간선을 체크하므로 시간 복잡도는 $O(VE)$가 됩니다. 간선의 수가 정점의 수에 비해 압도적으로 많은 밀집 그래프에서는 다익스트라보다 현저히 느리게 동작합니다. 따라서 개발자는 데이터의 특성을 파악하여 가중치가 양수임이 보장된다면 다익스트라를, 음수 가중치나 사이클 검증이 필요하다면 벨만-포드를 선택하는 혜안을 가져야 합니다.

최적화 기법: SPFA (Shortest Path Faster Algorithm)

벨만-포드의 성능을 개선하기 위해, 거리가 갱신된 노드들만 큐에 넣어 관리하는 SPFA 알고리즘이 자주 활용됩니다. 최악의 경우 복잡도는 벨만-포드와 동일하지만, 일반적인 경우에는 다익스트라에 근접하는 빠른 성능을 보여주며 음수 가중치까지 처리할 수 있는 매력적인 대안입니다.


# 벨만-포드 알고리즘 로직 요약
def bellman_ford(start, n, edges):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    
    # n-1번 모든 간선 확인
    for i in range(n):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                # n번째 반복에서도 갱신되면 음수 사이클 존재
                if i == n - 1:
                    return "Negative Cycle Detected"
    return dist
[벨만-포드 핵심 요약]
1. 장점: 음수 가중치 간선을 완벽히 처리하며 음수 사이클의 존재를 감지할 수 있습니다.
2. 원리: 모든 간선을 $V-1$번 순회하며 최단 거리를 확정하고, $V$번째 순회로 사이클을 판별합니다.
3. 복잡도: $O(VE)$로 다익스트라보다 느리므로 상황에 맞는 선별적 사용이 권장됩니다.

티스토리툴바