[Algorithm] Bellman-Ford(벨만포드)

Bellman-Ford(벨만포드) 알고리즘은 음수 가중치가 있는 그래프에서 특정 시작점 Vs에서 다른 나머지 정점(Vi, i=1, N)까지의 최단거리를 구할 수 있는 알고리즘입니다. 이 벨만포드 알고리즘을 그래프의 음수 사이클의 존재 여부도 알 수 있죠.

1. 음수 가중치가 있는 그래프에서 시작점에서 다른 정점까지의 최단거리를 구할 수 있다.

2. 음수 사이클 존재 여부를 알 수 있다.

Bellman-Ford 알고리즘의 동작과정은 각 정점들을 차례로 돌아 가면서 해당 정점의 간선들을 탐색합니다, 단 맨 처음은 시작점부터 탐색합니다. 그리고 그 간선의 가중치와 시작점에서 정점까지의 거리의 합이 해당 간선이 도달하고자 하는 정점의 기존 거리보다 작으면 업데이트합니다. 식으로 나타내면 다음과 같습니다.

d[T] <= d[S] + w(S,T)  ( T : 해당 간선이 도달하고자 하는 정점

            S : 해당 간선의 시작점

            d : 시작점에서 해당 정점의 거리

            w : 해당 간선의 가중치 )

이 해당식을 그래프의 정점의 수만큼 반복해서 계속해서 업데이트하여 최종적으로 정점의 수 V만큼 반복하면 시작점부터 모든 각 정점의 최단 거리가 구해집니다.

다음 그림들을 보면서 동작과정을 익히면 이해하기가 더 쉬울겁니다.

먼저, 시작점을 1로 설정하겠습니다. 그리고 각 정점들의 거리를 저장하는 1차원 배열 Dist를 정의합니다. 그리고 시작점의 거리는 0으로 놓고 나머지 정점은 아직 탐색되지 않았다는 의미로 무한대의 수로 설정합니다.

위에서 설명했듯이, 시작점부터 조사하기 시작합니다. 시작점의 각 간선들을 탐색하면서 업데이트되는 값이 타겟이 되는 정점의 Dist값보다 작으면 그 값을 업데이트 합니다. 여기서는 업데이트되는 값들이 INF보다 작으므로 2~5번 정점이 다 업데이트 되는 것을 볼 수 있습니다.

이제 2번 정점의 차례입니다. 2번 정점에 해당하는 간선을 탐색합니다. 위 그래프에서는 Dist[4]가 업데이트 된다는것을 알 수 있습니다.

그리고 나머지 3~5번도 같은 방법으로 탐색합니다.

최종적으로는 { 0,-4,5,-5,1 } 의 값이 나오게 됩니다. 

하지만 여기서 Bellman-Ford 알고리즘에서 중요한 기능이 하나 존재합니다. 바로 음수 사이클을 찾는 기능이죠! 어떻게 하면 해당 그래프의 음수사이클을 찾을 수 있을까요?

답은 V까지 반복하는 것이 아닌 한 번 더 해당 과정을 반복하는 겁니다. 음수사이클이 없을 경우에는 V+1 반복한다고 Dist 배열의 값들이 갱신되지 않습니다. 이유는 이론상 V정점들의 간선을 다 탐색했을 경우 각 정점들의 최단거리는 항상 구해지게 되어있기 때문이죠. 그러나 이 상태에서 한 번 더 반복했을 때 업데이트되는 경우는 음수사이클이 존재하여 Dist의 특정값에 - 가중치를 더해주는 경우겠죠. 그래서 V+1번째 탐색을 수행한 뒤 업데이트 되는 값의 존재여부를 발견하는 것은 음수사이클이 존재한다는 것을 알려주는 단서가 됩니다.

다음은 벨만코드 알고리즘을 구현한 코드입니다.

import java.util.Arrays;

public class BellmanFord {

    public static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int num = 5;
        int[][] adj = new int[][] {
                {0, -4, 5, 2, 3},
                {INF, 0, INF, -1, INF},
                {INF, INF, 0, -7, INF},
                {INF, INF, INF, 0, 6},
                {INF, INF, INF, -4, 0},
        };
        int src = 0;
        int dst = 1;

        solve(num, adj, src, dst);
    }

    public static void solve(int num, int[][] adj, int src, int dst) {
        int[] dists = new int[num];
        Arrays.fill(dists, INF);
        dists[src] = 0;

        for(int v=0; v < num; ++v) {
            for(int w=0; w < num; ++w) {
                if(adj[v][w] != INF)
                    dists[w] = Math.min(dists[w], dists[v] + adj[v][w]);
            }
        }

        for(int i=0; i< num; ++i)
            System.out.println(dists[i]);
    }
}

0
-4
5
-5
1