[Algorithm] 벨만포드(BellmanFord) 알고리즘 JAVA

개념

가중 유향 그래프에서 최단 경로를 구하는 알고리즘입니다.

벨만 포드 알고리즘은 동작원리는 다익스트라(Dijkstra)와 유사합니다.

차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며

시간 복잡도가 O(VE) 입니다. (V: 정점 개수, E: 간선 개수)

다익스트라 알고리즘에서 우선순위 큐를 이용한 방식으로 시간구현하면 

시간 복잡도 O(VlogV)이므로 벨만 포드 알고리즘보다 실행속도가 빠릅니다.

 

다익스트라 알고리즘의 한계

정점 A → C로 갈 때, 두 가지 경로가 존재합니다.

① A → B → C

     cost: 7 + (-4)  = 3

② A → C

    cost: 5

결과적으로는 ① 경로가 최단 거리 비용이지만, 다익스트라 알고리즘에서는 정점 [A]와 연결된 정점 [B], [C] 중에서

7 > 5로 정점 [C]를 방문하여 최단 거리를 5로 확정합니다.

이는 다익스트라 알고리즘 구현 조건자체가 가중치는 양의 정수이기 때문입니다.

 

음수 가중치의 문제

음의 가중치 자체가 문제가 되는것은 아니지만 

아래와 같이 음의 값이 누적되는 사이클을 형성하면 문제가 됩니다.

A → D로 최단 거리 비용을 생각해보자.

cost: 2 → 3  → -6  → 3  → -6  → 3  → -6 ... 무한히 최소 거리가 작아집니다.

그렇기에 벨만 포드 알고리즘에서는 음의 값이 누적되는 사이클이 존재하는 경우, 의미 없는 값을 반환합니다.

 

★ 음수 사이클 판단

정점의 개수가 N인 경우, 최단 경로의 크기는 최대 |N| - 1 이 됩니다.

ex) 정점의 개수 = 4, 최단 경로는 최대 3의 크기를 가짐.

즉, 사이클을 순환하여 최단 경로 크기가 커지는 것을 제한.

 

 

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]);
    }
}