벨만-포드 알고리즘(Bellman-Ford Algorithm)

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

벨만-포드 알고리즘(Bellman-Ford Algorithm)은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로/최소 비용를 찾는 알고리즘이다.
다익스트라 알고리즘과 차별되는 점은 음수 가중치를 처리할 수 있다는 점과 음수 사이클을 탐지할 수 있다는 점이다.
때문에, 음수 가중치가 포함된 그래프에서 유용하게 사용된다.
 
 
 

동작 원리

벨만-포드 알고리즘은 크게 세가지의 과정을 거친다.
1. 초기화
시작 정점에서 다른 모든 정점까지의 거리를 무한대로 설정한다.
시작 정점의 거리를 0으로 설정한다.
 
2. 간선 반복
모든 간선에 대해 그 간선을 따라 가는 거리가 기존에 기록된 거리보다 짧으면, 해당 거리를 업데이트 한다.
이 과정을 그래프에 있는 정점의 수 - 1번 반복한다.
왜냐하면, 최단 거리는 최대 정점의 수 -1번의 간선 탐색만으로도 도달할 수 있기 때문이다.
 
3. 음수 사이클 검출
마지막으로, 한 번 더 모든 간선을 확인한다.
이때 거리 값이 업데이트 되면 그래프에 음수 가중치 사이클이 존재한다고 판별한다.
 
 
 

예시

아래 이미지와 같은 그래프를 가질 때, A에서 출발하는 최단 비용을 구해보자.

1. 초기화
시작 정점의 거리는 0으로 설정하고, 나머지 노드의 거리는 무한으로 설정한다.

Node	A	B	C	D
Distance	0	INF	INF	INF

 
 
2. 간선 반복
모든 간선을 확인한 후 거리를 갱신해준다. 정점이 4개 있으므로 이므로 3(=정점 수-1)번 반복을 하면 된다.
- 반복 1
A->B : 5  = A의 거리(0) + 가중치(5) (INF 값보다 작으므로 갱신)
A->C : 4  = A의 거리(0) + 가중치(4) (INF 값보다 작으므로 갱신)
B->D : -1 = B의 거리(5) + 가중치(-6) (INF 값보다 작으므로 갱신)
C->D : 1 = C의 거리(4) + 가중치(-3) (앞에서 갱신된 D-1보다 크므로 갱신 X)
D->C : -4 = D의 거리(-1) + 가중치(-3) (앞에서 갱신된 C4보다 작으므로 갱신)

Node	A	B	C	D
Distance	0	5	-4	-1

- 반복 2
A->B : 5  = A의 거리(0) + 가중치(5) (앞에서 갱신된 A 값과 같으므로 갱신 X)
A->C : 2  = A의 거리(0) + 가중치(2) (앞에서 갱신된 C-4보다 크므로 갱신 X)
B->C : 7 = B의 거리(5) + 가중치(2) (앞에서 갱신된 C-4보다 크므로 갱신 X)
C->D : -7 = C의 거리(-4) + 가중치(-3) (앞에서 갱신된 D-4보다 작으므로 갱신 )
D->C : -10 = D의 거리(-7) + 가중치(-3) (앞에서 갱신된 C-4보다 작으므로 갱신 )

Node	A	B	C	D
Distance	0	5	-10	-7

- 반복 3
A->B : 5  = A의 거리(0) + 가중치(5) (앞에서 갱신된 A 값과 같으므로 갱신 X)
A->C : 2  = A의 거리(0) + 가중치(2) (앞에서 갱신된 C-10보다 크므로 갱신 X)
B->C : 7 = B의 거리(5) + 가중치(2) (앞에서 갱신된 C-10보다 크므로 갱신 X)
C->D : -13 = C의 거리(-10) + 가중치(-3) (앞에서 갱신된 D-13보다 작으므로 갱신 )
D->C : -16 = D의 거리(-13) + 가중치(-3) (앞에서 갱신된 C-10보다 작으므로 갱신 )

Node	A	B	C	D
Distance	0	5	-16	-13

 
 
3. 음수 사이클 검출
A->B : 5 = A의 거리(0) + 가중치(5) (앞에서 갱신된 A 값과 같으므로 갱신 X)
A->C : 2 = A의 거리(0) + 가중치(2) (앞에서 갱신된 C-16보다 크므로 갱신 X)
B->C : 7 = B의 거리(5) + 가중치(2) (앞에서 갱신된 C-16보다 크므로 갱신 X)
C->D : -19 = C의 거리(-16) + 가중치(-3) (앞에서 갱신된 D-13보다 작으므로 갱신 )
D->C : -22 = D의 거리(-19) + 가중치(-3) (앞에서 갱신된 C-16보다 작으므로 갱신 )

Node	A	B	C	D
Distance	0	5	-22	-19

 
거리가 여전히 갱신되고 있으므로, 이 그래프에는 음수 사이클이 존재한다고 판단.
 
 
 
 
 

사용 사례

• 음수 가중치를 다룰 때
  다익스트라 알고리즘과 달리, 벨만-포드 알고리즘은 음수 가중치가 포함된 그래프에서 최단 경로를 찾을 수 있다.
  
  
• 음수 사이클 검출
  음수 사이클이 그래프에 존재하는지 확인할 수 있다.
  예를 들어, 금융 거래(무위험 차익 거래; arbitrage)나 경제 모델링에서 중요한 역할을 할 수 있다.
  
  
• 네트워크 최단 경로
  패킷 전송이나 네트워크 경로에서 음수 가중치가 존재할 수 있을 때 사용된다.

 
 
 
 

시간 복잡도

동작 원리에서 알 수 있듯이 정점 수만큼 반복하고, 그 때마다 모든 간선을 탐색하므로 O(VE)이다.
O((V+E)logV)인 다익스트라 알고리즘보다 시간은 더 걸리지만, 음수 가중치를 처리할 수 잇는 장점이 있다.