Bellman-Ford’s Algorithm

다익스트라 알고리즘의 약점

다익스트라는 노드들을 방문하면서 최단거리를 정한다.
이때 한 번 방문된 노드의 최단거리는 바뀌지 않는다.

때문에 다익스트라 알고리즘은 가중치 중 음수인 것이 존재할 때는 쓸 수 없다.
가중치가 음수인 엣지가 발견되면 이전에 내가 방문했던 노드의 최단 거리도 바꿔주어야 하고
이에 따라 그 노드에 의해 최단거리가 결정된 노드들을 다 줄여줘야 한다.
다익스트라 알고리즘은 그 앞의 노드를 참조하지 않으므로
이 작업은 불가능하다.

이것이 가능한 알고리즘 중
벨만-포드 알고리즘이 있다. (Bellman-Ford’s Algorithm)

벨만-포드 알고리즘

모든 노드에 달린 모든 엣지를 다 본다.

이의 수도 코드는

for ( i = 1; i < n; i++ ) {  
  for ( (u, v) in E ) {
    if ( v.distance > u.distance + w(u, v) )  
      v.distance = u.distance + w(u, v);  
      v.predecessor = u;
  }
}

이다. 그냥 다 보는 것이다.
앞이고 뒤고 다 보게 되므로 음수더라도 다익스트라와 다르게 수정이 가능하다.

단, 벨만-포드 알고리즘도 만능은 아니다.

음의 사이클 (사이클 중 가중치의 합이 음수) 이 생긴다면
앞과 뒤를 모두 보는 알고리즘 특성 상
볼 때마다 거리가 계속 줄어들 것이다.

시간 복잡도

모든 노드의 모든 엣지
N 에 M …

O(n * m) 임이 자명하다.