Shortest Path Algorithm - Bellman-Ford

Bellman-Ford

벨만 포드 알고리즘은 음수 가중치가 있고, 음수 사이클이 없는 그래프에서 한 정점으로부터 다른 모든 정점으로의 최단경로 및 거리를 구하는 알고리즘이다. 다익스트라와는 달리 간선에 음수 가중치가 있어도 본래의 시간복잡도를 가지고 동작하며(단, 이 때에는 무방향 그래프가 아니어야 한다), 음수 사이클이 있는 경우는 무한히 사이클을 루프할 수 있다는 점에서 최단경로를 구할 수 없다. 단, 벨만 포드 알고리즘의 장점은 그래프 내에 음수 사이클이 있을 경우, 음수 사이클이 있음은 판단할 수 있다.

벨만 포드는 다음과 같이 동작한다.

시작점을 제외한 모든 정점으로의 최단거리를 무한으로 설정한다(시작점은 0). 이후 다음 수행을 반복한다.

1. 그래프 내에 모든 간선에 대해 2번을 시행한다.

2. 정점 A에서 정점 B로의 방향을 가지고 있는 각 간선에 대해 현재 정점 B까지의 거리가 정점 A까지의 거리와 현재 간선의 거리의 합보다 클 경우, 정점 B의 경로와 거리를 갱신해준다.

3. 이를 경로와 거리의 갱신이 일어나지 않을 때까지 반복해준다. 만약, 정점의 수 만큼의 시행 이후에도 경로와 거리의 갱신이 일어날 경우, 음수 사이클이 존재한다고 판단한다.

벨만 포드 알고리즘의 정당성 증명은 다음과 같다.

시작점부터 임의의 정점까지의 최단경로가 위와 같다고 하면, 마지막 정점으로의 최단경로를 알기 위해서는 마지막 정점 이전의 정점까지의 최단경로를 알아내야 한다. 만약 이를 알고 있다면, 그래프 내의 모든 간선에 대해 2번을 수행 하는 것으로 마지막 정점으로의 최단경로를 갱신해줄 수 있다(마지막 이전 정점의 최단경로와 마지막 이전 정점과 마지막 정점을 잇는 간선의 경로 합은 최단경로라고 가정했기 때문이다.) . 시작점 자체는 최단경로임이 보장되기 때문에(음수 사이클이 없으므로) 귀납적으로 임의의 최단경로를 구하기 위해서는 (그 최단경로의 전체 정점 - 1)회의 1, 2번 과정을 수행하면 최단경로를 구할 수 있음을 알 수 있다.

임의의 최단경로에 같은 정점 A을 2회 이상 방문한다면, (처음 방문한 A - 마지막에 방문한 A)의 사이클이 만들어진다. 이 경로를 갱신하는 것이 최단경로라고 한다면, 이 사이클은 무조건 음의 거리합을 가지는 사이클이 된다. 즉, 음의 사이클이 없다면 임의의 최단경로에서 같은 정점을 2회 이상 방문하는 경우는 없고, 최단경로는 최악에 그래프 전체 정점 수 만큼의 정점 수를 가지게 된다.

이제 벨만 포드 알고리즘을 진행하면 음의 사이클이 없는 경우 최단경로를 (그래프 내 전체 정점 수 - 1) * (전체 간선 수)의 시행으로 구할 수 있음이 증명되었다. 남은 것은, 이후에도 갱신이 진행될 경우, 음의 사이클을 가짐을 보이는 것이다.

먼저, 전제 정점 수 만큼의 시행에도 갱신이 이루어진다면, 어떠한 최단 경로는 (전체 정점 수 + 1)이상의 정점을 경로 상에 가지게 된다. 비둘기 집의 원리에 의해 어떠한 한 정점은 두 번 이상 경로에 나오게 되고, 그 사이의 경로를 보면 사이클임을 알 수 있다. 만약, 이 사이클이 음이 아닌 사이클이라면 현재 사이클을 통해 정점을 재방문하는 것은 언제나 손해임을 알 수 있고, 이 사이클은 음수 사이클임을 알 수 있다.

역으로, 음수 사이클이 있을 경우, 전체 정점 수 만큼의 시행 이상에서 무조건 갱신이 이루어짐을 보일 수 있다.

임의의 그래프 내에 존재하는 음수 사이클의 크기가 N이며, (전체 정점 수 - 1)회의 시행에서 시작점으로부터 음수 사이클 내 k번 정점까지의 거리를 Ak(1 <= k <= N), k번 정점에서 나오는 사이클 내의 간선이 가리키는 정점 번호를 Bk, 그 간선의 가중치를 Ck라고 하자.

만약, (전체 정점 수) 회의 시행에서 갱신이 이루어지지 않는다면, 1 <= k <= N인 모든 Ak에 대해 Ak <= ABk + Ck 이다. 이 모든 부등식을 다 더하면, 

또한, 1 <= k <= N인 모든 k에 대해 Ak의 합과 ABk의 합은 사이클 내 모든 정점의 거리 합과 같으므로 둘은 같다. 이를 이용해

와 같은 식이 유도된다. 이 때, 오른쪽 식에서 사이클 내 모든 간선의 가중치 합이 0 이상이어야 한다는 결론이 나오는데, 현 사이클은 음수 사이클이므로 전체 합이 0보다 작아야해서 모순이다. 즉, 음수 사이클이 있을 경우 (전체 정점 수)회의 시행에서 갱신이 무조건 이루어짐을 알 수 있고, 음수 사이클이 있음을 알 수 있다.