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

벨만-포드(Bellman-Ford)

• 음수 간선이 포함되어 있어도 최단 경로 구할 수 있음 (↔ 다익스트라는 음수 간선 포함 X)
  • 다만, 음수 사이클이 있으면 정상 동작하지 않음
• 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림
• 알고리즘 복잡도: O(VE)  ** V: 노드 // E: 간선 **

 

 

 

음수 간선이 포함된 가중그래프

• 노드1 -> 노드4 최단 경로
• 다익스트라 적용 시: 7 
• 최단 경로: 5

 

 

 

벨만-포드 알고리즘 Flow (1 / 2)

• 다음과 같이 노드와 간선 가중치 정보가 있을 때, 
  • A 노드에서 다른 노드들에 대한 최단 거리 구하기

• 1번 노드부터 돌면서 모든 간선들에 대한 정보를 갱신해 줌(더 작은 값이면 업데이트)

 

 

 

벨만-포드 알고리즘 Flow (2 / 2)

• 다음과 같이 노드와 간선 가중치 정보가 있을 때, 
  • A 노드에서 다른 노드들에 대한 최단 거리 구하기

• 반복문을 노드 수(V번)만큼 돌리는데, 여기서 한 번 더 돌렸을 때(V+1) distance 정보가 V번 돌렸을 때와는 다르게 값의 변화가 생긴다면 문제가 있음
• 그래서 값의 변화가 생긴다면 false 처리를 해줌

 

 

 

벨만-포드 알고리즘 코드 구현

// 알고리즘 - 최단 경로 알고리즘
// 벨만-포드

public class Main {
    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[] edge = new Edge[e];
        for (int i = 0; i < e; i++) {
            edge[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 = 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) { // 간선 수만큼 돌고 나서도 업데이트가 생긴다면 음수 사이클 true
                        isMinusCycle = true;
                    }
                }
            }
        }
        System.out.println("음수 사이클 발생: " + isMinusCycle);
        for (int i = 1; i < v + 1; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("INF ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
        System.out.println();
    }


    public static void main(String[] args) {
        // Test code
        // 각 배열에 든 정보: ex) 노드 1 -> 노드2의 간선 정보는 8, ...
        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);
    }
}

음수 사이클 발생: false
0 8 3 7 5 10 3
음수 사이클 발생: true
0 -2 -6 -2 5 3 -4