[Algorithm] Dynamic Programming(4) - 벨만포드(Bellman-Ford)

🤔Dynamic Programming

다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다.

 

다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다.

 

이번 포스팅에서는 최단 경로 문제중 하나인 벨만포드 알고리즘에 대해 알아보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 최단 경로 문제(Shortest Path Problem)

✍️ 최단 경로 문제란?

그래프 G = (V, E)의 상에서 정점 u에서 v로의 가장 짧은 경로의 길이를 구하는 문제를 최단 경로 문제라고 합니다.

 

우리는 edge-weighted graph의 경우만을 생각하도록 하겠습니다. ( 이때 |V| = n, |E| = m )

 

 

 

 

 

✍️ Edge-weighted graph

그래프 G의 edge(a, b)에 가중치 w(a, b)가 있는 그래프를 말합니다.

 

이때 정점 u에서 v로의 경로의 길이는 u에서 v로의 경로 상의 edge들의 총 가중치의 합이 됩니다.

 

아래의 그래프에서 정점 '0' 에서부터 '2'까지의 빨간색 경로의 거리는 '8 + 7 = 15' 입니다.

 

 

 

 

두 정점 사이에 여러 경로가 존재하는데 우리가 공부하는 최단 경로 문제는 그 중 가장 거리가 짧은 경로의 거리를 반환합니다.

 

위의 그림에서는 edge(0, 3)과 edge(3, 2)의 가중치를 더한 14가 최단 경로가 됩니다.

 

 

 

 

 

✍️ 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘은 최단 경로 문제 중 가장 대표적인 문제 중 하나입니다.

 

하지만 오늘 배울 벨만포드 알고리즘과는 다르게, 그래프에서 음수 가중치를 가지는 edge가 존재한다면 올바르게 동작하지 않습니다.

 

다익스트라 알고리즘을 해결하는 방법은 아래와 같습니다.

 

 

 

How To Solve

시작 정점 s(source) 에서 다른 모든 정점들 간의 최단 경로의 길이를 구하는 알고리즘

즉, 다른 모든 정점들간의 거리는 table로 저장하며, 정점을 하나 씩 방문해가면서 table을 업데이트 합니다.

 

 

 

Key Lemma

다익스트라 알고리즘에 정점 s에서부터의 길이가 방문하지 않은 정점 중 가장 짧은 정점을 v라고 할 때 해당 길이는 실제 s에서 v로의 최단 경로 길이와 같다.

 

따라서 다익스트라 알고리즘은 정점을 local optimum(주변의 다른 값들보다 더 좋은 값)에 기반하여 하나씩 방문하는 일종의 greedy 알고리즘입니다.

 

하지만 위의 Key Lemma는 가중치가 음수인 edge가 존재할 경우 성립하지 않습니다.

 

아래의 그래프에서 다익스트라 알고리즘은 Edge(s, v)가 s와 v 사이의 shorest path라고 답합니다.

 하,

 

하지만 실제 s와 v 사이의 최단 경로는 s - v' - v 입니다.

 

 

 

 

 

 

 

 

 

🔎 벨만포드 알고리즘

벨만포드 알고리즘은  최단 경로 문제를 해결하는 DP(Dynamic Programming) 기반의 알고리즘입니다.

 

다익스트라 알고리즘과 마찬가지로 시작 정점 s 에서 그래프 G의 다른 모든 정점들간의 최단 경로의 길이 및 경로를 구하며, 매 단계마다 해당 최단 경로들의 길이를 업데이트해 나가는 알고리즘입니다.

 

기본적으로 directed graph를 가정하며 undirected graph는 두 정점간의 방향을 모두 가지는 directed graph로 생각합니다.

 

다익스트라 알고리즘과는 달리가중치가 음수인 edge가 존재할 때도 올바르게 동작합니다.

 

 

 

 

✍️ Problem & Subproblem 정의

dist(u)를 정점 s 에서 u까지의 실제 최단 경로의 길이라고 하고 dis(i, u)를 'edge를 i개 이하로 사용하면서' vertex s 에서 u로 가는 shortest path의 길이'라고 하겠습니다.

 

 

 

 

✍️ Lemma

모든 i < j에 대해 dist(u) ≤ dist(j, u) ≤ dist(i, u)가 성립한다.

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

 

 

 

✍️ Recurrence Relation

base case) i = 0일 때, 즉, dist(0, s) = 0 나머지 v ∈ V에 대해서는 dist(0, v) = 무한대로 둡니다.

 

induction step) dis(i, v)가 주어졌다고 할 때 dis(i, v)가 주어졌다고 할 때 dis(i + 1, v)를 어떻게 구할까? 문제를 해결합니다.

 

dist(i, v) > dist(i, u) + w(u, v)를 만족하는 모든 edge(u, v)들 중 오른쪽 항을 가장 작게 만드는 edge(u', v)가 있다면

 

$$dis(i + 1, v) = dist(i, u') + w(u', v)$$입니다.

 

해당 edge가 존재하지 않는 경우 $dis(i+1, v) = dis(i, v)$입니다.

 

 

 

확인을 위해 예제 그래프를 살펴보겠습니다.

 

 

example

 

 

시작 정점 s에서 i개 이하의 edge를 지나 v에 도착하는 경우인 dis(i, v) = 3입니다.

 

dis(i+1, v)를 구하기 위해 정점 u에 도달할 때 dis(i, u) = 5라고 하겠습니다.

 

edge(u, v)의 가중치가 -6이라 할 때, $dis(i+1, v) = dis(i, u) + w(u, v) = -1 < dis(i, v)$를 만족하므로 위의 그래프에서 dis(i+1, v) = -1이 됩니다.

 

 

 

 

✍️ Algorithm outline

그러므로 벨만포드 알고리즘은 아래와 같이 나타낼 수 있습니다. 

 

 

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

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

 

 

 

 

 

 

 

 

위와 같이 값을 update할 때는 이전의 update한 값을 이용해야만 한다는 것입니다.

 

 

 

 

 

 

✍️ 수도코드

이를 수도코드로 나타내면 아래와 같습니다.

 

 

 

 

✍️ 실제 shortest path를 구하는 방법

위 알고리즘에서 dis(v)를 dis(u) + w(u, v) 로 업데이트 할 때마다 pre(v) = u로 설정합니다.

 

실제 경로는 알고리즘의 종료 후 v에서부터 pre(v)를 역으로 거슬러 올라가며 역추적할 수 있습니다.

 

 

 

 

 

✍️ Time Complexity

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Negative Cycle 판별하기

Negative cycle이 있는 경우 벨만포드 알고리즘은 path가 아닌 같은 cycle을 계속해서 도는 walk의 길이를 retrun 하게 됩니다.

 

쉽게 말해 cycle을 무한번 돌게 된다면 shortest path는 -무한대가 된다는 뜻입니다.

 

그러므로 벨만포드 알고리즘은 음의 가중치 edge가 있는 undirected graph 에서는 동작하지 않는다.( 위에서 정의했듯 undirected 그래프는 각각의 정점끼리 cycle이 존재하는 directed graph와 같기 때문)

 

또한 위의 성질을 역으로 이용하여 벨만포드 알고리즘을 이용해 graph가 negative cycle을 가지고 있는지 확인할 수 있습니다.

 

 

Negative Cycle 판별법

n-1번째 stage후, n 번째 stage를 추가로 수행하여 dist 값이 update 되는 경우 negative cycle이 존재합니다.

 

 

👉증명

해보자 해보자~

 

귀류법을 사용하여 이를 해결합니다.