벨만-포드(Bellman-Ford) 알고리즘

개요

벨만-포드(Bellman-Ford) 알고리즘은 음수 가중치 간선이 있는 그래프에서도 시작 노드로부터의 최단 경로를 찾을 수 있는 알고리즘이다. 다익스트라와 달리 우선순위 큐를 사용하지 않고, 간선 정보를 반복적으로 갱신하는 방식으로 동작한다. 또한, **음수 사이클(Negative Cycle)**의 존재 여부도 탐지할 수 있어, 금융 모델, 네트워크 분석 등에서도 유용하게 활용된다.

---

1. 개념 및 정의

벨만-포드 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하되, 음수 간선이 존재해도 정확한 결과를 보장한다. 각 간선을 V-1번 반복하면서 최단 거리를 갱신하며, 마지막 반복에서 거리값이 줄어들 경우 음수 사이클 존재로 간주한다.

---

2. 알고리즘 동작 원리

단계	설명
1단계	시작 정점의 거리를 0, 나머지는 ∞로 초기화
2단계	전체 간선을 V-1번 반복하며 각 간선의 거리값을 갱신
3단계	(선택적) V번째 반복을 수행해 거리값이 감소하면 음수 사이클 판단

모든 간선에 대해 완전탐색을 반복하는 것이 핵심 구조이다.

---

3. 파이썬 구현 예시

def bellman_ford(graph, V, start):
    distance = [float('inf')] * V
    distance[start] = 0

    for _ in range(V - 1):
        for u, v, w in graph:
            if distance[u] != float('inf') and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w

    # 음수 사이클 존재 확인
    for u, v, w in graph:
        if distance[u] != float('inf') and distance[u] + w < distance[v]:
            return None  # 음수 사이클 존재

    return distance

graph는 (출발, 도착, 가중치)의 리스트로 구성되며, O(VE) 복잡도를 가진다.

---

4. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(VE)
공간 복잡도	O(V)

모든 간선에 대해 V-1회 반복하므로 대규모 그래프에는 느릴 수 있다.

---

5. 벨만-포드 vs 다익스트라 비교

항목	벨만-포드	다익스트라
음수 간선 처리	가능	불가능
음수 사이클 탐지	가능	불가능
시간 복잡도	O(VE)	O((V+E)logV) (우선순위 큐 사용 시)
우선순위 큐 사용	X	O
적용 상황	복잡한 가중치/음수 포함 문제	빠른 일반적인 최단경로 계산

두 알고리즘은 문제의 제약 조건에 따라 선택해야 한다.

---

6. 활용 사례

분야	활용 예시
금융 시스템	차익 거래 탐지 (음수 사이클 기반)
네트워크 보안	비용 변화 기반 침입 탐지 분석
통신 프로토콜	RIP(Routing Information Protocol) 기반 경로 탐색
경쟁 게임 AI	행동 비용이 음수일 수 있는 게임 맵 탐색
알고리즘 문제풀이	음수 간선 또는 사이클 판별 문제

음수 간선이 존재하거나, 사이클 여부 판단이 필요한 문제에 효과적이다.

---

7. 결론

벨만-포드 알고리즘은 음수 가중치 처리 및 음수 사이클 탐지가 가능한 유일한 대표 알고리즘으로, 다익스트라 알고리즘이 적용되지 않는 경우 유용하게 사용된다. 다소 느릴 수 있지만 정확성이 보장되며, 금융, 네트워크, 시뮬레이션 등 다양한 영역에서 폭넓게 활용된다. 복잡한 그래프 조건이 있는 문제를 다룰 때 반드시 이해하고 있어야 할 필수 알고리즘이다.