[알고리즘] 벨만포드 최단거리 알고리즘 정리

최단경로 알고리즘에는 다익스트라, 벨만포드, 플로이드 워셜 ... 이 가장 대표적인 알고리즘이다.

이번 포스팅은 벨만포드에 대해 알아보도록 하겠다.

 

이미 다익스트라 알고리즘을 알고있는 상태에서 왜 벨만포드 알고리즘이 따로 존재하고, 사용되는 것일까?

 

다익스트라 알고리즘와 벨만포드 알고리즘은 둘다 최단거리를 구할 수 있는 알고리즘임에 분명하다.

하지만 두 알고리즘에는 차이점이 존재한다.

 

다익스트라 알고리즘의 단점을 생각해보면 알 수 있다.

다익스트라 알고리즘은, 모든 간선의 길이가 양수(+)일때 최단거리를 보장한다.

혹여나 음수(-)의 간선이 존재한다면.. 최단거리를 구할 수 있지 못할 수도 있다.

 

벨만포드는 이러한 다익스트라의 단점을 해결할 수 있는 최단거리 알고리즘이다.

즉, 간선이 어떤 형태 ( 양수, 음수)던 상관없이 최단거리를 구할 수 있는 것이다.

 

그럼 어떻게 진행될까? 다익스트라와 굉장히 비슷하다.

 

1. 시작점을 제외한 나머지 V에 아주 큰값(inf)을 가지는 배열을 만든다. 이 배열은 시작점부터 각 노드까지 최소거리를 뜻한다.

2. 연결되어있는 간선들을 모두 체크하여 이동거리를 update한다.

3. V-1번 반복하여 진행한다.

 

이러한 과정을 통해 최단거리를 구할 수 있다.

하지만, 글로만 보면 의미전달에 한계가 있기에, 밑에 예제를 하나 넣어보겠다

아주 간단한 예제를 통해 전체적인 프로세스를 나타내 보았다.

다익스트라처럼 visit, 방문한 노드는 체크해주지 않아도 되므로 상대적으로 코드가 짧아질 수 있다.

 

하지만, 벨만포드의 단점도 존재한다.

바로 '음의 폐로'라는 경우가 존재할 수 있다.

벨만포드의 특징인 음의간선이 있어도 최단거리를 찾을 수 있다는 장점때문에 발생하는 것인데.. 밑의 그래프를 보자.

 

위와같은 그래프는 진행하면 할 수록, 1,2,3의 최단거리가 점점 줄어드는 것을 알 수 있을 것이다. 바로 '음의 폐로' 때문...

즉, 무한 사이클이 반복된다.

벨만포드는 이러한 단점을 가지고 있지만, 반대로 음의폐로가 존재하는지 안하는지 알 수 있기도 하다.

벨만포드는 V-1번 반복한 결과가 최단거리를 보장하지만, 이러한 음의 폐로가 존재한다면 최단거리를 보장하지 못한다.

즉, V번째 이동거리를 update할때, 최단거리가 update되었다면 음의 폐로가 존재한다는 것을 알 수 있다.