Bellman-Ford는 하나의 출발점에서 시작해 모든 간선을 반복해서 완화하며 음수 가중치가 있는 그래프의 최단 거리를 계산하는 알고리즘입니다. Dijkstra처럼 “현재 가장 작은 후보가 영원히 확정된다”는 전제를 사용하지 않기 때문에 음수 간선을 처리할 수 있습니다. 대신 음수 사이클이 출발점에서 도달 가능하면 최단 거리가 유한한 값으로 존재하지 않을 수 있다는 사실을 결과 계약에 포함해야 합니다.
정점 수를 n, 간선 수를 m이라 하면 각 라운드는 모든 간선을 한 번 훑습니다. 음수 사이클이 source에서 reachable하지 않다면 최대 n-1개의 간선을 가진 단순 경로가 유한 최단 경로가 될 수 있으므로 n-1회 라운드 후 값이 안정됩니다. n번째 라운드에도 갱신이 일어나면 source에서 그 갱신까지 도달 가능한 음수 cycle의 신호입니다. 다만 미도달 영역의 음수 cycle을 single-source 결과에 섞어서는 안 됩니다.
단일 출발 거리의 상태
거리 배열은 source만 0, 나머지는 INF로 초기화합니다. INF는 실제 거리 숫자가 아니라 “현재 source에서 도달한 경로가 없음”을 나타내는 표식이므로 INF + weight를 계산하면 안 됩니다. 간선 (u,v,w)에 대해 dist[u]가 유한하고 dist[v] > dist[u]+w라면 dist[v]를 줄이고 parent[v] = u를 함께 갱신합니다.
완화는 간선을 한 번 처리할 때마다 한 단계 긴 경로 정보를 앞으로 전파합니다. 간선 순서가 S→A, A→B, B→C인 한 pass라면 한 라운드 안에 새로 낮아진 값이 뒤쪽 간선으로 계속 전달될 수 있습니다. 반대로 입력 순서가 역순이면 같은 정보가 다음 라운드에야 도달할 수 있습니다. 따라서 “한 번의 간선 순회면 모든 최단 경로가 계산된다”는 설명은 입력 순서와 무관한 보장이 아닙니다.
완화 라운드와 경로 간선 수
라운드의 개념을 명확히 하려면 각 단계의 거리 변화를 실제 숫자로 적어 보는 것이 좋습니다. 정점 S,A,B,C와 간선 S→A=4, A→B=3, B→C=-2가 있고 간선을 이 순서로 순회한다고 하겠습니다.
| 라운드 종료 | S |
A |
B |
C |
관찰 |
|---|---|---|---|---|---|
| 시작 | 0 | INF | INF | INF | source만 도달 |
| 1 | 0 | 4 | 7 | 5 | 한 라운드에 세 간선이 연쇄 반영 |
| 2 | 0 | 4 | 7 | 5 | 추가 갱신 없음 |
다른 순서로 B→C, A→B, S→A를 읽으면 첫 라운드에서 A=4만 알게 되고, 다음 라운드에 B=7, 그 다음에 C=5가 됩니다. n-1=3회라는 상한은 어떤 간선 순서에도 맞는 보장이고, 조기 종료는 실제 순회에서 변화가 없었던 경우에만 가능합니다.
이 논리는 음수 간선이 있어도 음수 cycle이 없는 한 성립합니다. 최단 walk에 cycle이 들어 있고 그 cycle 비용이 음수가 아니면 cycle을 제거해도 더 나빠지지 않는 단순 경로를 얻을 수 있습니다. 그래서 source-reachable finite shortest distance는 최대 n-1개 간선으로 표현됩니다. 음수 cycle이면 cycle을 한 바퀴 더 돌 때마다 값이 더 내려가 이 경계가 사라집니다.
그림을 글로 읽기
- source S: dist = 0
- 라운드 1: S→A→B 정보 전파
- 라운드 n-1: 최대 단순 경로 반영
- 라운드 n 검사: 갱신이면 음수 cycle 신호
- source S → 라운드 1: 모든 간선 완화
- 라운드 1 → 라운드 n-1: 경로 간선 수 증가
- 라운드 n-1 → 라운드 n 검사: 변화 없음 또는 갱신
음수 간선과 Dijkstra의 차이
Dijkstra는 최소 힙에서 꺼낸 정점의 거리를 확정할 때, 나중에 거쳐 갈 간선이 현재 값을 더 낮추지 못한다는 비음수 전제를 사용합니다. 음수 간선이 있으면 이미 확정한 정점이 뒤늦게 낮아질 수 있습니다. Bellman-Ford는 확정 집합을 만들지 않고 모든 간선을 반복하므로 이러한 역전도 다음 라운드에 반영합니다.
예를 들어 S→A=2, S→B=5, B→A=-4에서는 Dijkstra가 A를 2로 먼저 확정할 수 있지만 실제 S→B→A 비용은 1입니다. Bellman-Ford는 B가 먼저 알려졌는지와 무관하게 후속 라운드의 B→A 완화로 A를 1로 낮춥니다. 음수 간선이 있다는 이유만으로 곧바로 음수 cycle이라는 뜻은 아닙니다. cycle 탐지는 별도의 라운드 조건입니다.
음수 간선이 없고 단일 source에서 우선순위 큐로 더 빠르게 계산할 수 있는 입력이라면 Bellman-Ford의 O(nm) 반복 비용을 지불할 이유가 적습니다. 반대로 음수 가중치가 허용되거나 도달 가능한 음수 cycle을 보고해야 하는 요구라면 Dijkstra를 우선순위 큐만 바꿔 대체할 수 없습니다.
n번째 갱신과 cycle 판정
일반적인 탐지는 먼저 n-1회 완화를 수행하고, 다음 한 번의 추가 pass에서 어떤 간선이라도 갱신되는지 확인하는 방식입니다. 갱신 조건은 dist[u] != INF이고 dist[v] > dist[u] + w여야 합니다. dist[u] == INF인 간선은 source에서 아직 도달할 수 없는 영역이므로 건너뜁니다.
왜 이것이 cycle을 뜻하는지는 경로 간선 수로 볼 수 있습니다. 음수 cycle이 source에서 도달 가능하지 않다면, n-1개 이하 간선의 최단 단순 경로가 이미 반영된 뒤 더 긴 경로가 더 좋아질 수 없습니다. 그런데 n번째 pass에서 갱신됐다는 것은 cycle을 포함한 walk가 기존의 모든 단순 경로보다 낮아졌다는 뜻입니다. 유한한 정답이 아니라 계속 반복해 낮출 수 있는 구조가 source에서 reachable하다는 신호입니다.
한 번 갱신된 정점 자체가 곧 모든 음수 cycle 정점이라는 뜻은 아닙니다. 그 정점으로부터 도달 가능한 정점도 이후 완화에서 계속 영향을 받을 수 있으므로, 애플리케이션이 -INF 영향 범위를 표시하려면 갱신 후보에서 다시 그래프를 탐색해 cycle 영향이 target까지 닿는지 확인하는 단계를 둘 수 있습니다. 정확한 출력이 단순 boolean인지, 특정 정점 목록인지에 따라 이 후처리 계약이 달라집니다.
도달 불가 음수 사이클
정점 X,Y에 X→Y=-3, Y→X=1이 있고 source S가 그 요소와 연결되지 않았다고 하겠습니다. cycle 비용은 -2이지만 dist[X]와 dist[Y]는 계속 INF입니다. INF를 0으로 초기화해 모든 간선을 검사하는 변형은 전역 음수 cycle 탐지에는 활용될 수 있지만, 그것을 source 단일 출발 최단 거리 결과로 오해해서는 안 됩니다.
source에서 A에 도달하고 A가 음수 cycle에 들어가지만 B로 나가는 경로가 없다면 S→A 계열 거리는 계속 낮아질 수 있어 유한 최단 거리가 없지만, S→B는 cycle로부터 도달 불가능하므로 자동으로 -INF가 되지 않습니다. 반대로 cycle에서 B로 갈 수 있다면 S→B도 cycle을 반복한 뒤 이동할 수 있어 유한 최솟값으로 확정할 수 없습니다.
따라서 출력은 적어도 UNREACHABLE, FINITE(distance), NEGATIVE_CYCLE_REACHABLE 같은 상태를 구별하는 편이 안전합니다. 단순히 큰 음수 sentinel을 거리 배열에 넣으면 “유한하게 매우 큰 음수”와 “무한히 낮아짐”을 구분하기 어렵고, 후속 계산에서 잘못된 경로 비용이 전파됩니다.
오버플로와 sentinel 산술
INF = MAX_INT64 같은 표식을 사용할 때 INF + (-5)는 MAX_INT64-5이므로 signed overflow가 아닙니다. 그러나 sentinel을 실제 거리처럼 비교하면 미도달 정점이 INF-5로 오염되어 거짓 경로가 됩니다. 실제 양의 overflow 예는 MAX_INT64+5이고, 유한한 덧셈은 checked addition으로 양의 overflow와 음의 underflow를 분리해야 합니다. 먼저 dist[u] == INF인지 검사해 sentinel을 산술에서 제외합니다.
음수 cycle의 반복 하강을 같은 정수 배열에 무한히 기록할 필요는 없습니다. n번째 pass 갱신 여부를 별도 boolean으로 기록한 뒤, 필요하면 해당 정점에서 도달 가능한 정점 집합을 표시합니다. -INF를 출력하는 경우에도 그것이 실제 정수 값이 아니라 결과 상태임을 타입 또는 별도 열로 표현해야 합니다.
구현 예시는 다음과 같은 흐름입니다.
dist[source] = 0
for v != source:
dist[v] = INF
for round in 1 .. n-1:
changed = false
for (u, v, w) in edges:
if dist[u] == INF:
continue
candidate = checked_add(dist[u], w)
if candidate < dist[v]:
dist[v] = candidate
parent[v] = u
changed = true
if not changed:
break
cycleSeeds = []
for (u, v, w) in edges:
if dist[u] != INF and checked_add(dist[u], w) < dist[v]:
cycleSeeds.push(v)
이 코드는 설명용 의사코드이며 이 환경에서 실행한 결과를 의미하지 않습니다. checked_add가 오류를 반환하는 경우에는 음수 cycle로 가장하지 않고 입력 범위 오류로 분리해야 합니다. parent로 cycle을 복원하는 방식은 갱신한 정점에서 n번 부모를 따라가는 등 추가 규칙이 필요하고, 여러 cycle과 도달성 전파가 있으면 결과 계약을 따로 정해야 합니다.
조기 종료와 복잡도
한 라운드 전체에서 어떤 거리도 바뀌지 않았다면 이후 라운드도 바뀌지 않습니다. 모든 가능한 완화가 고정점에 도달했기 때문입니다. 이 조건은 빠른 입력에서 실제 실행 횟수를 줄이지만, 최악의 시간 복잡도 O(nm)를 없애지는 않습니다. 정점·간선 수가 크고 음수 cycle 탐지가 필요하면 그래프 구조와 입력 분포를 기준으로 다른 방법을 검토해야 합니다.
간선 배열을 한 번씩 순회하므로 메모리는 거리·부모·간선 저장을 포함해 보통 O(n+m)입니다. adjacency list를 쓰는지 flat edge list를 쓰는지는 순회와 캐시, 갱신 요구에 따라 달라지며, Bellman-Ford의 논리는 모든 간선을 각 라운드에 볼 수 있다는 사실에 있습니다.
검증과 실패 경계
검증 입력은 양의 간선만 있는 짧은 체인, 음수 간선이지만 cycle은 없는 그래프, source-reachable 음수 cycle, source와 분리된 음수 cycle, 고립 정점, INF와 덧셈 경계값을 포함해야 합니다. 작은 그래프라면 가능한 단순 경로를 열거해 음수 cycle이 없는 경우의 최솟값과 각 라운드 결과를 대조할 수 있습니다.
입력 순서를 뒤집어도 최종 결과가 같아야 하고, 조기 종료는 마지막 변화 없는 pass 뒤에만 일어나야 합니다. n번째 pass의 갱신 후보를 기록한 뒤, source에서 그 후보로 갈 수 없었던 경우가 섞이지 않았는지도 확인합니다. 음수 cycle이 있는 경우에는 단일 숫자 최단 거리를 기대하는 테스트를 작성하지 말고, finite/unreachable/negative 영향 상태를 검증해야 합니다.
참고와 적용 범위
이 문서의 라운드 불변식, 음수 간선 허용, n-1회 충분성, n번째 갱신을 이용한 도달 가능한 음수 cycle 탐지는 입력 계약에 지정된 CP-algorithms Bellman-Ford 참고 항목과 저장소의 Dijkstra 설명을 대조한 범위에서 작성했습니다. CP-algorithms 페이지는 알고리즘 참고 자료이며 특정 언어의 정수 오버플로 계약이나 라이브러리 동작을 규정하지 않습니다.
라이브러리 구현을 선택할 때는 무한대 표현, checked arithmetic, negative cycle을 반환하는 API 형식, 도달 불가 정점의 출력 타입을 실제 문서와 코드로 확인해야 합니다. 이 글은 SPFA의 큐 계수 변형이나 모든 source를 동시에 다루는 전역 cycle 탐지의 별도 성질을 일반 Bellman-Ford 결과로 확대하지 않습니다.
참고 경로
위 링크는 개념별 참고 경로이며, 본문에서 명시한 확인 범위와 미확인 구현 조건을 함께 적용합니다.