Bellman Ford Algorithm의 설명 및 Python code
Bellman Ford Algorithm의 설명 및 Python code
그래프 구조가 주어졌을 때, 한 점에서 다른 점까지 가는 최단경로를 찾는 문제는 컴퓨터 공학에서 많이 다루는 문제입니다. Bellman Ford는 방향 그래프에서 양수와 음수의 weight가 모두 가능한 Shortest path 알고리즘입니다.
* Negative Cycle에 대해서는 적용할 수 없는데, Negative Cycle은 Cycle을 계속 돌수록 가중치가 음의 무한대로 작아지기 때문입니다.
Bellman Ford 알고리즘의 기초가 되는 철학은 relaxation 입니다. relaxation이란 문제를 해결함에 있어서 조금더 쉬운 문제로 풀고 이를 토대로 원래의 해를 찾는 것을 말합니다. 예를 들어서, 서울에서 부산까지 가는 경로에는 굉장히 많은 도시들이 있습니다. 최적의 경로를 생각할 때, 중간에 대전을 끼고 서울-대전, 대전-부산으로 가는 경로를 생각한다면, 문제는 조금더 쉽게 풀릴 수 있습니다.
Bellman Ford Algorithm
Bellman Ford 알고리즘은 이중 Loop로 구성됩니다.
먼저 안쪽 Loop는 모든 Edge에 대해서 Relaxation을 합니다. 이를 통해서 모든 Edge를 이용해서, 노드까지 방문하는 weight를 줄이게 됩니다.
Pseudo-Code는 다음과 같습니다.
실제 예제를 가지고 총 4번의 Relaxation을 진행하면 다음과 같습니다.
Distance가 update되면서 총 4번의 Relaxation으로 각 노드까지 Distance를 구할 수 있었습니다. 여기서 4 = |V|-1 과 값이 같았는데, 이는 |V|-1 번의 Iteration이 수렴을 보장하기 때문입니다. 그림에서 보듯이 처음 부분에는 초록색 주변의 노드에 대한 최소거리가 업데이트 되면서 나중에는 그렇게 구한 최소거리가 오른쪽 노드들에도 영향을 주는 것을 볼 수 있습니다. 따라서 |V|-1 번의 Relaxation을 한다면 Shorest Distance를 보장하게 됩니다.
Python Implementation
함수는 두 가지로 구분해서 작성하였습니다.
- 최소거리와 전임자(노드방문경로)를 알고 싶을 때
- 최소거리만 알고 싶을 때
# bellman ford algorithm works with a graph in which edges can have negative weights
import math
def bellman_ford1(num_vertexs, edges, source):
# distance from source to the other vertext
distance = [math.inf for i in range(num_vertexs)]
distance[source] = 0
# precedessor to the node
precedessor = [None for i in range(num_vertexs)]
for i in range(num_vertexs-1):
# relaxation
for e_source, e_dest, e_weight in edges:
if distance[e_dest] > distance[e_source] + e_weight:
distance[e_dest] = distance[e_source] + e_weight
precedessor[e_dest] = e_source
# negatie cycle when another way is shorter.
for e_source, e_dest, e_weight in edges:
another_weight = distance[e_source] + e_weight
assert distance[e_dest] <= another_weight
return distance, precedessor
def bellman_ford2(num_vertexs, edges, source):
# distance from source to the other vertext
distance = [math.inf for i in range(num_vertexs)]
distance[source] = 0
for i in range(num_vertexs-1):
# relaxation
for e_source, e_dest, e_weight in edges:
if distance[e_dest] > distance[e_source] + e_weight:
distance[e_dest] = distance[e_source] + e_weight
# negatie cycle when another way is shorter.
for e_source, e_dest, e_weight in edges:
another_weight = distance[e_source] + e_weight
assert distance[e_dest] <= another_weight
return distance
if __name__ =="__main__":
edges = [(1,2, 10), (2,3,-2), (4,2,3), (0,3,5),
(0,1,2), (4,3,6), (1,3,6),(1,4,6) , (3,1,10)]
num_vertexs = 5
distance1, precedessor1 = bellman_ford1(num_vertexs, edges, 0)
distance2 = bellman_ford2(num_vertexs, edges, 0)
print(distance1, precedessor1)
print(distance2)Addtional Tip - Dijkstra's Algorithm
사실 Dijstra's Shortest Path Algorithm 또한 relaxation을 통해서 해를 구합니다. Bellman Ford와 다른 점이 있다면, 다익스트라는 노드에서 근처에 가까운 노드를 Heuristic하게 찾으면서 해를 구한다는 것 입니다. 따라서 일부 노드에서 구한 해가 점차 다른 노드로 영향이 가는 것은 Bellman Ford 알고리즘과 유사합니다. 대신 Dijkstra's Algorithm은 음수 weight에 대해서는 사용할 수 없는데, Relaxation을 하면서 해를 만들 때, 최소거리로 찾아서 다른 길로 노드를 방문한 것이 항상 크다는 가정이 있기 때문입니다. 이 가정에서는 Negative Weight 가 있다면 거짓이 되므로 양수의 weight를 가진 경우에만 사용할 수 있습니다.
References
[1] Wikipedia Bellman Ford
https://en.wikipedia.org/wiki/Bellman–Ford_algorithm#cite_note-Bang-1