[algorithm] bellman-ford

Bellman-Ford Algorithm 번역+공부 (예제 코드는 kotlin)

 

* 문제: 주어진 그래프에서 시작 점(vertex)으로부터 모든 점까지의 최단 거리 찾기

 - 그래프는 음수 가중치(negative weight)를 갖는 선(edge)을 가질 수 있다.

 - 시간 복잡도: O(VE), V=점 갯수, E=선 갯수

 - 음수 가중치를 갖는 선이 없다는 가정하에 이 문제를 해결하는 다른 알고리즘으로 Dijkstra가 있지만 별도로 다룬다.

 

* 입력: 그래프(directed graph), 시작점 src

* 출력: src로부터 모든 점까지의 최단 거리

 - 음수 가중치가 순환되는 경우(negative weight cycle) 최단 거리를 계산할 수 없기 때문에 이에 대한 출력이 있어야 한다.

---

* step by step

 

(1) 시작점으로부터 모든 점들까지의 거리 초기화

 - distance(시작점 -> 시작점) = 0

시작점 A로부터 모든 점들까지의 거리 초기화 상태

 

(2) 주어진 그래프에서 아래와 같은 과정을 |V|-1번 반복해 최단 거리 계산

 - 시작점에서 어떤 점까지의 최단 경로에서 선(edge)은 최대 |V|-1개 나올 수 있기 때문에 |V|-1번 반복.

val dist = IntArray(V)
// src = 0, dist[0] = 0, dist[...rest] = Int.MAX_VALUE

for (i in 1 until V) {
  for (edge in graph.edges) {
    val u = edge.src
    val v = edge.dest
    if (dist[u] != Int.MAX_VALUE
      && dist[v] > dist[u] + edge.weight) {
      dist[v] = dist[u] + edge.weight
    }
  } // inner
} // outer

 

(3) 음수 가중치가 순환되는 경우(negative weight cycle) 검사

 - 순환이 없다는 가정 하에 (2) 과정에서 이미 시작점으로부터 모든 점들까지의 최단 거리 계산을 마쳤다.

 - 그럼에도 불구하고 모든 선들에 대해서 다시 한번 최단 거리 갱신 과정을 수행했을 때((2) 과정의 inner 루프), 최단 거리가 갱신이 된다면 그래프가 순환됨을 알 수 있다.

for (edge in graph.edges) {
  val u = edge.src
  val v = edge.dest
  if (dist[u] != Int.MAX_VALUE
    && dist[v] > dist[u] + edge.weight) {
    println("found negative weight cycle in the graph")
    return
  }
}

 

* 동작 방식

이 알고리즘은 bottom-up 방식으로, (2) 과정에서 outer 루프의 i 번째 반복을 거치면 최대 i 개의 선을 가진 최단 거리가 계산된다.(proof)

 

다음은 이해를 돕기 위한 예제이다.

 

1번째 outer 루프에서 최단 거리 갱신됐을 때의 스냅샷들 (좌측 상단)

 

edge 순서가 (B,E), (D,B), (B,D), (A,B), (A,C), (D,C), (B,C), (E,D) 라고 가정하고

1번째 outer 루프가 실행되면 아래와 같이 최단 거리가 갱신된다.

1. (B,E), (D,B), (B,D) 갱신없음
2. (A,B) 1번째 갱신
3. (A,C) 2번째 갱신
4. (D,C) 갱신없음
5. (B,C) 3번째 갱신 - 앞서 B까지의 최단 거리가 갱신되었기 때문에 가능
6. (E,D) 갱신없음

 

2번째 outer 루프 갱신 과정 (좌측) - 그래프에서 점 B까지의 최단 거리 -1 생략되었음

 

위 과정대로라면 (B,E) -> (B,D) -> (E,D) 순서로 최단 거리가 갱신된다.

 

이 예제에서는 |V|=5 라서 outer loop가 4번 수행되지만,

이미 최대 2개의 선(edge)를 갖는, 시작점 A부터 다른 점들까지의 최단 거리 계산이 완료된다.

 

---

* 직접 실행해본, 테스트 샘플 코드

 - kotlin playground 에서 바로 실행해볼 수 있다.

 - 테스트 그래프 2개 중 1개는 위 예제 그래프를 사용했지만 outer loop 1번째에서 모든 계산이 완료된 이유는 등록한 edge 순서가 다르기 때문임을 감안

gist.github.com/Kelicia91/5233e9ee95357785c59f4a146f32a5a0

bellman-ford-algorithm

 

출처: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/