[computer science] single-source shortest path(2), Bellman-Ford Algorithm(벨만포드 알고리즘)

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

 

저번 시간에 다익스트라 알고리즘에 대해 배웠는데

다익스트라 알고리즘의 가장 중요한 특징 중 하나는

edge의 weight들 중에 negative weight가 있으면 안된다는 점이다

 

기본적으로 다익스트라는 greedy algorithm에

기초하고 있기 때문에

negative weight가 있으면 기존에 확정 되었던 값이

이후에 더 짧아지는 경우가 생길 수가 있는데

이는 greedy algorithm의 기본적인 가정에 반하게 되는 것이기 때문이다

 

따라서 edge들의 weight에 음수가 있는 경우

다익스트라 대신에 사용할 수 있는 알고리즘은 바로

Bellman-Ford Algorithm이다

 

 

Bellman-Ford 알고리즘은 weighted, directed graph에서 수행되며

edge들의 값이 음수값이 나올 수가 있다

 

그리고 또 한 가지 중요한 특징은

negative-weight cycle이 존재하면 안된다는 점이다

위 ppt의 그래프 경우 negative weight cycle이 존재하는 것인데

벨만포드 알고리즘 상, 무한 loop가 생길 수가 있다고 한다

 

벨만포드 알고리즘의 basic idea는

모든 vertex에 대해서 동시에 반복적으로

계속해서 업데이트를 하자는 것이다

 

 

이후에 관련 내용이 나올테지만

Bellman-Ford 알고리즘에는 pass라는 것이 존재한다

 

하나의 pass 안에서는 모든 edge들을 거치면서 업데이트한다

 

source vertex는 이전과 마찬가지로 0

나머지는 무한대로 초기화한다

 

그래프의 각각의 edge들을 순서에 관계없이

다 탐색하면 되는데 위 ppt의 사례를 한 번 보자

 

가장 처음에 무한대에서 무한대로가는 5 edge는

무한대에서 무한대이기 때문에 업데이트가 되지 않는다

그 이후로도 쭈욱 그렇다가 마지막에서 3번째 그림에서

z에서 s로 가는 2 edge를 탐색할 때

s가 0이기 때문에, 2보다 0이 더 작아서 업데이트하지 않는다

 

그 다음 s에서 t로 갈 때 드디어 업데이트가 되는데

무한대와 weight인 6을 비교하니, 6이 더 작기때문에

t을 6으로 업데이트하고 t.π를 s로 업데이트한다

 

마지막 그림에서는

s에서 y로 가는 edge를 탐색한 뒤

위와 동일하게 y를 7로

y.π를 s로 업데이트를 해주면

pass 1이 끝나게 된다

 

 

첫 번째 pass가 끝나고 두 번째 pass를 보자

 

t에서 x까지 가는 edge가 5이기 때문에

6+5=11이고

x값은 무한대이기 때문에 무한대보다 11이 더 작으므로

x에 11을 업데이트해준다

 

t에서 y는 6+8=14인데

14보다 7이 더 작으므로 업데이트를 하지않는다

 

t에서 z로 가는 것도 마찬가지

6+(-4)=2인데 무한대보다 2가 더 작으므로

2로 relax를 시켜준다

 

이러한 과정을 반복해서 2nd pass가 끝나면

가장 마지막 그래프의 상태가 된다

 

 

동일한 방식으로 3번째 pass도 수행해준다

 

 

동일하게 네 번째 pass도 수행해준다

 

위 그래프 예시에서 source s에서 vertex까지 도달하는데

총 포함이 되는 vertex는 아무리 많아봤자 5개이다

왜냐하면 전체 vertex가 5개밖에 없기 때문이다

그러면 포함되는 edge는 최대 4개가 된다

 

그래서 벨만포드 알고리즘에서 수행하는

총 pass의 수는 vertex의 개수 -1이다

 

 

위 그래프의 벨만포드 알고리즘을 table로 작성해보자

column이 pass이고 row가 vertex이다

 

table내용은 왼쪽 숫자가 distance

오른쪽이 precedessor값이다

 

첫 번째 pass인 iter 0 column에서는

s빼고 나머지는 다 무한대이다

 

그리고 2번째 pass에서 B는 2/C가 아니고 2/D이다

잘못표기된..

 

 

벨만포드 알고리즘의 pseudo code이다

 

INITIALIZE-SINGLE-SOURCE 코드를 보자

우선 그래프 G에 있는 모든 vertex에 대해서

무한대로 초기화 한 후, s만 0으로 다시 초기화해준다

precedessor는 nil로 설정해준다

 

그 다음 vertex개수 -1 만큼 loop를 돌면서

모든 edge에 대해 탐색하며 relax를 시켜준다

 

그다음 5번째 줄의 for문은

negative cycle이 존재하는지 판단하는 로직이다

