[삼성 알고리즘] 벨만-포드 알고리즘(Bellman-Ford)

안녕하세요!!

이번에 포스팅할 내용은 바로 벨만-포드 알고리즘 입니다!!

 

벨만-포드 알고리즘은 지난번에 소개드린 다익스트라 알고리즘의 음수사이클에서의 문제를 극복하기 위한 변형 알고리즘입니다.

 

다익스트라 알고리즘은 아래 URL을 이용해주세요~!

https://bluemoon-1st.tistory.com/16

 

벨만-포드는 다익스트라와 같은 방식으로 동작하며 모든 노드를 바탕으로 순환을 진행함으로써 경로 내에 음의 순환이 존재하는지 체크할 수 있는 기능을 가지고 있는 알고리즘입니다.

 

하지만, 위에서 언급한 바와 같이 다익스트라의 연산 과정을 모든 노드에서 진행하기 때문에 많은 연산을 자랑합니다...

본격적으로 예시를 들어 설명을 진행하겠습니다.

 

먼저 벨만-포드 알고리즘의 순환 순서는 개발자의 마음대로 입니다. 포스팅에서는 벨만-포드의 이해가 쉽도록 순서를 진행하겠습니다.

 

위와 같이 노드가 존재할 때 우선 1을 시작노드로 벨만-포드 알고리즘을 진행하겠습니다. 처음 표는 모두 무한대 값으로 초기화되며 1이 시작노드이기 때문에 1의 값은 0으로 셋팅해도 무방합니다.

 

처음 동작을 보면 1번노드에서 갈 수 있는 2번노드와 5번노드의 비용은 각가 5,6이고 무한대와 비교했을 때 더 작은 값이므로 표에 값을 셋팅합니다.

 

 

 

다음으로 2번노드에서 3번노드로 이동할 때 비용이 5이므로

5(2번까지의 비용)+5(2에서 3으로의 비용)=10이 되는데 무한대보다 작은 값이므로 10으로 값을 셋팅합니다.

 

 

그리고 3번노드에서 진행을하면 -2가 존재하므로 2번노드 비용을 다시 비교합니다. 이 때 3번노드의 비용 10에서 -2를한 8과 기존의 5와 비교했을 때 5가 작으므로 수정되지는 않습니다. 그리고 4번노드 역시 값이 셋팅됩니다.

 

그리고 체크하지않은 남은 edge의 체크를 진행합니다.

 

먼저 해당 edge를 체크하면 기존의 4번노드로 이동하는 비용 17은 1->5->4 일 때 7의 비용보다 크므로 값이 다시 셋팅됩니다.

 

5번노드에서 2번노드로의 이동은 최솟값이아니라 변경되지 않지만 4번노드에서 2번노드로 이동 시 최솟값 3이되므로 2번노드의 비용을 2로 다시 셋팅합니다.

 

이렇게 1번노드에서 출발했을 경우 모든 edge를 체크함으로써 1,2,3,4,5 노드의 비용을 구할 수 있었습니다.

마찬가지로 같은 방법을 2,3,4,5 노드를 시작점으로 반복을 진행합니다.

2번노드를 시작으로 순환을 진행할 때 2번노드에서 3번노드로 진행할 때 마지막으로 3번노드의 비용이 8로 변화합니다.(전에 4번노드에서 2번노드로 -4 비용을 통해 2번노드의 값이 바뀌었기 때문)

 

이후 모든작업은 표의 변화에 영향을 끼치지 않습니다. 때문에 벨만-포드에서는 음수의 비용에 대해서도 효과적으로 처리를 할 수 있습니다.

하지만 벨만-포드 역시 다익스트라와 마찬가지로 음수 사이클이 존재하는 경우에는 정상적인 표를 만들 수 없습니다.

 

음수 사이클이 존재하는 경우 방금 -4비용을 통해 2번노드의 값이 바뀌고 이어서 3번노드의 값이 바뀐 것처럼 계속 값이 바뀔 수 밖에 없기 때문입니다. 하지만 벨만-포드는 모든 노드의 순환을 통해 음수사이클의 존재여부를 판단할 수 있고 음수사이클이 존재하는 경우 false를 return함으로써 그래프 구조의 문제점을 지각할 수 있습니다.

 

결과적으로 벨만-포드는 다익스트라의 변형을 통해 음수간선에 대한 처리 및 음수사이클을 체크하기 위한 알고리즘입니다.

마지막으로 벨만-포드의 시간복잡도를 계산해보면 최악의 경우 다익스트라 알고리즘이 O(N^2)를 가지게 되는데 이 때, 벨만-포드는 모든 노드 즉 노드의 개수 N만큼 다익스트라 알고리즘의 계산을 반복하므로 O(N^3)의 효율성을 가지게 됩니다.

 

이상으로 벨만-포드 알고리즘의 포스팅을 마치겠습니다.

감사합니다~!!