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

• 개요

Bellman-Ford algorithm에 대해서 찾아보는데, 대부분 간단하게, 또 과정 위주로 설명되어 있고 왜 Bellman-Ford algorithm이 정당성을 가지는지, 또 왜 그러한 순서로 해도 문제가 발생하지 않는지에 대해 설명이 부족한 것 같아 직접 정리하기로 하였다.

---

• Single Source Shortest Path problems(SSSP)

 SSSP는 그래프 이론에서 아주 중요하고 또 자주 출제되는 문제이다. non-negative weighted graph와 관련된 문제의 경우에 Dijkstra's algorithm이 풀이에 사용되는데, 이는 time complexity가 O(VlogE)이므로 일반적인 graph에서 다른 알고리즘보다 빠른 측면이 있기 때문이다.

 

 그러나 Dijkstra's algorithm은 모든 edge가 non-negative weight를 가지는 경우에만 해결이 가능하다는 문제가 있다. 만약 negative edge가 있으면 답을 도출하지 못한다. 다음과 같은 예를 보자.

dijkstra's algorithm이 해답을 내지 못하는 directed weighted graph

 위 graph의 경우 shortest path는 {u, x, y, v}이지만 Dijkstra는 y를 먼저 방문한 이후에 y는 visited vertex set에 들어가기 때문에 x에 의해서 relaxation이 되어도 다시 방문할 수 없다. 따라서 {u, y, v}를 최단 경로라고 인식하게 된다. 

 

 • graph의 분류(negative weight가 존재하는지에 따라서)

 따라서 graph는 다음과 같은 세 종류로 구분될 수 있다.

 

1. non-negative weighted edge만 가지는 graph

2. negative weighted edge를 가지지만 negative weighted cycle을 가지지 않는 graph

3. negative weighted cycle을 가지는 graph (정답을 가지지 않는다)

 

 이에 대한 내용은 다른 곳에도 자세히 나와있으니 깊게 기술할 필요는 없어 보인다. 결론적으로는 1의 경우 Dijkstra's algorithm을 사용하는 것이 좋고, 2의 경우 Bellman-Ford algorithm으로 해결할 수 있다. 3의 경우도 Bellman-Ford algorithm으로 negative cycle을 인식하는 것이 가능하다.

 

---

• The Bellman-Ford algorithm

• 요약

• edge weight가 negative한 경우를 포함하여 general한 경우의 SSSP 문제를 해결한다.
• graph가 negative cycle이 존재하는지 boolean value로 리턴한다.
• time complexity는 O(VE)이다.

• 과정

pseudocode (사진 출처 : Introduction to algorithms)

 위 pseudocode를 보며 이해해 보면 간단하다.

1. 시작 지점인 s vertex만 0으로 초기화하고 나머지는 모두 vertex의 초기값을 INF로 초기화한다.(line 1)
2. vertex 개수만큼 iteration을 돌며 (line 2)
3. 모든 edge에 대해서 relaxation을 수행한다. (line 3)

이러면 모든 동작이 끝난다. line 5-8은 negative cycle을 검사하는 과정이다. negative cycle의 검사 과정에 대해서는 정당성 증명에서 보기로 하자.

 

중요한 점은 vertex의 iteration과 edge의 iteration은 어떤 순서로 진행하여도 아무런 상관이 없다는 점이다.

 

예시를 보며 직접 iteration을 수행해 보자.

negative weighted edge가 포함된 directed graph (사진 출처 : Introduction to algorithms)

어떤 순서로 iteration을 진행하여도 상관이 없음을 보여주기 위하여 <Introduction to algorithms>와 다르게 진행해 보겠다. 먼저 edge의 순서는 임의로 다음과 같이 정하자. 

이제 각 iteration을 수행한 후의 값을 표로 정리하면 다음과 같다.

 

default

v	s	t	x	y	z
v.d	0	INF	INF	INF	INF

 

iteration 1

