[Java] 벨만-포드 알고리즘 (Bellman-Ford) [미완]

그래프 최단거리를 구하는 알고리즘

1. 다익스트라

2. 벨만 포드

3. 플로이드 와샬

 

 

벨만 포드 알고리즘은 다익스트라 알고리즘처럼 그래프에서 한 노드에서 다른 모든 노드까지 가는 최소비용을 구할 수 있는 알고리즘이다.

 

다익스트라와의 차이점은 음수 가중치가 존재하는 경우에도 적용 할 수 있다.

 

벨만 포드 알고리즘의 시간복잡도는 O(VE)이다. (V: 정점, E: 간선)

다익스트라에서 시간복잡도는 O(VlogE)이므로 다익스트라가 더 빠르다.

 

 

다익스트라 알고리즘의 한계

다익스트라 알고리즘은 그리디알고리즘 + 다이나믹 프로그래밍이 합쳐진 알고리즘이다.

 

그리디 알고리즘 한계점 때문에 다익트스라 알고리즘은 음수 가중치를 가질 수 없다.

위 그림에서 1번 -> 3번 이동할때 최소비용을 구하게하면

다익스트라는 1->3 경로인 10이 구해질것이다. (그리디 알고리즘이니까 매 선택시 가장 낮은 비용을 선택한다)

하지만 벨만 포드를 사용하면 "매번 모든" 간선을 "전부" 확인하므로 1->2->3의 경로를 선택하여 최소비용을 구할 수 있게된다.

 

---

벨만 포드 알고리즘 수행과정

다익스트라처럼 초기화하는 과정을 가진다.

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        v = Integer.parseInt(input[0]);
        e = Integer.parseInt(input[1]);
        //초기화 작업들
        time = new long[v + 1];
        Arrays.fill(time, maxRange + 1);
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            int[] edgeInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            graph.get(edgeInfo[0]).add(new Edge(edgeInfo[1], edgeInfo[2])); //단방향
//            graph.get(edgeInfo[1]).add(new Edge(edgeInfo[0], edgeInfo[2]));  양방향일 경우 추가
        }
    }

 

벨만포드 동작

static boolean bellmanFord() throws IOException {
    time[1] = 0;

    for (int i = 1; i < v; i++) { //(정점의 개수 -1)번 만큼 최소비용 초기화 작업 반복한다.
        for (int j = 1; j <= v; j++) { //초기화 작업 ==> 모든 간선을 살피며 최소비용값 업데이트를 한다
            for (Edge edge : graph.get(
                j)) { //해당 노드와 연결된 모든 간선에 대해 체크한다. (모든 간선을 살피기 위해 각 노드에 연결된 모든 간선을 가져온다)
                if (time[j] == maxRange
                    + 1) { // 지금 노드로 가는 길에 대한 비용이 아직 업데이트 되지않았다면, 그 길 + 간선 을 이용한 비용업데이트를 할 수 없으니 넘어간다.
                    break; // 다음 노드로
                }
                if (time[edge.index] > time[j]
                    + edge.cost) { //원래 저장된 간선의 도착지(인접노드)를 가는 최소비용이  지금 노드가는 비용 + 간선의비용 보다 크다면 갱신시켜준다.
                    time[edge.index] = time[j] + edge.cost;
                }
            }
        }
    }

    //위에서 (정점의개수-1)번 최소비용값을 초기화해줘서 초기화가 완료됬다. 1번 더했는데 값이 업데이트가 되는경우가 있다면 음수사이클이 존재하므로 실패를 의미한다.
    for (int j = 1; j <= v; j++) {
        for (Edge edge : graph.get(j)) {
            if (time[j] == maxRange + 1) { //maxRange+1은 초기값을 의미
                break;
            }
            if (time[edge.index] > time[j] + edge.cost) {
                return false; //수정될게 있다 -> 음수사이클이 존재해서 , 초기화작업을 할때마다 값이 더 작아질것이다 ( 비용이 무한히 작아지는 음수사이클이 존재)
            }
        }
    }

    return true;// 음수사이클이 없다면 성공


}

 

 

 

