최단 경로 문제 (2) 벨만-포드 알고리즘을 중심으로

1. 들어가기

지난 글에서는 경로의 가중치가 음이 아닌 수로 부여된 경우에 사용되는 다익스트라 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 단일 출발지의 최단 경로 문제를 해결하는 벨만-포드(Bellman-Ford) 알고리즘에 대해 알아볼 것이다. 
 

2. 벨만-포드(Bellman-Ford)

벨만-포드 알고리즘은 출발 점으로부터 도달 가능한 음의 가중치의 순환(음수 사이클)이 존재하는 경우에는 최단경로를 구할 수 없고, 그러한 순환이 없다면 최단 경로들과 그 경로들의 가중치를 계산할 수 있다. 벨만-포드 알고리즘은 매번 모든 간선을 확인하므로 다익스트라 알고리즘보다는 느리다. 시간 복잡도는 O(VE); E는 경로(간선) 수, V는 꼭짓점(노드)의 수 이다. 하지만 간선이 음수로 존재하는 가중치에서의 최단 경로를 구할 수 있다는 점에서는 이점이 있는 것은 분명하다. 
 

[그림 1] 그래프

 

 그래프가 위 [그림 1]과 같이 존재한다고 하면,  1에서 시작하여 음수 사이클이 존재하지 않음을 확인하였고, 출발점인 1 에서 각 점까지 이동하는 최단 경로의 최소 비용은 다음과 같이 구할 수 있다.

(1) 1 - 2 : 없음

(2) 1 - 3 : 없음 

(3) 1 - 4 : 없음

(4) 1 - 5 : 5 

(5) 1 - 6 : 1 -> 5 -> 6 : 5 + 5 = 10 

(6) 1 - 7 : 1 -> 5 -> 6 -> 7 : 5 + 5 + (-3) = 3

3. 정리

벨만-포드 알고리즘을 적용하여 최단거리 문제를 풀면 다음과 같은 절차를 거친다.

1) 경로 내 음수 사이클이 존재하는 지를 확인(존재하지 않으면 시작 점에서 각 점마다 이동하는 최단 경로를 구할 수 있고, 그렇지 않으면 구할 수 없다.)
2) 출발점을 제외한 모든 점에 매우 큰 값인 INF를 할당함
3) 음수 사이클 체크를 위해 V+1(V:노드 수)번 반복한다.
4) 각 꼭짓점을 방문할 때 값을 할당하는 조건으로는 현재 가중치가 dist에 할당된 값보다 더 작다면 변수에 저장된 값을 현재 가중치로 갱신한다.
5) 모든 꼭짓점에 방문하여 최단 경로를 구한다. 
 

4. 구현

public class Main {
    static int N, M;
    static Edge[] edge;
    final static int INF = (int)1e9;
    
    static class Edge {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static void bellmanFord(int start) {
        int[] dist = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[start] = 0;

        boolean isMinusCycle = false;
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < M; j++) {
                Edge cur = edge[j];

                if (dist[cur.from] == Integer.MAX_VALUE) {
                    continue;
                }

                if (dist[cur.to] > dist[cur.from] + cur.weight) {
                    dist[cur.to] = dist[cur.from] + cur.weight;

                    if (i == v) {
                        isMinusCycle = true;
                    }
                }
            }
        }

        for (int i = 2; i < N + 1; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("INF ");
            } else {
                System.out.print(dist[i] + " "); // INF INF INF 5 10 3
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[][] data = new int[][]{{1, 5, 5}, {2, 3, -5}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 7, -7}};
        N = 7; //꼭짓점 수(node)
        M = 7; //간선 수(edge)
        int start = 1; // 출발 지점
        edge = new Edge[e];
        for (int i = 0; i < M; i++) {
            edge[i] = new Edge(data[i][0], data[i][1], data[i][2]);
        }
        
        bellmanFord(start);
    }
}

 

5. 벨만-포드 구현 시 유의할 점

- 음수 사이클이 존재하는 경우에는 벨만-포드 알고리즘으로 최단경로를 구할 수 없음을 유의한다.

- 벨만-포드 알고리즘은 음수 사이클 체크를 위해 V+1(V:노드 수)번의 계산을 반복한다.

- 각 점들의 최단경로의 거리는 INF로 초기화 한다.

- 시작 점으로부터 연결된 경로가 없는 경우 값이 INF로 할당되어 있다.

 
참고문헌 : Introduction to algorithms 3rd edition