만약 6번째의 if문이 한 번이라도 성립한다면

negative cycle이 있다고 판단되고 false를 Return하게 된다

 

만약 모든 edge에 대해 if문이 성립하지 않는다면

negative cycle이 없다고 판단하고

결과값을 그대로 true로 return한다

 

 

그렇다면 벨만 포드 알고리즘의 time complexity를 보자

 

처음 초기화하는 알고리즘은 O(V)

v-1만큼의 pass만큼 돌면서(O(V))

relax를 해주면 (O(E)) 이기 때문에

총 O(VE)만큼의 시간이 걸린다

 

negative cycle verification도

모든 edge를 탐색하므로 O(E)만큼 소요돼서

총 time complexity는 O(VE)에 bound되게 된다

 

 

 

벨만 포드 알고리즘의 증명이다

induction을 사용한 증명을 가져왔다

 

우선 다익스트라 증명과 동일하게

p는 가장 짧은 path를 나타낸다

 

이 때 우리가 증명해야하는 것은

어떤 vertex v의 distance가 실제 s에서 v까지 도달하는

최단거리와 동일한지이다

 

p는 cycle이 있을 수가 없으므로(negative cycle이 없다고 가정을 하기 때문)

p안에는 최대 v개의 vertex가 있을 수 밖에 없다

 

따라서 0부터 시작하는 k번째 vertex라는 뜻의 k는

v-1보다 같거나 작을 수 밖에 없다

그렇기 때문에 델타(s, v)는 v의 d값과 같아질 수 밖에 없다

 

 

Base Case를 설정해보자

만약 i가 0이라면

v0의 d값은 당연히 0이 되고

델타(s, s)가 되므로 이 값도 0이 된다

 

그 다음 inductive step을 살펴보자

i-1번까지 성립을 한다고 가정했을 때, i도 성립을 한다고 증명해야한다

 

vi의 d는 v(i-1)의 d에 i-1에서 i로 가는 weight를 더한 값보다 작거나 같다

왜냐하면 벨만포드 알고리즘의 로직을 보면

값이 더 작으면 더 작은 값을 업데이트해주고 더 크면 그대로 두기 때문이다

따라서 위 부등식은 성립하는 부등식이 된다

 

그리고 델타(s, v(i-1)) + w(v(i-1), vi)가

위 식과 같다고 inductive하게 가정을 해준다

 

이전 다익스트라 알고리즘을 증명할 때도

lemma를 하나 깔아줬었는데

shortest path가 있으면 그 안에 속해있는 subpath도

shortest path가 된다는 것이었다

 

따라서 위 inductive hypothesis는 lemma에 의해서

델타(s, vi)와 같다는 등식이 성립한다고한다

(사실 나도 잘 이해가 안ㄷ..)

 

 

이제 negative weight cycle이 없어야

벨만 포드 알고리즘이 True가 되는 것을 증명해보자

 

v의 d값이 실제 최단거리와 동일하다는 것은

이미 앞에서 증명이 되었다

 

s에서 v로 가는 최단 경로가 있는데

s에서 u라는 vertex를 임의로 잡았을 때

w(u, v)와 델타(s, u)의 합보다는

델타(s, v)가 작거나 같을 수밖에 없다

 

델타(s, u) + w(u, v)는

u.d + w(u, v)와 동일하고

따라서 pseudo code에서

v.d > u.d + w(u, v)가 성립한다는 것이

negative weight cycle이 없다면 불가능 한 것이므로

위 식이 성립할 경우 negative weight cycle이

존재한다는 것으로 간주하고 벨만포드 알고리즘은

False로 종료되게 되는 것이다

 

 

만약 negative weight cycle이 존재한다면

벨만 포드 알고리즘이 False를 뱉는 것에 대해 증명해보자

 

negative weight cycle이 있는데

그게 v0, v1, v2, ..., vk-1이라고해보자

 

위 v값들은 negative weight cycle을 이루고있기때문에

weight들을 모두 다 더하면 음수 값이 나온다

 

그리고 벨만포드 알고리즘에서 True가 나왔다고 가정해보자

true가 나왔다는 뜻은 6번째의 if문에 걸리지 않았다는 뜻이고

 

이 부등식이 성립한다는 뜻이 된다

 

이 식을 시그마를 붙여서 정리해주면

아래의 식으로 풀어쓸 수 있다고 한다

 

 

v0에서 vk-1까지가 negative weight cycle을

구성하고 있다고 가정했으므로

cycle이라는 특성 상 첫 번째 vertex와 마지막 vertex는 같아진다

 

따라서 v0과 vk-1은 같은 vertex가 되고

이에 따라 v는 i부터 k까지 더한 값과

v는 i-1부터 k-1까지 더한 값이 동일해진다

 

따라서

 

이 식이 성립하게 되는데

위 식은 앞에서 우리의 가정인

