벨먼-포드 알고리즘

1. 개요[편집]

---

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

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

하지만 만약 음수 사이클이 그래프에 있으면 이 알고리즘을 써서 정확한 최단 경로가 나오는 것을 보장할 수는 없다. 이게 무슨 소리냐 하면, 가장 싼 톨비로 목적지 까지 가는 알고리즘을 만들기 위해 고속 도로를 그래프로 만든다고 생각해보자. 이 그래프의 가중치는 톨비일 것이고 알고리즘의 목표는 출발지에서 부터 최소 톨비로 갈 수 있는 경로를 찾는 것이다. 일반적인 상황에서라면 이런 그래프에서 벨먼-포드 알고리즘은 문제 없이 작동 할것이다.

그런데 만약 어떤 혜자스런 톨게이트에서 고객 감사 행사로 톨비 100원을 받는 대신에 100원을 준다고 하면? 그리고 이 톨게이트에서 나오자마자 다시 돌아가서 계속 반복으로 이 돈을 받을수 있다면? 그렇다면 이 톨게이트를 뺑글 뺑글 도는것 만으로도 무한으로 돈을 받을 수 있을 것이고 톨비는 계속 줄어들 것이다. 이게 바로 음수의 사이클이다. 이런 사이클이 있으면 벨먼-포드 알고리즘은 무한의 루프에 빠지게 되고, 최저 비용 거리를 구할 수 없게 된다. 물론 벨먼-포드 알고리즘을 실행했을 때 음수의 사이클이 있는지 없는지도 확인할 수 있으므로 알고리즘 자체의 본질적인 문제는 아니다. 아래 의사코드에서 마지막 for문에서 확인하는 것이 음수 사이클이 있는지 확인하는 것이다. 만약 음수 사이클이 있다면, 사이클을 한번 돌 때마다 간선이 완화가 된다. 그래서 맨 마지막 for문에서 간선을 V-1번씩 확인했음에도 불구하고 완화할 수 있는 엣지가 있다면 음수 사이클이 있다고 판단할 수 있다.

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