벨만 포드 알고리즘: 음수 간선과 음수 사이클을 구분하기
벨만 포드 알고리즘은 음수 간선이 있는 그래프에서도 한 출발점의 최단 거리를 구할 수 있다. 다만 출발점에서 도달 가능한 음수 사이클을 거쳐 목적지로 갈 수 있다면 비용을 계속 줄일 수 있어 그 목적지의 유한한 최단 거리는 존재하지 않는다.
음수 간선을 포함한 경로도 완화할 수 있으며 음수 순환 여부는 별도로 판단한다.
모든 간선을 반복해서 완화한다
dist[u]+w가 dist[v]보다 작으면 v를 갱신한다. 이 작업을 모든 간선에 대해 반복한다. 음수 사이클이 없는 최단 경로는 정점을 반복하지 않는 형태로 선택할 수 있고, 따라서 간선 수가 많아야 V-1이다. V-1회 전체 완화를 하면 필요한 개선이 전달된다.
def bellman_ford(vertex_count, edges, source):
distance = [float("inf")] * vertex_count
distance[source] = 0
for _ in range(vertex_count - 1):
changed = False
for start, end, cost in edges:
if distance[start] != float("inf"):
candidate = distance[start] + cost
if candidate < distance[end]:
distance[end] = candidate
changed = True
if not changed:
break
for start, end, cost in edges:
if distance[start] != float("inf") and distance[start] + cost < distance[end]:
raise ValueError("Reachable negative cycle")
return distance
간선 순서에 따라 한 회 안에서 여러 단계의 개선이 전달될 수도 있다. 그렇다고 V-1회 상한의 근거가 없어지는 것은 아니다. 별도 배열로 이전 회차를 읽는 구현은 “간선 k개 이하의 경로”라는 의미가 더 직접적으로 드러난다.
추가 완화가 의미하는 것
A→B가 4, A→C가 5, C→B가 -3이면 B의 최단 거리는 2다. 음수 간선 자체가 실패 원인은 아니다. B→C가 1까지 있으면 C→B→C의 합이 -2가 되어 한 바퀴마다 비용이 감소한다.
V-1회 이후에도 도달 가능한 간선에서 거리가 개선되면 음수 사이클의 영향을 의심할 수 있다. 위 코드는 존재를 알리고 중단한다. 어떤 정점이 -∞의 영향을 받는지까지 필요하면 개선된 정점에서 추가 도달 탐색을 해야 한다.
출발점에서 갈 수 없는 음수 사이클은 그 출발점의 거리 계산에 영향을 주지 않는다. 그래프 전체의 음수 사이클을 찾고 싶다면 모든 정점으로 연결된 가상 출발점을 두는 등 문제를 바꿔야 한다. 무한대인 정점에서 완화하지 않는 조건이 이 구별을 지킨다.
시간은 O(VE), 거리 저장 공간은 O(V)이며 간선 목록의 공간은 별도다. 변화가 없으면 조기 종료할 수 있지만 최악 복잡도는 그대로다. 비음수 간선만 있다면 더 빠른 방법이 유리할 수 있다.
환율 로그 변환, 이익·손실을 비용으로 표현한 모델 등에 응용할 수 있으나 부동소수점 오차와 가중치 의미를 확인해야 한다. “음수 간선을 지원한다”와 “음수 사이클에도 유한 답이 있다”는 서로 다른 주장이다.