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

다익스트라 알고리즘은 매우 효율적이지만, 간선의 가중치가 음수인 경우 최단 경로를 보장하지 못한다는 치명적인 약점이 있습니다. 현실의 데이터 처리에서는 특정 경로 통과 시 보상을 받거나 에너지가 충전되는 등 음수 가중치가 필요한 상황이 발생할 수 있습니다. 이때 해결책으로 제시되는 것이 바로 벨만-포드(Bellman-Ford) 알고리즘입니다. 본 가이드에서는 벨만-포드의 논리 구조와 무한 루프를 유발하는 '음수 사이클' 판별법을 2,500자 이상의 상세한 설명으로 정리해 드리겠습니다.

1. 벨만-포드 알고리즘의 우직한 철학: 전수 조사

벨만-포드 알고리즘은 다익스트라처럼 현재 가장 가까운 노드를 확정하며 나아가는 방식이 아닙니다. 대신 "모든 간선을 매 라운드마다 확인한다"는 우직한 전수 조사 방식을 택합니다. 노드가 $V$개인 그래프에서 사이클이 없다면 최단 경로는 최대 $V-1$개의 간선으로 이루어진다는 원리에 기반하여, 모든 간선에 대해 거리를 갱신하는 작업을 총 $V-1$번 반복합니다.

1-1. V-1번 반복의 수학적 근거

시작점에서 어떤 노드까지의 최단 경로는 중간에 거치는 노드의 개수가 최대 $V-1$개입니다. 따라서 모든 간선을 한 번씩 훑는 작업을 $V-1$번 수행하면, 이론적으로 그래프 내의 모든 노드에 대한 최단 거리가 반드시 확정됩니다. 이러한 안정성 덕분에 벨만-포드는 음수 가중치가 섞인 복잡한 네트워크 환경에서도 신뢰할 수 있는 해답을 제공합니다.

2. 음수 사이클(Negative Cycle)의 발견과 위험성

벨만-포드 알고리즘의 독보적인 강점은 바로 음수 사이클의 존재 여부를 100% 판별할 수 있다는 점입니다. 음수 사이클이란 순환 경로를 한 바퀴 돌 때마다 전체 비용이 계속 줄어드는 구조를 말합니다. 만약 이런 사이클이 존재한다면 최단 거리는 음의 무한대로 발산하게 되어 계산 자체가 무의미해집니다.

2-1. 판별 방법: V번째 갱신 시도

$V-1$번의 반복이 끝난 후, 마지막으로 한 번 더(V번째) 모든 간선을 확인합니다. 이때 만약 거리가 또 줄어드는 노드가 발생한다면, 그 그래프에는 반드시 음수 사이클이 존재한다는 증거가 됩니다. 이는 금융 시스템의 차익 거래 탐지나 물류 네트워크의 무한 루프 방지를 위해 필수적인 검증 절차입니다.

3. 다익스트라와의 성능 비교 및 실무적 선택

벨만-포드는 음수 가중치를 처리할 수 있는 범용성을 갖춘 대신 성능 면에서는 손해를 봅니다. 시간 복잡도가 $O(VE)$로, 다익스트라보다 현저히 느립니다. 따라서 가중치가 모두 양수라면 다익스트라를, 음수 가중치가 섞여 있거나 사이클 판별이 필요하다면 벨만-포드를 선택하는 것이 공학적으로 최적인 판단입니다.

실무 응용 사례: 네트워크 라우팅 프로토콜(RIP)

벨만-포드는 과거 인터넷 라우팅의 초기 모델인 RIP(Routing Information Protocol)의 기반이 되었습니다. 각 라우터가 주변 정보를 수집하며 점진적으로 최단 경로를 갱신하는 방식이 벨만-포드의 반복 구조와 일치하기 때문입니다. 비록 현재는 더 빠른 알고리즘들이 쓰이지만, 알고리즘의 안정성과 사이클 방지 로직은 여전히 시스템 설계의 중요한 참고 자료가 됩니다.

# 벨만-포드(Bellman-Ford) Python 구현
def bellman_ford(start, n, edges):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    for i in range(n): # n번 반복
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                if i == n - 1: # n번째에도 갱신되면 음수 사이클
                    return True # 사이클 발생
    return dist

[벨만-포드 핵심 요약]
1. 장점: 다익스트라가 처리하지 못하는 음수 가중치 간선 환경에서 최단 경로를 찾습니다.
2. 기능: $V$번째 갱신 확인을 통해 경로 비용이 무한히 낮아지는 '음수 사이클'을 감지합니다.
3. 복잡도: $O(VE)$로 다익스트라보다 느리므로 상황에 맞는 선별적 사용이 필요합니다.