벨먼-포드 알고리즘

---

벨먼-포드 알고리즘은 가중 유향 그래프(Weighted-Directed Graph)에서 노드 사이의 최단 경로를 찾는 알고리즘이다.

1 개요

풀어 설명하자면 그래프가 가중치를 가지는 방향있는 변(Edge)으로 이루어져 있을때 한 점(Vertex)에서 나머지 다른 점까지의 최단 경로를 찾는 알고리즘이다. 이러한 목표는 다익스트라 알고리즘과 같다. 벨먼-포드 알고리즘의 시간 복잡도는 O(VE)로 O((V+E)lgV)인 다익스트라 알고리즘보다 일반적으로 느리다. 그러면 이런 똑같은 목표를 가진 더 비효율적인 알고리즘을 왜 쓰는것인가? 그건 바로 벨먼-포드 알고리즘이 좀더 유연해서 변의 가중치가 음수라도 쓸수 있기때문이다.

하지만 만약 음수 사이클이 그래프에 있으면 이 알고리즘을 써서 정확한 최단 경로가 나오는 것을 보장할 수는 없다. 이게 무슨 소리냐 하면, 고속 도로 그래프가 있고 이 그래프의 가중치는 톨비라고 생각을 해보자. 또한 알고리즘의 목표는 출발지에서 부터 최소 톨비로 갈수있는 경로를 찾는 것이라고 해보자. 그런데 만약 어떤 헤자스런 톨게이트에서 고객 감사 행사로 톨비로 100원을 받는 대신에 100원을 준다고 하면? 그리고 이 톨게이트에서 나오자마자 다시 돌아가서 계속 반복으로 이 돈을 받을수 있다면? 그렇다면 이 톨게이트를 뺑글 뺑글 도는것 만으로도 무한으로 톨비를 아낄수 있는 것이다. 이게 바로 음수의 사이클이다. 이런 사이클이 있으면 벨먼-포드 알고리즘은 무한의 루프에 빠지고 최저 비용 거리를 구할수 없다.

2 의사 코드

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[]