개요

기본적으로는 “한 노드에서 다른 노드들까지의 최단 거리를 구하는 알고리즘”이라는 점에서 다익스트라랑 목적이 동일하다.

정점 개수 = V, 간선의 개수 = E 일 때, 다익스트라의 시간 복잡도는 (우선순위 큐를 쓰는 경우) O((V+E)lgV)이고, 벨만-포드의 시간 복잡도는 O(VE)이다. (단순 식으로는 각각 O(N lg N), O(N^2)) 그럼 더 효율적인 다익스트라가 있는데 왜 굳이 벨만-포드를 사용하는가 할 수 있는데, 다익스트라는 음의 가중치가 있는 경우 최적 해를 찾을 수 없다.

따라서 그래프에 음수 가중치를 갖는 간선이 존재하는 경우, 벨만 - 포드 알고리즘을 사용한다.

다만 벨만-포드라도 “음수 사이클”이 있다면 정확한 최단 경로를 산출할 수 없다. 이 경우 정확한 최단 경로를 구할 수는 없지만 “음수 사이클”이 존재하는지는 확인 가능하기 때문에 두 가지 목적으로 사용된다고 볼 수 있을 것 같다.

• 음수 가중치를 갖는 간선이 있는 그래프에서, 한 노드에서 다른 노드들까지의 최단 거리를 구하기 위하여
• 음수 가중치를 갖는 간선이 있는 그래프에서, 음수 사이클이 존재하는지 확인하기 위하여.

음수 사이클

특정 간선들을 반복하여 이동하면서 가중치 총합이 무한히 작아질 수 있는 경우.

예컨데 이런 경우, 2-3-5을 이동하는 경우 2+2+(-5)로 가중치 총합이 -1이며, 이를 반복하면 가중치 총합은 무한히 작아질 수 있다.

이 경우를 “음수 사이클”이라 한다.

알고리즘

과정

1. 테이블을 초기화하고, 출발 노드를 지정한다.
2. 기본적으로는 아래 과정을 (V-1)회 반복한다.
   1. 모든 간선을 확인하여
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하고 테이블을 갱신한다.
3. 1을 다시 한번 수행했을 때 테이블 갱신이 일어난다면, 음수 사이클이 존재한다.

• 벨만-포드 또한 다익스트라처럼 “한 노드에서 다른 모든 노드로의 이동 비용”이기 때문에 출발 노드를 지정해야 한다. 하지만 그래프 내 음수 사이클의 존재 여부를 확인하는 것이 목적이라면, 출발 노드는 어떤 것으로 지정해도 상관없다.
• 1-a에서 “모든 간선”을 확인한다는 사실에 주목해야 한다. 출발지와 도착지가 중복되는 간선이 있더라도 어차피 모든 간선을 확인하기 때문에, 입력받을 때 이를 고려하지 않아도 된다. (물론 극한의 최적화를 위해서라면 중복확인을 할 수도 있겠지만, 어느 쪽이 더 효율적일지는 모르겠다. 웬만한건 메모리 사용량을 늘리면 해결된다.)