Bellman-Ford Algorithm

두 번째 SSP (Single Source Shortest Path) 알고리즘은 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 이다.

다익스트라 알고리즘과 비교했을 때 가장 큰 특징은, 음의 가중치를 가지는 간선이 있어도 사용할 수 있다는 점이다.
주의할 점은, 음의 가중치를 가지는 순환고리가 있다면 최단 거리가 존재하지 않는다는 것이다.

예를 들어, A -> B 가 가중치 -5, B -> A 가 가중치 +2 라면, A 와 B 를 계속 왕복할수록 가중치가 무한히 작아질 수 있다.
벨만 포드 알고리즘은 음의 가중치가 포함된 그래프에서의 최단 경로를 구하는 것은 물론이고,위의 예시와 같이 음의 순환고리가 있는지 없는지, 최단경로가 존재하는지 그렇지 않은지 판단할 수도 있다.
이를 벨만 포드 알고리즘의 정확성이라고 한다.

하나의 단점으로는, (당연히) 다익스트라 알고리즘보다 시간복잡도가 크다.

---

벨만 포드 알고리즘에서는, “모든 정점에 대해” “모든 간선을” Relax 한다.
( 시간복잡도는 위에서 알 수 있듯이 $O(EV)$ 이다 )
이와 같이 비효율적인 이유는, 벨만 포드 알고리즘의 정확성과 관련이 있다.

우선, 알고리즘의 단계를 천천히 살펴 보자.

다익스트라 알고리즘과 비슷하게 dist 배열을 사용하며, (dist[i] : 노드 i 까지의 최단거리) 단계마다 이 dist 배열을 갱신해 줄 것이다.
Relax 단계는, 어떠한 정점에서 출발하여 모든 간선을 차례차례 확인해 보고, 만약 기존의 dist 배열의 값보다 작다면 갱신해 주는 단계이다.
확인하는 간선의 순서, Relax의 기준이 되는 정점의 순서는 중요하지 않다. Relax 과정의 횟수가 중요하다.

따라서, 필자는 다음과 같이 알고리즘을 구현하였다:
" 확인하는 간선의 순서를 고정시켜 두고, 모든 간선의 Relaxation 과정을 총 N번 진행한다 "

만약 음의 순환고리가 없다면, N번의 Relaxation 과정 후면 모든 점들의 최단 거리가 정해진다.
즉, N번의 Relaxation 후에는 다시 Relaxation을 진행하더라도 변화가 없다.
하지만, 만약 음의 순환고리가 있다면 결코 모든 점들의 최단 거리가 정해질 수 없기 때문에 N+1번째 Relaxation에서도 변화가 생긴다.
따라서, 우리는 이 변화 유무를 통해 음의 순환고리의 유무를 확인할 수 있다!!

즉, N번의 Relaxation을 한 후, 한 번 더 Relaxation을 진행하여 변화가 있다면 음의 순환고리가 있고, 변화가 없다면 음의 순환고리가 없는 것 이라고 결론지을 수 있다.

위와 같이 벨만 포드 알고리즘으로는 음의 순환고리의 유무와, 음의 순환고리가 없다면 한 점으로부터 모든 점들의 최단 경로들을 구할 수 있다.

필자가 직접 구현한 코드는
Baekjoon 11657 (타임머신)을 참고하라.