Bellman-Ford: 음수 가중치를 견디는 완화(relaxation) 기반 최단 경로 탐색
Bellman-Ford는 그래프의 모든 정점 수만큼 반복하며 간선을 완화(relaxation)해 최단 경로를 구하는 알고리즘이다. Dijkstra와 달리 음수 가중치 간선을 허용하며, 음수 순환(negative cycle)의 존재 여부까지 탐지할 수 있다. 시간복잡도는 O(V·E)로 Dijkstra보다 느리지만 적용 범위가 넓다.
1. 개념
Bellman-Ford 알고리즘은 하나의 시작 정점(source vertex)에서 그래프 내 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 정점 개수가 V, 간선 개수가 E일 때, 모든 간선을 V-1번 반복해서 완화(relaxation)하는 방식으로 동작한다.
완화란 특정 정점까지의 현재까지 알려진 최단 거리가, 어떤 간선을 거쳐 갈 때 더 짧아진다면 그 값으로 갱신하는 연산이다. 이 과정을 그래프의 모든 간선에 대해 충분히 반복하면 모든 정점의 최단 거리가 확정된다.
Dijkstra 알고리즘과 목적은 같지만, Dijkstra는 탐욕적(greedy)으로 가장 가까운 정점을 확정해나가기 때문에 음수 가중치가 있으면 잘못된 결과를 낼 수 있다. Bellman-Ford는 이런 탐욕적 선택 없이 모든 간선을 반복적으로 검사하므로 음수 가중치에도 안전하다.
2. 왜 사용하는가
- 음수 가중치 처리: 환율 차익 거래, 비용이 아닌 이득을 표현하는 그래프 등 음수 가중치가 필요한 문제에서 Dijkstra는 쓸 수 없다.
- 음수 순환 탐지: 그래프 안에 음수 순환이 존재하면 최단 경로 자체가 정의되지 않는다(무한히 순환할수록 거리가 줄어듦). Bellman-Ford는 이를 명시적으로 탐지할 수 있다.
- 구현 단순성: 우선순위 큐(priority queue) 같은 자료구조 없이 배열과 이중 반복문만으로 구현 가능해서, 코드가 짧고 이해하기 쉽다.
3. 동작 원리
- 시작 정점의 거리를 0으로, 나머지 모든 정점의 거리를 무한대(infinity)로 초기화한다.
- 그래프의 모든 간선 (u, v, w)에 대해,
dist[u] + w < dist[v]이면dist[v] = dist[u] + w로 갱신한다. - 이 과정을 V-1번 반복한다. 최단 경로는 최대 V-1개의 간선으로 이루어지므로, V-1번 반복하면 모든 최단 거리가 확정된다.
- V-1번 반복 후 한 번 더 모든 간선을 검사한다. 이때도 완화가 일어난다면, 그래프에 음수 순환이 존재한다는 뜻이다.
핵심은 "왜 V-1번인가"이다. 최단 경로가 사이클 없이 구성된다면 최대 V개의 정점, 즉 V-1개의 간선을 지난다. 한 번의 전체 순회는 경로 길이를 1씩 늘려가며 확정시키는 효과가 있으므로, V-1번 반복하면 가능한 모든 경로 길이를 커버한다.
4. 코드 예제
from typing import List, Tuple, Dict, Optional
def bellman_ford(
num_vertices: int,
edges: List[Tuple[int, int, float]],
source: int
) -> Optional[Dict[int, float]]:
"""
num_vertices: 정점 개수 (0 ~ num_vertices-1)
edges: (u, v, weight) 형태의 방향 간선 리스트
source: 시작 정점
반환값: 정점별 최단 거리 딕셔너리. 음수 순환이 있으면 None 반환
"""
INF = float("inf")
dist = {v: INF for v in range(num_vertices)}
dist[source] = 0
# 1단계: V-1번 완화 반복
for _ in range(num_vertices - 1):
updated = False
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
# 더 이상 갱신이 없으면 조기 종료 가능 (최적화)
if not updated:
break
# 2단계: 음수 순환 탐지
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
return None # 음수 순환 존재
return dist
if __name__ == "__main__":
# 정점 0~4, 방향 그래프
edges = [
(0, 1, 4),
(0, 2, 5),
(1, 2, -3),
(2, 3, 4),
(3, 1, -6),
(1, 4, 3),
]
result = bellman_ford(num_vertices=5, edges=edges, source=0)
if result is None:
print("음수 순환이 존재하여 최단 경로를 정의할 수 없습니다.")
else:
for vertex, distance in sorted(result.items()):
print(f"정점 {vertex}까지 최단 거리: {distance}")실행 결과:
정점 0까지 최단 거리: 0
정점 1까지 최단 거리: 4
정점 2까지 최단 거리: 1
정점 3까지 최단 거리: 5
정점 4까지 최단 거리: 75. 시간 복잡도 또는 성능 특성
- 시간복잡도: O(V·E) — 바깥 반복이 V-1번, 매 반복마다 모든 간선 E개를 검사하므로 O(V·E)가 된다.
- 공간복잡도: O(V) — 거리 배열만 유지하면 되므로 정점 개수에 비례한다.
- Dijkstra와 비교: Dijkstra는 우선순위 큐를 쓰면 O((V+E)logV)로 Bellman-Ford보다 빠르지만, 음수 가중치가 없는 그래프에서만 정확하다. 밀집 그래프(dense graph)에서는 E가 V²에 가까워지므로 Bellman-Ford가 O(V³)까지 느려질 수 있다.
- 조기 종료 최적화: 한 번의 전체 순회에서 아무 갱신도 일어나지 않으면 이미 수렴한 것이므로 반복을 멈출 수 있다. 실제 데이터에서는 V-1번을 다 채우기 전에 수렴하는 경우가 많다.
6. 실무 사용 사례
- 네트워크 라우팅 프로토콜: RIP(Routing Information Protocol) 같은 거리 벡터 라우팅(distance-vector routing) 프로토콜은 Bellman-Ford의 아이디어를 기반으로 한다. 각 라우터가 이웃과 거리 정보를 교환하며 반복적으로 완화하는 방식이 유사하다.
- 환율 차익 거래(arbitrage) 탐지: 환율을 로그 스케일로 변환해 그래프의 가중치로 두면, 음수 순환의 존재가 차익 거래 기회의 존재와 대응된다.
- SPFA(Shortest Path Faster Algorithm): Bellman-Ford를 큐 기반으로 최적화한 변형으로, 실제 갱신이 필요한 정점만 큐에 넣어 처리한다. 평균적으로는 빠르지만 최악의 경우 시간복잡도는 동일하게 O(V·E)다.
7. 주의할 점
- 음수 순환이 있으면 최단 거리 자체가 정의되지 않는다. 순환을 돌수록 거리가 계속 줄어들기 때문이다. Bellman-Ford는 이를 감지만 할 수 있고, 해결(예: 최단 경로 출력)은 별도 로직이 필요하다.
- 방향 그래프와 무방향 그래프를 혼동하면 안 된다. 무방향 그래프에서 음수 가중치 간선이 하나라도 있으면, 그 간선 자체가 왕복하며 무한히 줄어드는 순환이 되므로 사실상 항상 음수 순환이 존재한다.
- 도달 불가능한 정점의 거리는 무한대로 유지된다. 코드에서
dist[u] != INF조건을 빼먹으면 오버플로나 잘못된 비교가 발생할 수 있다. - 간선 리스트 순서는 결과에 영향을 주지 않지만, 수렴 속도에는 영향을 줄 수 있다. 최종 결과는 동일하다.
8. 핵심 정리
Bellman-Ford는 모든 간선을 V-1번 반복해서 완화하는 단순한 원리로 최단 경로를 구하며, 음수 가중치를 허용하고 음수 순환까지 탐지할 수 있다는 점에서 Dijkstra보다 활용 범위가 넓다. 다만 시간복잡도 O(V·E)는 Dijkstra의 O((V+E)logV)보다 느리므로, 음수 가중치가 없는 일반적인 상황이라면 Dijkstra를 우선 고려하고, 음수 가중치나 순환 탐지가 필요할 때 Bellman-Ford를 선택하는 것이 합리적이다.