[알고리즘] Bellman-Ford 알고리즘이란?

오늘은 최단 경로를 찾는 알고리즘 중 Dijkstra 알고리즘의 단점을 보완한 Bellman-Ford 알고리즘에 대해서 알아보겠습니다.

 

---

Dijkstra 알고리즘의 단점

이전 포스팅에서 말한 Dijkstra 알고리즘의 단점을 찾아보셨나요?? 여기서 간단하게 다뤄봅시다.

 

0번 정점을 우선 방문했습니다. 그리고 1번 정점과 2번 정점에 대해서 값을 갱신해줍니다.

이제 1번 노드를 선택할 것입니다. 가중치도 같이 갱신해줍시다.

 

이제 2번 정점에 갈 차례입니다!! 2번 정점에서 값을 갱신해봅시다.

 

이렇게 모든 노드를 방문하고 알고리즘을 종료합니다.

 

 

이제 0번 노드로부터 각 노드의 최단거리를 알았습니다.

0에서 2로 가는 최단거리는 1

0에서 1로 가는 최단거리는 -2

 

뭔가 이상하지 않나요??

사실 0에서 1로 가는 최단거리는 0 -> 2 -> 1이여서 2가 되어야합니다. 하지만 다익스트라는 -2라는 잘못된 결과를 도출하고 있죠.

 

조금 자세히 살펴보면 알 수 있는데 사실 -2라는 값은 [0 -> 1-> 2 -> 1]의 결과에서 나온 것입니다.

 

즉, 다익스트라 알고리즘은 음수의 가중치가 존재할 때 사용할 수 없습니다.

(사실 현실 세계에서는 음수의 가중치가 존재하기 어렵습니다. 거리 or 시간 등.. 따라서 다익스트라를 실생활에서는 많이 사용하지만 예외적인 문제나 이를 해결하기 위한 알고리즘은 존재해야하므로, Bellman-Ford를 제시한 것입니다.)

 

 

Bellman-Ford란?

다익스트라 알고리즘의 문제점을 해결하기 위해 Bellman-Ford 알고리즘이 생겨나게 됩니다. 이는 다익스트라의 음수가중치 문제를 해결할 수 있습니다만..  입력 그래프에서 사이클 내의 가중치의 총합이 음수인 사이클이 없어야합니다.

 

만약 이 조건을 성립하지 않는다면, Bellman-Ford에서는 알고리즘을 계속 반복하며 경로의 길이를 계속해서 줄이는 작업을 진행할 것입니다.

 

 

 

Bellman-Ford의 핵심 아이디어는 출발점에서 각 정점까지의 최단 경로 상에 있는 간선의 수는 최대 n-1개이다.

 

따라서 저희는 각 정점에 대해서 간선 완화 작업을 n-1번하면 가중치의 갱신이 없음을 알 수 있습니다.

 

음수 사이클이 없다면, 간선완화는 사이클을 돌지 않습니다. 음수가 아니라면 계속 돌 이유가 없기 때문이죠.

 

따라서, 각 정점까지 가는 경로에 사이클이 없고, 이는 두 정점 사이에는 최악의 경우 모든 노드를 방문하는 경우이기 때문에, 최단 경로 상에 있는 간선의 수는 최대 n-1개입니다.

 

 

자 그럼 Bellman-Ford의 과정에 대해서 이해해보겠습니다.

 

가장 처음 시작할 노드의 값을 초기화해야합니다. weight는 0으로, 이전 노드의 값은 자기자신을 가리키게 합니다.

 

Bellman-Ford는 총 n-1번의 반복을 진행합니다. 각 반복마다 주어진 모든 값들을 갱신해줍니다. 갱신할 수 있다면 말이죠.

 

자, k=0부터 시작해봅시다. 위의 그림의 상태에서 값을 초기화해봅시다.

위와 같습니다. 나머지 다른 정점에서의 값은 갱신될 수 없습니다.

 

이제 k=1에서 갱신되는 값들을 확인해봅시다.

이런 식으로 진행되겠군요. k=2까지만 확인해봅시다.

이렇게 진행되는 것을 볼 수 있습니다.

 

 

이 작업을 n-1번 반복해야하므로 k=n-2=6까지 반복하게 되면 아래와 같은 결과를 얻습니다.

 

이제 우리는 정점 0으로부터 모든 정점까지의 최단 경롤를 구한 셈입니다. 물론 가중치가 음수인데도 말이죠.

 

 

 

이제 Bellman-Ford 알고리즘을 구현해봅시다.

 

 

Bellman-Ford의 알고리즘 구현

Edge 클래스는 이전 Dijkstra 알고리즘과 동일한 내용입니다. Dijkstra의 글을 확인하시기 바랍니다.

 

public class BellmanFord {
    public static final int INF = Integer.MAX_VALUE;
    private int[] D;
    private int[] previous;
    private int N;

    public BellmanFord(int numOfVertices){
        N = numOfVertices;
        D = new int[N];
        previous = new int[N];
    }

    public void shortestPath(int s, int adjMatrix[][]){
        for(int i=0; i<N; i++) D[i] = INF;

        D[s] = 0;
        previous[s] = 0;

        for(int k=0; k<N-1; k++){
        	// 모든 i와 j에 대해서
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(adjMatrix[i][j] != INF){ // 만약 연결되어있다면
                        if(D[j] > D[i] + adjMatrix[i][j]){
                        	// 만약 거리 갱신이 필요하다면
                            D[j] = D[i] + adjMatrix[i][j];
                            previous[j] = i;
                        }
                    }
                }
            }
        }
    }

    public void printPaths(int s){
        System.out.println("정점 "+s+"으로부터 최단 거리");

        for(int i=0; i<D.length; i++){
            if(i==s) continue;
            if(D[i] == Integer.MAX_VALUE){
                System.out.println(s+"과 "+i+" 사이에 경로 없음");
            }else{
                System.out.println("["+s+", "+i+"] = "+D[i]);
            }
        }
        System.out.println();
        System.out.println("정점 "+s+"으로부터의 최단 경로");
        for(int i=0; i<D.length; i++){
            if(i==s) continue;
            int back = i;
            System.out.print(back);
            while(back!=0){
                System.out.print("<-"+previous[back]);
                back = previous[back];
            }
            System.out.println();
        }
    }
}

 

간단한 주석으로 설명을 대체합니다.

 

 

Bellman-Ford 알고리즘의 수행시간

총 정점의 개수 n-1을 반복한다 O(n). 한번의 반복마다 모든 간선을 확인한다. O(m)이므로 O(nm)이다. 하지만 m < n^2이므로 Bellman-Ford는 O(n^3)의 시간복잡도가 나온다.

 

---

오늘은 Bellman-Ford에 대해서 알아봤습니다. 다음은 마지막으로 최단 경로 알고리즘인 Floayd-Warshall에 대해서 포스팅해보겠습니다. 감사합니다.