1. 개요
벨먼-포드 알고리즘은 가중 유향 그래프(Weighted-Directed Graph)에서 노드 사이의 최단 경로를 찾는 알고리즘이다.풀어 설명하자면 그래프가 가중치를 가지는 방향있는 변(Edge)[1]으로 이루어져 있을때 한 점(Vertex)에서 나머지 다른 점까지의 최단 경로를 찾는 알고리즘이다. 이러한 목표는 다익스트라 알고리즘과 같다. 벨먼-포드 알고리즘의 시간 복잡도는 O(VE)로 O((V+E)lgV)인 다익스트라 알고리즘보다 일반적으로 느리다. 그러면 이런 똑같은 목표를 가진 더 비효율적인 알고리즘을 왜 쓰는것인가? 그건 바로 벨먼-포드 알고리즘이 좀더 유연해서 변의 가중치가 음수라도 쓸수 있기 때문이다.
하지만 만약 음수 사이클이 그래프에 있으면 이 알고리즘을 써서 정확한 최단 경로가 나오는 것을 보장할 수는 없다. 이게 무슨 소리냐 하면, 가장 싼 톨비로 목적지 까지 가는 알고리즘을 만들기 위해 고속 도로를 그래프로 만든다고 생각해보자. 이 그래프의 가중치는 톨비일 것이고 알고리즘의 목표는 출발지에서 부터 최소 톨비로 갈 수 있는 경로를 찾는 것이다. 일반적인 상황에서라면 이런 그래프에서 벨먼-포드 알고리즘은 문제 없이 작동 할것이다.
그런데 만약 어떤 혜자스런 톨게이트에서 고객 감사 행사로 톨비 100원을 받는 대신에 100원을 준다고 하면? 그리고 이 톨게이트에서 나오자마자 다시 돌아가서 계속 반복으로 이 돈을 받을수 있다면? 그렇다면 이 톨게이트를 뺑글 뺑글 도는것 만으로도 무한으로 돈을 받을 수 있을 것이고 톨비는 계속 줄어들 것이다. 이게 바로 음수의 사이클이다. 이런 사이클이 있으면 벨먼-포드 알고리즘은 무한의 루프에 빠지게 되고, 최저 비용 거리를 구할 수 없게 된다. 물론 벨먼-포드 알고리즘을 실행했을 때 음수의 사이클이 있는지 없는지도 확인할 수 있으므로 알고리즘 자체의 본질적인 문제는 아니다. 아래 의사코드에서 마지막 for문에서 확인하는 것이 음수 사이클이 있는지 확인하는 것이다. 만약 음수 사이클이 있다면, 사이클을 한번 돌 때마다 간선이 완화가 된다. 그래서 모든 간선을 V-1번씩 확인했음에도 불구하고 맨 마지막 for문에서 거리를 추가로 완화시킬 수 있는 간선이 있다면 음수 사이클이 있다고 판단할 수 있다.
2. 의사 코드
#!syntax java
BellmanFord(G,w,s):
//초기화 과정
for each u in G.V: //노드를 초기화 하기
distance[v] = inf //모든 노드의 최단거리를 무한으로 지정
parent[v] = null //모든 노드의 부모 노드를 널값으로 지정
distance[s] = 0 //출발점의 최단거리는 0으로 지정한다
//거리측정 과정
for i from 1 to len(G.V): //노드의 숫자만큼
for each (u,v) in G.E: //모든 변을 체크해 최단 거리를 찾아본다.
if distance[u] + w[(u,v)] < distance[v]:
//만약 u를 경유하여 v로 가는 거리가 현재 v의 최단 거리보다 짧으면
distance[v] = distance[u] + w[(u,v)] //그 거리를 v의 최단거리로 지정
parent[v] = u //u를 v의 부모 노드로 지정
//음수 사이클 체크 과정
for each (u,v) in G.E:
if distance[u] + w[(u,v)] < distance[v]:
return false //음수 사이클을 확인하고 알고리즘을 정지
return distance[], parent[]
[1]
대개 길이라고 생각하나 100% 들어맞는 비유는 아니다. 비슷하게 생각할 수는 있지만...