벨만-포드 알고리즘 (Dijkstra를 넘어서는 그래프 알고리즘)

벨만-포드 알고리즘이란?

벨만-포드(Bellman-Ford) 알고리즘은
음수 가중치 간선이 포함된 그래프에서도
한 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.

 

다른 정리로는,

Dijkstra는 음수 가중치 간선이 있으면 작동하지 않습니다.
반면 Bellman-Ford 알고리즘은
음수 간선이 존재하는 그래프에서도 최단 경로를 안전하게 구할 수 있는 알고리즘입니다.

또한, 사이클 판별 기능까지 갖춘 다목적 알고리즘입니다.

---

언제 Bellman-Ford를 써야 할까?

조건	설명
그래프 유형	방향 또는 무방향 그래프 (음수 간선 포함)
가중치	음수/양수 모두 허용
목적	단일 출발점 기준 최단 거리
사이클	음수 사이클도 탐지 가능

실전 예시

• 환율 우회 이익(Arbitrage) 계산
• 일정/자원 배분 시 마이너스 패널티가 존재하는 경우
• 비용 계산에서 "이득"이 음수로 표현되는 상황

---

벨만-포드 알고리즘의 핵심 원리

"모든 간선을 최대 (노드 수 – 1)번 반복하며 거리 갱신"

• 모든 경로의 최단 거리는 "노드 수 – 1"개의 간선을 넘지 않음
• 각 단계에서, 모든 간선을 검사해서 더 짧은 경로가 있으면 갱신
• 이를 반복하여 최단 거리 보장

---

알고리즘 흐름

 

1. 시작점의 거리는 0, 나머지는 무한대로 초기화
2. (노드 수 – 1)번 반복:
   • 모든 간선을 확인
   • 거리[u] + 가중치 < 거리[v]이면, 거리[v]를 갱신
3. 한 번 더 반복해서 갱신되는 간선이 있으면?
   • → 음수 사이클 존재!

노드 수: 3  
간선:  
1 → 2 (가중치: 4)  
1 → 3 (가중치: 5)  
2 → 3 (가중치: -6)

 

 

• 1 → 2 → 3 = 4 + (-6) = -2
• 1 → 3 = 5 (기존보다 느림)
• 반복하면서 더 빠른 경로로 "거리 갱신" → 이게 Relaxation

---

 

Python 구현 (그래프는 간선 리스트 사용)

def bellman_ford(n, edges, start):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0

    # 1. (n-1)번 반복
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 2. 음수 사이클 판별
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError("음수 사이클이 존재합니다")

    return dist

 

예시 간선 리스트

edges = [
    (1, 2, 4),
    (1, 3, 5),
    (2, 3, -6),
    (3, 4, 2)
]

---

왜 (노드 수 – 1)번만 반복해도 될까?

최단 경로에 중복 방문이 없는 한,
최대로 방문할 수 있는 노드는 (노드 수 – 1)개이기 때문입니다.

즉, 만약 n개의 노드가 있는데

• 1 → 2 → 3 → ... → n의 최단 경로를 찾을 때
• 최대 n-1개의 간선만 사용하면 되므로,
  n-1회 반복이면 모든 경우를 보장합니다.

---

음수 사이클이란?

출발점으로 돌아올 때마다 경로의 총 비용이 계속 줄어드는(음수 누적) 사이클

예:
A → B → C → A
(각 간선의 합이 –3이라면, 무한히 돌면 –∞로 내려갈 수 있음)

• 현실에서는 환율 차익 거래(arbitrage)처럼 무한 이득이 가능한 상황
• 벨만-포드로 음수 사이클을 정확히 감지할 수 있음

---

시간복잡도

연산	복잡도
모든 간선 확인	O(E)
(노드 수 – 1)번 반복	O(V)
총합	O(VE)

 

• E: 간선 수
• V: 노드 수
• (다익스트라보다 느리지만, 음수 가중치까지 안전하게 처리 가능)

---

다익스트라와 벨만-포드 비교

항목	다익스트라	벨만-포드
음수 가중치	❌ X	✅ O
음수 사이클 판별	❌ X	✅ O
시간복잡도	O(E log V)	O(VE)
실전 용도	가중치 0 이상	음수 가능/싸이클 탐지 필요 시

---

 

정리

 

• 벨만-포드 알고리즘은
  • 음수 가중치도 안전하게 처리
  • (노드 – 1)번 모든 간선을 반복하며 최단거리 확정
  • 한 번 더 반복해서 음수 사이클 유무를 판별
• 다익스트라의 한계를 극복하는 유일한 단일 출발점 최단경로 알고리즘
• 실전에서는 간선 리스트 기반 구현이 가장 적합