negative-weight cycle의 경우

weight를 모두 더한 값은 음수가 되어야한다는

가정에서 모순이 된다

(사실 나도 잘 이해가 ,,ㅎㅎㅎ 그냥 그렇구나하고 넘어가보자ㅠ)

 

 

벨만포드 알고리즘은 앞에서 배웠던

dynamic programming으로도 해결할 수 있다

 

dynamic programming step에 따라 정의해보자

 

 

dist[v][k]는 k번째 pass가 지나갔을 때

시작 vertex에서 마지막 vertex v까지의

shortest path를 나타낸다

 

따라서 우리가 구해야할 것은

k가 끝났을 때 dist[v][k]의 값이다

 

Base Case는

source s부터 자기 자신까지는 0이므로

dist[s][0] = 0

 

source s와 v가 다른 vertex라면

dist[v][0]은 0번째 pass이므로

무한대가 된다

 

그래서 이를 점화식으로 표현해보면

dist[v][k]는 k-1 pass에서의 값 그대로거나

k pass에서 더 작은 값이 있어 업데이트가 되었거나

둘 중에 하나가 된다

 

따라서 그것을 식으로 나타내면

이렇게 나타낼 수 있다

 

따라서 pass는 총 v-1번만 진행하므로

dist[v][v-1]이 shortest path를 포함하게된다

 

Bellman-Ford 알고리즘과 다익스트라를 비교해보자

 

벨만 포드 알고리즘은 기본적으로

다익스트라보다 느리다

 

하지만 벨만 포드 알고리즘은 negative weight가

있을 때 수행이 가능하다는 특징이 있다

 

negative weight는 보통 transportation과 같은 곳에서

reward의 개념으로 사용되기 때문에

이런 경우에는 벨만 포드가 유용하다고 할 수 있다

 

또 다익스트라와 벨만포드가 다른 점은

다익스트라는 vertex들을 순차적으로 탐색하지만

벨만포드는 distributed fashion으로

vertex들을 동시에 업데이트하는 방식으로 수행하고

globally하게 vertex를 업데이트 하는 것이 아닌

해당 vertex와 연결된 local information만을 업데이트시킨다

 

이런 벨만포드 알고리즘은 우리가 흔히 알고있듯이

네트워크 경로 계산에 유용하기 때문에

주로 사용되는 알고리즘이다

 

보통 네트워크에서 패킷을 보낼 때

여러 개의 router들을 거쳐서 전송을 하는데

패킷을 빨리 보낼 수 있는 shortest path를 찾아야하는데,

network information은 dynamic하게 변하기때문에

local information만 찾아서 빠르게 shortest path를

찾을 수 있는 벨만 포드 알고리즘이 유용하게 사용된다

 

 

Directed Acyclic Graphs (DAGs)

sssp를 찾을 때 다익스트라나 벨만포드 알고리즘말고

조금 더 단순하게 sssp를 찾는 방법이 있다

 

Directed Acyclic Graph라고

흔히 줄여서 DAG라고 부르는 방식이다

 

DAG는 negative weight cycle을 포함해서

cycle이 없으며

topological order로 자연스럽게 나타낼 수 있다

 

위의 예시를 보면 이해하기가 쉬운데

DAG는 linear ordering을 사용하는데

이게 무엇인가하면

임의의 edge(u, v)에 대해서

vertex u는 항상 vertex v의 왼쪽에 오도록

정렬을 한다는 뜻이다

 

그래서 edge의 방향들이 모두

왼쪽에서 오른쪽으로 갈 수 있게된다

 

 

위 예시에서는 두 번째 vertex가 source이다

차례대로 살펴보면 r에서 s로 갈 때는

0이 더 작기 때문에 업데이트를 시켜주지 않는다

 

s에서 t로 갈 때는 2가 더 작기 때문에 relax해주고

s에서 x로 가는 것은 6으로 relax를 해준다

 

그 다음은 t에서 x, y, z로 가는 것이 가능한데

x는 기존 값이 더 짧아서 update시키지 않고

y는 6으로, z는 4로 relax된다

 

이러한 방식으로 끝까지 동일하게 수행해주면된다

 

위 수행방식을 잘 살펴보면 눈치챘겠지만

source보다 앞에 있는 vertex들에 대해서는

죽었다 깨어나도 업데이트가 될 수 없다

source보다 앞에 있는 vertex들은

무조건 무한대가 된다

 

DAG의 pseudo code이다

 

일단 처음에 toplogically sort를 해준다

그다음 initialize를 해주고

for문을 통해서 왼쪽에 있는 vertex부터

topological order로 for문을 돌면서 relax를 시켜준다

 

 

time complexity를 살펴보자

 

기본적으로 모든 vertex들을 다 탐색하고

그래프에 있는 모든 edge들을 다 탐색하기 때문에

total time complexity는 O(V+E)가 된다