[최단경로] Bellman-Ford Algorithm

최단경로 알고리즘

package com.study.datastructrue.mst;

import java.util.ArrayList;
import java.util.Arrays;

class Pair<T, V> {

    T node;
    V cost;

    public Pair(T node, V cost) {
        this.node = node;
        this.cost = cost;
    }

}

public class BellmanFord {

    static long[] dist = new long[6];

    public static void main(String[] args) {
        // 집 1, 학교 2, 박물관 3, 영화관 4, 마트 5
        ArrayList<ArrayList<Pair<Integer, Integer>>> graph = input();
        for (int i = 1; i < graph.size(); i++) {
            dist = bellmanFord(graph, i);
            for (long dis: dist) {
                System.out.printf((dis == Integer.MAX_VALUE ? "INF" : dis) + " ");
            }
            System.out.println();
        }

        for (int i = 1; i < graph.size(); i++) {
            for (Pair<Integer, Integer> path : graph.get(i)) {
                if (dist[path.node] > dist[i] + path.cost) {
                    System.out.print("negative cycle exists ........");
                }
            }
        }
    }

    public static ArrayList<ArrayList<Pair<Integer, Integer>>> input() {
        ArrayList<ArrayList<Pair<Integer, Integer>>> graph = new ArrayList<>();
        for (int i = 0; i <= 5; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(1).add(new Pair<>(2, -1));
        graph.get(1).add(new Pair<>(5, 4));
        graph.get(2).add(new Pair<>(3, 2));
        graph.get(2).add(new Pair<>(4, 1));
        graph.get(2).add(new Pair<>(5, 3));
        graph.get(3).add(new Pair<>(4, -3)); // 음수 값에 따라 음수 사이클 판별 가능
        graph.get(4).add(new Pair<>(2, 2));
        graph.get(4).add(new Pair<>(5, 5));

        return graph;
    }

    public static long[] bellmanFord(
            ArrayList<ArrayList<Pair<Integer, Integer>>> graph,
            int start
    ) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        for (int node = 0; node < 5; node++) {
            for (int i = 1; i < graph.size(); i++) {
            	if (dist[i] == Integer.MAX_VALUE) continue;
                for (Pair<Integer, Integer> path : graph.get(i)) {
                    if (dist[path.node] > dist[i] + path.cost) {
                        dist[path.node] = dist[i] + path.cost;
                    }
                }
            }
        }

        return dist;
    }

}

 

벨만 포드 알고리즘은 한 점에서 다른 모든 점까지의 최단 경로를 찾는 것이다.

한 점에서 Dynamic Programming으로 Flooding 할 경우 현재까지의 최단 거리가 갱신된다.

이것을 n-1번 째 점까지 모두 반복을 하면 전체 최단 경로가 갱신이 된다는 것이다.

 

벨만 포드는 음수 가중치도 갖고 있으므로 n번째에서 한번 더 최단 경로가 갱신이 된다면, 음수 사이클을 갖고 있다는 것이된다. 음수 사이클만 계속 돌면서 -INF 까지 떨어짐.

 

또 음수 가중치가 있기 때문에 INF일 경우 continue를 해주어야한다. 안그럼 OverFlow 발생

 

전체적인 알고리즘 정리

1. 현재 노드에서 연결된 모든 간선의 가중치를 기준으로 최단거리를 갱신한다.

-> 현재 노드의 가중치 + 다음 노드의 가중치 < 다음 노드의 가중치라면 현재 노드에서 다음 노드로 이동하는 길이 최단 경로이므로 업데이트 해준다.

2. 위 과정을 노드의 갯수 - 1번까지 반복하면 최단 경로가 갱신된다.

3. 2번까지 과정을 마치고 한번 더 최단 경로가 갱신된다면 음수 사이클이 존재하는 것이다.

 

 

참고

https://10000cow.tistory.com/entry/%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%9C-%EC%82%B4%EB%8F%84-%EC%9D%B4%ED%95%B4%ED%95%98%EB%8A%94-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Bellman-Ford-Algorithm

[벨만-포드 알고리즘] 한 살도 이해하는 벨만-포드 알고리즘(Bellman-Ford Algorithm)