최단 경로 알고리즘 - 벨만-포드 (Bellman-Ford)

 벨만-포드 알고리즘이란?

• 하나의 정점에서 모든 정점으로 가는 최단 거리를 구할 수 있습니다.
• 다익스트라와 달리 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있습니다.
  • 다만, 음수 사이클이 있을 땐 사용 X
• 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느립니다.
• 알고리즘 복잡도 : O(VE)

 

벨만-포드 알고리즘 흐름

1. 정점의 숫자만큼 모든 간선을 체크한다. (정점 * 간선 , VE)

• distance가 무한대인 경우, 뽑힌 변의 가중치를 더해봤자 무한대이기 때문에 continue 처리한다.
• 1의 노드에서 5의 노드로 가는 경우, 1의 최단 경로 값이 0이기 때문에 5번 노드로 가는 가중치 5를 더해준다.
• 위의 작업을 정점 별로 모든 간선을 체크해나가다보면 distance가 갱신된다.

 

출처 : zero-base

2. 음수 사이클이 있는지 체크한다.

• 음수사이클이란 사이클이 생기는 부분에 음수간선이 더 큰 경우, 계속해서 distance가 줄어드는 경우가 생기는 경우입니다.

• 위의 이미지에서 1에서 시작해서 2 ->6으로 간다고 할 때,
  • 8 (2번 노드가 가지고 있는 최단경로) + 4(2번에서 6번으로 갈 때의 가중치) = 12 (6번 최단경로)
  • 12 (6번노드가 가지고 있는 최단경로) - 5(6번에서 2번으로 갈 때의 가중치) = 7(기존의 8보다 작기 때문에 7로 교체)
  • 7 (2번노드가 가지고 있는 최단경로) + 4(2->6) = 11 (기존 12 보다 작기 때문에 6번 가중치는 11로 변경)
  • 위의 경우가 계속 반복된다.
• 정점 수만큼 간선을 다 확인했는데도 변경이 생긴다면 음수 사이클이 있는 것 입니다.
  • V만큼 다 돈 후의 최단경로 내역과 V+1번만큼 돌렸을 때의 최단 경로 내역이 다르면 음수사이클이 존재.
  • 음수사이클이 존재할 경우 false 처리(알고리즘을 정지)

 

벨만-포드 구현 및 예제

/**
 * 벨만-포드 알고리즘
 * - 음수 간선이 있는 경우에 사용하는 최단경로 알고리즘
 * - 다익스트라가 더 빠르기 때문에 음수 간선이 없는 경우에는 다익스트라 사용하는게 좋음
 * - 시간 복잡도 : O(EV)
 *
 * 알고리즘 흐름
 * 1. 노드 수 * 간선 수 만큼 반복문을 돌면서 모든 간선을 체크하고 최단 경로를 갱신한다.
 * 1-1. 만약, 출발지의 최단 경로가 INF라면 continue로 넘어간다.
 * 1-2. 출발지의 최단 경로가 INF가 아니라면, 출발지 최단 경로 값 + 간선의 가중치를 도착지의 최단경로 값과 비교해 작은 값으로 교체한다.
 * 1-3. 위를 노드 수 만큼 반복하면서 매번 간선을 체크한다.
 * 2. 노드 수보다 1 만큼 더 돌면서 음수 사이클이 있는지 체크
 * 2-1. 노드 수만큼 돌았을 때의 최단경로 내역과 노드 +1 만큼 돌았을 때의 최단 경로 내역을 비교해서 다르면 음수 사이클이 존재
 * 2-2. 알고리즘 종료.
 **/

public class BellmanFord {

    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 v, int e, int[][] data, int start) {
        Edge[] edges = new Edge[e];
        for (int i = 0; i < e; i++) {
            edges[i] = new Edge(data[i][0], data[i][1], data[i][2]);
        }

        int[] dist = new int[v + 1];

        for (int i = 1; i < v + 1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        dist[start] = 0;

        // 음수 사이클 확인
        boolean isMinusCycle = false;

        // 음수 사이클 확인하기 위해 v+1만큼 반복
        for (int i = 0; i < v+1; i++) {
            for (int j = 0; j < e; j++) {
                Edge cur = edges[j];

                // 출발지 최단 경로가 무한대인 경우 continue
                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;

                    // V+1 만큼 반복을 했는데도 변경사항이 발생한 경우
                    if (i == v) {
                        isMinusCycle = true;
                    }
                }

            }
        }


        System.out.println("음수 사이클 발생 : " +isMinusCycle);
        for (int i = 1; i < v + 1; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
        System.out.println();


    }

    public static void main(String[] args) {
        // Test code
        int[][] data = {{1, 2, 8}, {1, 3, 6}, {1, 5, 5}, {2, 3, -5}, {2, 4, 1}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 2, 0}, {6, 7, -7}};
        bellmanFord(7, 11, data, 1);

        data = new int[][]{{1, 2, 8}, {1, 3, 6}, {1, 5, 5}, {2, 3, -5}, {2, 4, 1}, {2, 6, 4}, {3, 4, 4}, {4, 7, 3}, {5, 6, 5}, {6, 2, -5}, {6, 7, -7}};
        bellmanFord(7, 11, data, 1);
    }
}