반응형

벨만 포드 알고리즘(Bellman-Ford Algorithm)이란?


그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용할 수 있다.

그래프 공부 시, 아주 중요한 알고리즘이며, 

이 알고리즘 및 다익스트라 알고리즘(Dijkstra Algorithm) 그리고 

플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) 이 3가지 알고리즘을 통해 최단 경로를 구할 수 있다.


이러한 세가지 알고리즘은 각각 정점과 간선의 개수가 어떻게 구성되냐에 따라 시간 복잡도의 차이가 있기에,


각 상황에 맞는 알고리즘을 이용하면 된다.


이번 게시물에서는 벨만 포드에 대해 알아 보도록 한다.



벨만 포드 알고리즘은, 다익스트라에서 할 수 없었던 음의 가중치도 계산 할 수 있도록 한 방식이지만


다익스트라보다 시간 복잡도가 높기에(더 느리기에) 어떤 상황에서 이용해야 할 지 잘 생각하여 써야한다.



우선 벨만 포드 알고리즘에 대한 전제 조건은 다음과 같다.


1. 최단 경로는 사이클을 포함할 수 없기 때문에, 최대 |V|-1개의 간선만 사용할 수 있다.

즉, 3개의 노드가 있을 때, 2개까지 간선만 허용한다는 의미이다.

2. 최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해주고, 음의 가중치로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.) 



다음은 벨만 포드 알고리즘의 시간 복잡도 공간 복잡도 분석이다.








벨만 포드는 그림을 통해 확인해 보는것이 글보다 더 쉽다.




다음과 같이 방향이 존재하는 정점 5개, 간선 9개의 그래프가 주어져있고, 0에서 2로 가는 최단 거리를 구해보자.


벨만 포드 알고리즘을 통해 최단 거리를 구하는 방식은 

계속해서 모든 간선을 이용하여 a정점에서 b정점으로 갈 때, 거리가 짧아지는 경우가 생긴다면 계속 업데이트를 해주는 방식이다.

V(정점)*E(간선)번 반복후 종료 된다.



 << 첫번째 itreation(반복) >> 



처음에는 모든 정점에 대해 최단 거리를 무한대로 설정한다. 


그리고 0번 정점에서 2번 정점의 최단거리를 구하니 0번 정점에 대해서는 최단 거리를 0으로 설정한다.


첫번째로 0에서 1로가는 간선이 없으니 0에서 2로 가는 간선을 보자.


가중치가 1이므로 2번 정점에 대한 최단 거리를 1로 업데이트 해준다.(1이 무한대 보다 최단거리니)



그리고 3번 노드를 확인하고 최단 거리를 5로 업데이트 해준다.



0번 정점 -> 1,2,3,4번 정점에 대한 모든 확인이 끝났으니 1번 정점으로 간다.


1번 정점 -> 2번 정점은 (무한대 - 2) > 1(현재 2번 정점의 최단거리)이므로 업데이트 하지 않는다.



1번 정점에 대한 확인이 끝났으니, 2번 정점으로 간다.


2번 정점 -> 1번 정점은 간선의 가중치가 4이니, 2번까지의 최단 거리 합(1) + 가중치(4) = 5를 1번 노드에 업데이트한다.



2 -> 3 :: 1 + 4 = 5를 업데이트해준다.



2번에 대해서도 끝이 났으니 3번 정점으로 이동한다.


3 -> 0 :: 5-1 = 4이지만, 0번에는 이미 0이 저장되어 있기에 4 > 0 이므로 업데이트 하지 않는다.



3 -> 1 :: 5 + 3 > 5 이기에 업데이트 하지 않는다.



3번에 대해서도 끝이 났으니 4번을 확인한다.


4 -> 0 :: 무한대 + 1 > 0 , 따라서 업데이트 하지 않는다.



4 -> 2 :: 무한대 - 1 > 1 , 따라서 업데이트 하지 않는다.


이렇게 첫번째로 첫번째 itreation을 끝냈다.



 << 두번째 itreation(반복) >> 



0에서 1로 갈 때 업데이트 할 것이 없으므로 하지 않는다.



0 -> 3 :: 업데이트 하지 않는다.



1 -> 2 :: 업데이트 하지 않는다.



2 -> 1 :: 업데이트 하지 않는다.



2 -> 3 :: 업데이트 하지 않는다.



3 -> 0 :: 업데이트 하지 않는다.



3 -> 1 :: 업데이트 하지 않는다.



4 -> 0 :: 업데이트 하지 않는다.



4 -> 2 :: 업데이트 하지 않는다.


결국 아무것도 업데이트 하지 않았고, 3,4,5번째 반복에서도 업데이트가 되지 않는다.


하지만 계속 반복한다는 점은 알고 있어야한다.



실제 벨만 포드 알고리즘이 추적한 경로는 다음과 같다.




결국 0에서 N의 최단 거리는 다음과 같다.

0 -> 0 :: 0

0 -> 1 :: 5

0 -> 2 :: 1

0 -> 3 :: 5

0 -> 4 :: INF(0에서 4로 가는 길이 없으므로 초기화 한 무한대가 된다.)


따라서 0에서 2까지의 최단 거리는 1이다.


이렇게 구하는 알고리즘을 벨만 포드 알고리즘(Bellman-Ford Algorithm)이라고 한다.


소스 코드는 다음 게시물에 올릴 예정이다.




반응형