Graph - Bellman-ford's algorithm

참고 사이트 : https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

bellman-Ford's algorithm

keywords : 최단 경로, 음수 사이클, 그래프

개념

벨만-포드 알고리즘은 Shortest path를 구할 때 graph 내 모든 edge에 대해 edge relaxation을 수행한다.

모든 노드 개수 : |V|-1개

모든 edge에 대해 edge-relaxation을 |V|-1회 수행한다.

방법)

• 시작 노드 A를 제외한 모든 노드의 value를 inf로 초기화한다.

• 노드 B에서 노드 C로 가는 경우, edge cost가 2인 경우,
  B노드 값 + 간선(B,C) = inf이기 때문에 업데이트할 필요가 없다.

• 노드 A에서 노드 B로 가는 경우, edge cost가 8인 경우,

  A노드 값 + 간선(A,B) = 0+8 이 B노드의 값인 무한대보다 작기 때문에 B노드의 값을 8로 업데이트한다.

  위와 같은 방법으로 모든 노드에 대해 edge relaxation을 적용한다.

• cost 계산을 했을 때 이전값보다 작을 때만 업데이트한다.

음수의 경우

다익스트라와 다르게 벨만-포드는 가중치가 음수여도 적용이 가능하다.

그러나 음수 가중치가 사이클을 이루고 있으면 계속 값이 작아지므로 -inf가 되어 최단 경로를 얻을 수 없다.

따라서 모든 엣지에 대해 edge relaxation을 시작노드를 제외한 전체 노드 수 만큼 반복한 뒤, 모든 엣지에 대해 edge relaxation을 1번 수행한다. 이때 1번이라도 업데이트가 일어난다면 negative cycle이 있다는 것이다. 이는 결과를 구할 수 없다는 의미이기 때문에 false를 반환하고 함수를 종료한다.

계산복잡성

모든 노드 수 - 1(시작노드) + 마지막 모든 엣지에 대한 edge relaxation

= O(|V||E|)

주로 Dense graph는 엣지 수가 노드 수 제곱에 근사하기 때문에 간단히 O(|V|^3)이 된다.

다익스트라 알고리즘은 O(|V|^2)보다 더 크다.

이것은 음수 가중치까지 분석할 수 있어서 일종의 trade-off라고 볼 수 있다.