Weighted Graph에서 최단거리를 찾는 Bellman-Ford Algorithm

Bellman-Ford(벨만 포드) 알고리즘은 Dynamic Programming 기반으로 Edge-Weighted Graph에서 최단거리를 계산하는 알고리즘이다.

특정 Vertex(source)에서 다른 모든 vertex로의 shortest path를 구하며(single-source shortest path), 매 step 마다 해당 shortest path의 distance를 update하는(dynamic) 알고리즘이다.

이 때, 다른 알고리즘과 구분되는 점은 Edge의 Weight가 negative여도 올바르게 동작한다는 점이다.

 

벨만 포드 알고리즘은 다음의 recurrence relation 아래 작동한다.

 

dist(u) = vertex s에서 u까지의 실제 shortest path의 길이
dist(i,u) = 'edge를 i개 이하로 사용'하면서 vertex s에서 u로 가는 shortest path의 길이

이 때, Lemma로서 모든 i<j에 대해 dist(u)<=dist(j,u)<=dist(i,u)가 성립한다.

(더 많은 edge 개수를 고려할 수록 더 많은 path를 계산할 수 있기 때문)

그리고 G가 ⭐negative cycle(weight의 합이 negative가 되는 cycle)이 없을 시⭐에 dist(u) = dist(|V|-1, u)가 성립한다.

👉 DP기반의 알고리즘이기 때문에 negative cycle이 있을 때 에는 해당 step에서 negative cycle을 반복적으로 도는 선택을 하게 된다. 하지만 negative cycle을 계속해서 도는 것은 shortest path가 아닌 walk(방문한 vertex를 1번 초과 방문)를 찾게 되고, V-1번의 stage가 끝났을 때 의도한 결과를 얻을 수 있을 것이라는 보장이 없다. 실제로 negative cycle이 있는 경우에는 path가 아닌 같은 cycle을 계속해서 도는 walk의 길이를 return한다.

 

1️⃣ Base case(i=0):

• dist(0,s) = 0 -> 자기 자신으로의 dist=0
• dist(0,v) (v는 s를 제외한 나머지 vertex) = INF -> edge를 0개 거쳐 다른 vertex로 가는 방법은 없다

2️⃣ Inductive step: 

• dist(i, v)가 주어졌다고 할 때 dist(i, v) > dist(i, u) + w(u, v)를 만족하는 모든 edge들 중 우항을 가장 작게 만드는 edge(u', v)가 존재한다면
• dist(i+1, v) = dist(i, u') + w(u', v)이다.

위의 그림을 보면, edge를 i개 거쳐 v로 가는 shortest path는 기존 3으로 저장되어 있다.

이 때 edge를 하나 더 추가해서, s에서 u로 간 뒤 u에서 v로 가는 path의 cost가 더 작다면 해당 path로 update해줄 수 있다.

(물론 기존의 cost가 더 작다면 그대로)

 

따라서 Bellman-Ford알고리즘의 개요는 다음과 같다.

1️⃣ 총 0~|V|-1개의 stage(iteration)으로 구성되며, i번째 stage가 끝날 때 마다 G의 모든 vertex v에 대해 dist(i, v)가 dist(v)에 저장된다(loof invariant).

👉 왜 n-1개의 stage일까? vertex의 개수는 |V|개이고, 모든 vertex를 거쳐서 destination으로 도달하기에는 |V|-1개의 edge만 필요하다(그 이상은 path가 아닌 walk가 된다).

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

3️⃣ 이후 i번째 stage마다 모든 edge(u, v)에 대해 update를 진행한다(dist(v)>dist(u)+w(u, v)인 경우 dist(v)를 update).

Bellman-Ford 알고리즘의 동작

 

procedure bellman-ford(G, l, s)
Input:	Directed Graph G=(V, E)
		edge lengths {le : e∈E} with no negative cycle
        vertex s∈V
Output:	For all vertices u reachable from s, dist(u) is setto the distance from s to u

for all u ∈ V:
	dist(u) = ∞
    prev(u) = nil

dist(s) = 0
repeat |V|-1 times:
	for all e ∈ E:
    	dist(v) = min{dist(v), dist(u) + l(u, v)} 

이 때 실제 shortest path를 구하기 위해서는 각 vertex마다 prev(v)를 유지하고, dist값이 update될 때 마다 prev(v) = u로 update해주면 된다. 

➕ negative cycle이 있으면 동작하지 않는 원리를 이용하여 negative cycle의 유무를 검사할 수 있다.

👉 n-1번째 stage 후 n번째 stage를 추가로 실행하여 dist값이 update되는 경우 negative cycle이 있다

 

Time Complexity

👉 (n번의 stage) * (각 stage마다 |E|=m개의 edge를 check하여 dist값을 update) = O(nm) (v-1 ≤ m ≤ v^2)