[Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘)

Shortest Path 를 구하는 대표적인 Alogorithm 으로는 Dijkstra Algorithm 이 있었습니다.

Dijkstra 알고리즘의 key lemma 는 다음과 같았습니다.

Dijkstra Algorithm 에서 (아직 방문 안 한 vertex 들 중) vertex s 에서부터의 shrotest path 길이가 가장 짧은 vertex 를 v라 하면 그 길이는 실제 s에서 v로의 shortest path 길이와 같다. 위 key lemma 는 weight 가 negative 인 edge 가 존재할 경우 성립하지 않습니다. 그 이유는 다음과 같습니다.

 

dijkstra algorith에서 negative edge 가 존재할 경우 올바르게 동작하지 않는 이유

 

그렇다면 negative edge 가 있는 경우에도 동작하는 Shortest path 를 구하는 Algorithm은 무엇이 있을까요?

 

The Bellman-Ford Algorithm

벨만-포드 알고리즘은 Shortest path 문제를 해결하는 dynamic programming 기반 알고리즘입니다. 다익스트라 알고리즘과 마찬가지로 source s 에서 G의 다른 모든 vertex 들 간의 shortest path 의 길이 (및 경로)를 구하며 (single-source shortest path), 매 step 마다 해당 shortest path 들의 길이를 update 해 나가는 알고리즘입니다. 기본적으로 directed graph를 가정하며 undirected graph 는 모든 edge(u,v) 에 대해 edge(u,v)와 (v,u) 를 모두 가지고 있는 directed graph 로 생각해줍니다. (이 경우에 w(u,v) = w(v,u)) 다익스트라 알고리즘과는 달리 weight 이 negative 인 edge가 존재하는 경우에도 올바르게 동작합니다.

 

벨만-포드 알고리즘이 다이나믹 프로그래밍 기반의 알고리즘이였으므로, Recurrence Relation 을 살펴보도록 합시다.

 

dist(u) 를 vertex s 에서 u 까지의 실제 shortest path의 길이라 하고, dis(i, u)를 'edge를 i개 이하로 사용하면서' vertex s 에서 u로 가는 shortest path의 길이라고 합시다. 그러면, 다음과 같은 lemma 가 성립합니다.

lemma : 모든 i < j 에 대해 dist(u) <= dist(j,u) <= dist(i,u)

따라서 G가 negative cycle (weight 의 합이 negative 가 되는 cycle) 이 없을 시, dist(u) = dist(|V|-1, u)가 됩니다.

Base case : i = 0, dist(0, s) = 0 나머지 v ∈ V에 대해선 dist(0, V) = INF 로 둡니다.

Inductive Step : dis (i, v) 가 주어졌다고 할 때 dis(i+1, v) 구하기. 

Inductive Step 에 대한 증명

따라서 Algorithm 의 전체적인 흐름은 다음과 같습니다.

1. 알고리즘은 총 0 ~ n-1의 stage(iteration)으로 구성되며, i번째 stage 가 끝날 때마다 G의 모든 vertex v 에 대해 dist(i, v)가 dist(v)에 저장됩니다. 

2. 0번째 stage에서는 앞선 base case에 맞게 dist 값을 정해줍니다.

3. 이후 i번째 stage 마다 모든 edge (u, v)에 대해 다음 작업을 반복합니다. dist(v) > dist(u) + w(u, v) 인 경우 dist(v)를 dist(u) + w(u, v)로 update.

 

Time Complexity 분석

벨만-포드 알고리즘의 시간 복잡도는 다음과 같습니다.

(n번의 stage) * (각 stage 마다 |E| = m 개의 edge를 check 하며 dist 값을 update) = O(nm)

 

다만, 벨만-포드 알고리즘도 negative cycle 이 없을 시에 작동한다고 했습니다. negative cycle 이 있는 경우 다음과 같은 문제들이 발생하게 됩니다. 

 

1. Negative Cycle 이 있는 경우, Bellman-Ford Algorithm은 path 가 아닌 같은 Cycle 을 계속해서 도는 walk의 길이를 return 하게 됩니다. 따라서 Bellman-Ford 알고리즘은 negative weight edge 가 있는 undirected graph 에서는 동작하지 않습니다. negative cycle 이 있는 경우, stage를 돌 때마다 최단 경로가 계속해서 갱신되기 때문입니다.

 

2. 또한 위 성질을 역으로 이용하여 Bellman-Ford Algorithm 을 이용해 graph 가 negative cycle을 가지고 있는지 check 할 수 있습니다. n-1 번째 stage 후 n번째 stage 를 추가로 수행하여 dist 값이 update 되는 경우 negative cycle이 존재합니다. (Why? -> negative cycle 이 없는 경우, n-1 번째 stage 에서 더 이상 최단 경로가 갱신되지 않기 때문임을 보이면 됩니다.)