벨만-포드 알고리즘 (Bellman-Ford Algorithm)
1. 벨만-포드 알고리즘이란?
벨만-포드 알고리즘(Bellman-Ford Algorithm) 은 하나의 시작 정점(source) 으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
다익스트라 알고리즘과 비슷한 목적을 가지지만, 다익스트라에서는 불가능한 음수 가중치(negative weight) 를 허용한다.
따라서, 음의 간선(negative edge) 이 존재하는 그래프에서 최단 경로를 구할 때 매우 유용하다.
2. 알고리즘의 핵심 아이디어
벨만-포드는 모든 간선을 반복적으로 완화(Relaxation) 하는 알고리즘이다.
Relaxation (완화):
어떤 경로를 통해 더 짧은 거리로 도달할 수 있다면, 그 거리 값을 갱신하는 과정
즉, 다음과 같은 갱신을 반복한다.
if distance[v] > distance[u] + w(u, v):
distance[v] = distance[u] + w(u, v)이 과정을 모든 간선에 대해 |V| - 1번 반복한다. (여기서 V는 정점의 개수)
최단 경로는 최대 |V|-1개의 간선으로 구성되기 때문에 만약 그 이후에도 갱신이 일어난다면, 음수 사이클(negative cycle) 이 존재한다는 뜻이다.
3. 알고리즘 동작 원리 예시
다음과 같은 그래프가 있다면
| 간선 | 가중치 |
| A -> B | 4 |
| A -> C | 2 |
| B -> C | -1 |
| B -> D | 2 |
| C -> D | 3 |
1) 초기화
distance[A] = 0
distance[B] = INF
distance[C] = INF
distance[D] = INF
2) 1번째 반복 (모든 간선 완화)
- A -> B : 0 + 4 -> distance[B] = 4
- A -> C : 0 + 2 -> distance[C] = 2
- B -> C : 4 + (-1) = 3 -> distance[C] = min(2, 3) -> 2 유지
- B -> D : 4 + 2 = 6 -> distance[D] = 6
- C -> D : 2 + 3 = 5 -> distance[D] = min(6, 5) -> 5로 갱신
[결과] A(0), B(4), C(2), D(5)
3) 2~3번째 반복
이후 반복에서도 더 이상 갱신이 일어나지 않으므로 종료되고, 최단 거리 결과는 아래와 같다.
A → A : 0
A → B : 4
A → C : 2
A → D : 5
4. 음수 사이클(negative cycle) 검출
벨만-포드는 음수 사이클을 탐지할 수 있는 유일한 최단경로 알고리즘이다.
V-1번 반복 후에도 여전히 distance가 갱신된다면, 음수 사이클이 존재한다고 판단한다.
예시:
A → B (-2)
B → C (-1)
C → A (-4)
이 경우 계속 갱신이 발생하며, 무한히 더 짧은 경로가 만들어지므로 최단 경로가 존재하지 않는다.
5. 파이썬 구현 예제
def bellman_ford(n, edges, start):
INF = float('inf')
distance = [INF] * (n + 1)
distance[start] = 0
# 1. 모든 간선에 대해 n-1번 반복
for i in range(n - 1):
for u, v, w in edges:
if distance[u] != INF and distance[v] > distance[u] + w:
distance[v] = distance[u] + w
# 2. 음수 사이클 검사
for u, v, w in edges:
if distance[u] != INF and distance[v] > distance[u] + w:
print("음수 사이클 존재")
return None
return distance[1:]
# 예시 실행
edges = [
(1, 2, 4),
(1, 3, 2),
(2, 3, -1),
(2, 4, 2),
(3, 4, 3),
]
print(bellman_ford(4, edges, 1))
출력:
[0, 4, 2, 5]
6. 시간 복잡도
| 항복 | 복잡도 |
| 간선 완화 반복 | O(V × E) |
| 음수 사이클 검사 | O(E) |
| 총합 | O(VE) |
다익스트라(O(E log V))보다 느리지만, 음수 가중치가 있는 그래프에서는 벨만-포드가 필수입니다.
7. 다익스트라 알고리즘과 비교
| 구분 | 벨만-포드 | 다익스트라 |
| 가중치 | 음수 가능 | 음수 불가 |
| 자료구조 | 단순 반복 | 우선순위 큐(힙) |
| 복잡도 | O(VE) | O(E log V) |
| 음수 사이클 탐지 | 가능 | 불가능 |
- 다익스트라 : 빠르지만 음수 불가능
- 벨만-포드 : 느리지만 음수 가능 + 사이클 탐지 가능