v	s	t	x	y	z
v.d	0	6	4	7	16

 

iteration 2

v	s	t	x	y	z
v.d	0	4	4	7	2

 

iteration 3

v	s	t	x	y	z
v.d	0	2	4	7	0

 

iteration 4

v	s	t	x	y	z
v.d	0	2	4	7	-2

 

이는 모두 shortest path이다.

 

 

 

• 정당성 증명

Lemma 1

임의의 directed graph에 대하여 |V|-1 번의 iteration 이후에는 반드시 모든 vertex에 최단 거리가 저장된다.

 

Proof

shortest path가 최대로 가질 수 있는 edge의 수는 |V|-1이다. vertex s에서 reachable한 임의의 vertex에 대해서 최단 경로 p를 다음과 같이 정의하자.

이때 k <= |v|-1이 성립한다. Bellman-Ford algorithm에서는 |V|-1번 iteration을 하면서 모든 edge를 돌기 때문에 각 i번째 edge는 i번째 iteration에 relax된다. 따라서 path-relaxation property에 의해서 항상 최단 경로를 갖게 된다.

 

간단히 생각하면 어떤 경로를 거치던 간에 한 iteration당 한 edge씩 전진하다 보면 |V|-1에는 최단 경로가 |V|-1이어도 그 경로에 도달할 수 있다는 이야기이다.

 

 

Lemma 2 (음수 사이클의 존재성 증명)

만약 이미 |V|-1의 iteration이 수행된 이후에 negative cycle이 있으면 pseudocode는 false를 리턴한다.

 

Proof

이는 귀류법으로 증명할 수 있다. 임의의 graph G가 source에서 reachable한 negative cycle이 없다고 하자. Lemma 1에 의해서 reachable할 경우에는 각 vertex에 최단 거리가 저장된다. 만약 reachable하지 않다면 INF가 저장되어 있다. 만약 이 경우 임의의 vertex v에 도달하는 최단 경로 v.d는 다음 관계가 성립한다.

즉, 최단 경로는 s에서 v까지 가는 임의의 다른 경로보다 작거나 같다는 의미이다. 이 경우 pseudocode의 BELLMAN-FORD는 true를 항상 리턴한다.

 

그런데 만약 negative cycle이 존재하는 경우에도 true를 리턴한다고 해 보자.

negative cycle은 경로의 합이 0보다 작은 경로이므로 위의 식이 성립하지 않는다. 이는 전제에 어긋난다. 따라서 negative cycle이 존재하는 경우에는 Bellman-Ford algorithm은 false를 리턴한다.

 

 

---

• C++ implementation

• BOJ 11657 : 타임머신

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

Bellman-Ford algorithm 예제 수준의 문제이다. 단순히 Bellman-Ford algorithm을 구현하면 된다. 유의할 만한 점은 중간에 값이 int 범위를 벗어나는 경우가 있으므로 long long int로 구현해야 한다는 점과, source vertex와 직접 연결되어 있지 않은 경우에는 negative cycle이 존재해도 무시한다는 점이다. 

 

 

 

bool Bellman_Ford(vector<Edge_s>&edge, vector<ll>&dist) {
    init(dist);
    
    for(int i = 1; i < dist.size(); i++)
        for(int j = 1; j < edge.size(); j++)
            if(dist[edge[j].v] > dist[edge[j].u]+edge[j].cost && dist[edge[j].u]!=INF)
                dist[edge[j].v] = dist[edge[j].u]+edge[j].cost;
    
    for(int i = 1; i < edge.size(); i++)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].cost && dist[edge[i].u] != INF) 
            return false;
 
    return true;
}

 

 

이 문제의 전체 코드는 내 github에서 확인할 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/11657/11657.cpp

GitHub - Jordano-Jackson/PS: Problem solving

 

 

 

 

• 참고문헌

• Cormen, T. H., & Cormen, T. H. (2001). Introduction to algorithms. Cambridge, Mass: MIT Press.