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

Bellman-Ford 알고리즘 이란?

• 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음

• 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능

• 시간복잡도 : O(NE) (N:노드의 수, E: 엣지의 수)

• 다음과 같은 그래프가 있다고 가정
• 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면
• 1 -> 2 = 1
• 1 -> 2 -> 3 = 2
• 1 -> 2 -> 3 -> 4 = 4 가 되고
• 노드 2는 이미 방문했기 때문에 4 -> 2 경로는 고려하지 않음
• 결과적으로 1 -> 2의 최단경로는 1이 됨
• 하지만 실제 1 -> 2의 최단경로는 -∞ 임
• 이를 해결하기 위해 벨만포드 알고리즘 탄생

Bellman-Ford 원리

• 엣지는 1->2, 4->2, 2->3, 3->4 순으로 입력되었다고 가정
• dist[1~4] = [0, ∞, ∞, ∞]로 초기화 후 시작
• 모든 엣지를 방문하며 각각의 엣지 방문으로 인해 발생하는 최소값으로 갱신
• 1번 loop
  1. 1 -> 2 엣지 방문 -> 이 엣지로 인해 dist[2] = dist[1] + 1 = 1로 갱신
  2. 4 -> 2 엣지 방문 -> dist[4] = ∞이므로 갱신 X
  3. 2 -> 3 엣지 방문 -> 이 엣지로 인해 dist[3] = dist[2] + 1 = 2
  4. 3->4 엣지 방문 -> 이 엣지로 인해 dist[4] = dist[3] + 2 = 4
• 루프 종료 시 dist = [0, 1, 2, 4]
• 2번 loop
  1. 1 -> 2 엣지 방문 -> dist[2] == dist[1] + 1 이므로 갱신 X
  2. 4 -> 2 엣지 방문 -> 이 엣지로 인해 dist[2] = dist[4] - 5 = -1
  3. 2->3 엣지 방문 -> 이 엣지로 인해 dist[3] = dist[2] + 1 = 0
  4. 3->4 엣지 방문 -> 이 엣지로 인해 dist[4] = dist[3] + 2 = 2
• 루프 종료 시 dist = [0, -1, 0, 2]
• 3번 loop도 마찬가지로 실행하면 루프 종료 시 dist = [0, -3, -2, 0]
• n - 1번의 loop 완료
  • 만약 음의 사이클이 없다면 이때의 dist 값이 노드 1에서 모든 노드들까지의 최소 거리
• 하지만 음의 사이클이 있다면 사이클을 돌때마다 dist값이 계속 갱신될 것임
• 따라서 n-1번의 loop 후 loop를 한번 더 돌리고, 갱신값이 하나라도 존재하면 음의 사이클이 존재함을 알 수 있음

구현

https://www.acmicpc.net/problem/11657

[11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

www.acmicpc.net](https://www.acmicpc.net/problem/11657)

• 이 문제를 벨만포드를 통해 해결하면서 구현해봄

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class p11657 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.valueOf(st.nextToken());
        int m = Integer.valueOf(st.nextToken());

        List<Edge> edges = new ArrayList<>();
        for(int i = 0 ; i < m ; i ++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.valueOf(st.nextToken());
            int end = Integer.valueOf(st.nextToken());
            int cost = Integer.valueOf(st.nextToken());

            edges.add( new Edge(start, end, cost) );
        }

        // 500 * 6000 * 10000이 int의 범위를 넘어감
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;

        // n - 1 번의 반복작업과 마지막 확인작업을 한 번에 돌림
        for(int i = 1 ; i <= n ; i ++) {
            for(Edge edge : edges) {
                // 한번도 들른적 없으면 패스
                // Long 최대값으로 초기화했기 때문에 이 작업 반드시 필요
                if(dist[edge.start] == Long.MAX_VALUE) continue;

                // 버스 도착점까지의 최소거리가 시작점 + 비용보다 크면 갱신
                if(dist[edge.end] > dist[edge.start] + edge.cost) {
                    dist[edge.end] = dist[edge.start] + edge.cost;

                    // n번째 작업에서 값이 변경되면 무한히 되돌아 갈 수 있다는 뜻
                    if(i == n) {
                        System.out.println(-1);
                        System.exit(0);
                    }
                }
            }
        }

        for(int i = 2 ; i <= n ; i ++) {
            if(dist[i] == Long.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(dist[i]);
            }
        }
    }

    static class Edge {
        int start, end, cost;

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