벨만-포드 알고리즘(Bellman-Ford algorithm)

벨만-포드 알고리즘(Bellman-Ford algorithm)

최단 경로 알고리즘에서 대표적인 것으로는

1) 다익스트라 : 유향그래프, 한점 - 다수의 점, 음수 가중치 X

2) 벨만-포드  : 유향그래프, 한점 - 다수의 점, 음수 가중치 O, 음수 사이클 X

3) 플로이드-와샬 : 모든 점- 모든 점

여기서는 벨만-포드 알고리즘에 대해 알아보겠습니다.

* 벨만-포드 알고리즘(Bellman-Ford algorithm)

 벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 

 

 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르다. 

 하지만 다익스트라 알고리즘은 가중치가 음수인 경우에는 처리할 수 없으므로, 이런 경우에는 벨먼-포드 알고리즘을 사용한다.

V와 E가 각각 그래프에서 꼭짓점과 변의 개수라고 한다면, 벨먼-포드 알고리즘의 실행시간은 O(VE)이다.

출처 : https://ko.wikipedia.org/wiki/%EB%B2%A8%EB%A8%BC-%ED%8F%AC%EB%93%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

,

아래의 그림에서 시작점이 s, 도착점이 g라고 했을 때,

문제되는 경우를 알아봅시다.

1) s → a → b → g

 : 문제되지 않음

2) s → c → d → g

 : c와 d 사이에 사이클이 존재함을 알 수 있습니다.

  그러나 사이클을 순환하는 동안 경로값이 증가하므로, 사이클을 선택하지 않으면 큰 문제가 되지 않습니다.

3) s → e → f → g

 : e와 f 사이에 사이클이 존재함을 알 수 있습니다.

  그러나 사이클을 순환하는 동안 경로값이 감소하므로, 이 경우에는 최단 경로값을 측정할 수 없습니다.

4) h → i → j

 : 순환 사이클이 존재하며, 경로값이 무한대로 감소하지만 s → g로의 최단경로를 구하는 것에는 관계 없으므로 문제가 되지 않습니다.

위의 예에서 보았듯이 모든 음수 순환이 문제가 되지는 않습니다. 

시작점에서 도착점까지의 경로에 포함되는 음수 순환만 문제가 되는 것을 알 수 있습니다.

- 결론 : 

1. 최단 경로는 순환을 포함해서는 안된다.

2. 최단 경로의 길이는 최대 |V| - 1 이다.

3. Relaxation(완화)을 이용해 최단 경로값을 찾는다.

    : 현재 경로 값보다 더 적은 경로가 존재한다면 값을 변경한다.

4. 시작점에서 다른 노드를 0번 경유해서 갈 수 있는 경우부터 ~ N-1번 경유해서 갈 수 있는 경우까지 Relaxation을 한다.

   → 값 갱신이 N번 이상 갱신된다면 음수 사이클이 존재한다는 것이라고 판단한다.
,

의사 코드(Pseudo-Code)

// 함수 파라미터 : G그래프, w가중치, s출발점

BELLMAN-FORD(G, w, s)

 

 INITIALIZE-SINGLE-SOURCE(G, s)

     // 사이클을 가지지 않는 최대 Iteration

     For i ← 1 to |V[G]|-1

           // Relaxation

           do for each edge(u, v) ∈ E[G]

                   do RELAX(u, v, w)

     // Check - Negative edge weight cycles

     // Relaxation 과정 이후에도 distance가 갱신된다면 = N번 이상 갱신된다면

     For each edge(u, v) ∈ E[G]

            do if d[v] > d[u] + w(u, v)

                    then return FALSE

return TRUE       

, 

실제 코드는 아래 문제 풀이에서 확인해봅시다. (백준 11657 타임머신)

http://stack07142.tistory.com/83