벨만포드 코드 + 예제(11657:타임머신) 풀이

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int v, e;

    static List<List<Edge>> graph;
    static long[] time; //주의 : 벨만포드는 전체 과정을 정점의 수만큼 돌린다. 예상가능한 비용의 최대값은 간선의수 * 가중치의 최대값이다.
    /*
    만약 음수사이클이 존재한다고하자, 그 음수사이클로인해 어떤 정점까지 가는 비용이 계속 마이너스로 감소되고있을때, 그 음수사이클의 비용이 최대간선의수 * 가중치의 최소값일경우
    예상가능한 최소값을 정점의 갯수만큼 반복해서 time이라는 비용저장변수에 저장되는것이다.
    즉 최소비용을 저장하는 변수에 저장되는 최악의 경우는 음수사이클이 존재할때 ->  -(정점의개수 * 간선의최대갯수 * 가중치최대값) ~ +(정점의개수 * 간선의최대갯수 * 가중치최대값)의 범위값이 들어가야한다.
    간단하게 (v * maxRange)값을 포함할 수 있는 자료형을 사용해야하며 여기서는 500 * 6천만 이므로 long 타입으로 해줘야한다.
     */
    static final int maxRange = 60000000;

    /*
     */

    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        v = Integer.parseInt(input[0]);
        e = Integer.parseInt(input[1]);
        //초기화 작업들
        time = new long[v + 1];
        Arrays.fill(time, maxRange + 1);
        graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            int[] edgeInfo = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
            graph.get(edgeInfo[0]).add(new Edge(edgeInfo[1], edgeInfo[2])); //단방향
//            graph.get(edgeInfo[1]).add(new Edge(edgeInfo[0], edgeInfo[2]));  양방향일 경우 추가
        }
    }

    static void solve() throws IOException {
        if (bellmanFord()) {
            for (int i = 2; i <= v; i++) {
                if (time[i] == maxRange + 1) {
                    bw.write(-1 + "\n");
                } else {
                    bw.write(time[i] + "\n");
                }
            }
        } else {
            bw.write(-1 + "");
        }
    }

    static boolean bellmanFord() throws IOException {
        time[1] = 0;

        for (int i = 1; i < v; i++) { //(정점의 개수 -1)번 만큼 최소비용 초기화 작업 반복한다.
            for (int j = 1; j <= v; j++) { //초기화 작업 ==> 모든 간선을 살피며 최소비용값 업데이트를 한다
                for (Edge edge : graph.get(
                    j)) { //해당 노드와 연결된 모든 간선에 대해 체크한다. (모든 간선을 살피기 위해 각 노드에 연결된 모든 간선을 가져온다)
                    if (time[j] == maxRange
                        + 1) { // 지금 노드로 가는 길에 대한 비용이 아직 업데이트 되지않았다면, 그 길 + 간선 을 이용한 비용업데이트를 할 수 없으니 넘어간다.
                        break; // 다음 노드로
                    }
                    if (time[edge.index] > time[j]
                        + edge.cost) { //원래 저장된 간선의 도착지(인접노드)를 가는 최소비용이  지금 노드가는 비용 + 간선의비용 보다 크다면 갱신시켜준다.
                        time[edge.index] = time[j] + edge.cost;
                    }
                }
            }
        }

        //위에서 (정점의개수-1)번 최소비용값을 초기화해줘서 초기화가 완료됬다. 1번 더했는데 값이 업데이트가 되는경우가 있다면 음수사이클이 존재하므로 실패를 의미한다.
        for (int j = 1; j <= v; j++) {
            for (Edge edge : graph.get(j)) {
                if (time[j] == maxRange + 1) { //maxRange+1은 초기값을 의미
                    break;
                }
                if (time[edge.index] > time[j] + edge.cost) {
                    return false; //수정될게 있다 -> 음수사이클이 존재해서 , 초기화작업을 할때마다 값이 더 작아질것이다 ( 비용이 무한히 작아지는 음수사이클이 존재)
                }
            }
        }

        return true;// 음수사이클이 없다면 성공


    }

    static class Edge {  //다익스트라에서는 이름이 Node라고하고 내용은 같았다 , 인접노드로 가는 간선이므로 정확히는 Edge라는 표현이 맞는거같다.

        int index;
        int cost;

        public Edge(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }
    }


}

11657번: 타임머신

long범위

long a = Long.MAX_VALUE;
bw.write(a+"");

 

 

 

 

 

 

벨만-포드 알고리즘 · ratsgo's blog

 

 

[Algorithm] 벨만포드 알고리즘(Bellman-Ford Algorithm)

 

 

[알고리즘/Java] 벨만-포드(Bellman-Ford) 알고리즘

 

 

[BOJ] 백준 11657번 : 타임머신 (JAVA)

[BOJ] 백준 1865번 : 웜홀 (JAVA)