벨만-포드 (Bellman-Ford)

개념

가중 유향 그래프에서 최단 경로를 구하는 알고리즘입니다.

벨만 포드 알고리즘은 동작원리는 다익스트라(Dijkstra)와 유사합니다.

차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며

시간 복잡도가 O(VE) 입니다. (V: 정점 개수, E: 간선 개수)

다익스트라 알고리즘에서 우선순위 큐를 이용한 방식으로 시간구현하면 

시간 복잡도 O(VlogV)이므로 벨만 포드 알고리즘보다 실행속도가 빠릅니다.

 

다익스트라 알고리즘의 한계

정점 A → C로 갈 때, 두 가지 경로가 존재합니다.

① A → B → C

     cost: 7 + (-4)  = 3

② A → C

    cost: 5

결과적으로는 ① 경로가 최단 거리 비용이지만, 다익스트라 알고리즘에서는 정점 [A]와 연결된 정점 [B], [C] 중에서

7 > 5로 정점 [C]를 방문하여 최단 거리를 5로 확정합니다.

이는 다익스트라 알고리즘 구현 조건자체가 가중치는 양의 정수이기 때문입니다.

 

음수 가중치의 문제

음의 가중치 자체가 문제가 되는것은 아니지만 

아래와 같이 음의 값이 누적되는 사이클을 형성하면 문제가 됩니다.

A → D로 최단 거리 비용을 생각해보자.

cost: 2 → 3  → -6  → 3  → -6  → 3  → -6 ... 무한히 최소 거리가 작아집니다.

그렇기에 벨만 포드 알고리즘에서는 음의 값이 누적되는 사이클이 존재하는 경우, 의미 없는 값을 반환합니다.

★ 음수 사이클 판단

정점의 개수가 N인 경우, 최단 경로의 크기는 최대 |N| - 1 이 됩니다.

ex) 정점의 개수 = 4, 최단 경로는 최대 3의 크기를 가짐.

즉, 사이클을 순환하여 최단 경로 크기가 커지는 것을 제한.

 

 

시뮬레이션

각 정점별 간선과 가중치가 아래와 같습니다. 

edge[]에 간선의 정보가 ① ~ ⑦순서로 담겨있다고 가정.

 

 

출발점 [A]는 dist = 0, 나머지 정점은 INF(무한대)로 초기화.

- edge[]를 순회하며, dist[] != INF인 간선 정보를 토대로 dist[] 값을 갱신해줍니다.

- dist[A] != INF 이므로, 정점 [A]와 연결된 간선 ①, ②, ③에 대해서 dist[] 갱신

    정점 [A]를 기준으로 연결된 정점을 활성화 합니다.

  

- dist[C], dist[D], dist[E] 모두 INF가 아니므로 

  정점 [C], [D], [E]와 연결된 간선 ④, ⑤, ⑥, ⑦도 활성화 됩니다.

  결과적으로 한번의 for문으로 ①~⑦ dist[] 배열은 아래와 같습니다.

 

- 이미 모든 간선이 활성화된 상태이지만

    위의 과정을 |V|-1번 반복하여 dist[] 값을 구해줍니다.

  

* |V|-1까지 갱신 후, 추가로 한번 더 동일한 작업을 수행할 때, 

    dist[]값이 갱신되는 것이 있다면 음수 사이클을 형성하고 있습니다.

 

[Java]

① 최대 |V|-1까지 Relaxation 작업을 수행하면 간선이 edge[]에 들어가 있는 순서와 관계없이

    출발점으로부터 각 정점의 최단 거리를 구할 수 있습니다.

② 아직 활성화되지 않은 정점은 continue

    edge[] 배열에 들어가 있는 순서에 따라서 활성화 되는 간선이 다를 수 있습니다.

③ 활성화된 간선을 토대로 dist[]값 갱신

④ 음수 사이클 형성 여부 확인

    : |V|-1번의 dist[] 갱신이 끝난 후, 한번 더 갱신 작업을 수행하여 변화가 있는지 확인

 

edge[]에 아래와 같은 순서로 간선 정보가 저장되어 있다면,

첫번째, for문 순회 과정에서 ①~④와 연결된 정점의 dist[] = INF 이기에

for문이 끝난 단계에서는 활성화된 간선은 ⑤, ⑥, ⑦이며 dist[] = {0, INF, 4, 10, -2} 입니다.

※ edge[] 원소 순회 및 배열 순회 순서와 상관없이 |V|-1번 for문 수행하면

    벨만 포드 알고리즘을 통해 출발점 - 나머지 정점까지의 최단 거리를 구할 수 있습니다.

    (전제: 음수 사이클 존재 X)

 

관련문제

- [BOJ] 11657 타임머신

- [Jungol] 2223 블랙홀