벨만 포드 알고리즘

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 다음의 과정을 (V(=정점) - 1)번 반복한다.
   1. 모든 간선 E개를 하나씩 확인한다.
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

시간 복잡도: 벨만-포드 알고리즘의 시간 복잡도는 O(V * E) 입니다. 여기서 V는 정점의 수, E는 간선의 수입니다

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

import java.util.*;

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 class Main {
    static final int INF = 987654321;
    static int N, M;
    static List<Edge> edges = new ArrayList<>();
    static long[] distance;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 도시의 개수
        M = sc.nextInt(); // 버스 노선의 개수
        distance = new long[N + 1];

        // 거리 배열 초기화
        Arrays.fill(distance, INF);
        distance[1] = 0; // 시작 도시는 0으로 초기화

        // 버스 노선 정보 입력
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt(); // 출발 도시
            int B = sc.nextInt(); // 도착 도시
            int C = sc.nextInt(); // 소요 시간
            edges.add(new Edge(A, B, C));
        }

        // 벨만 포드 알고리즘 실행
        boolean isCycle = false;
        for (int i = 1; i <= N; i++) {
            for (Edge edge : edges) {
                int from = edge.from;
                int to = edge.to;
                int weight = edge.weight;
                if (distance[from] != INF && distance[to] > distance[from] + weight) {
                    distance[to] = distance[from] + weight;
                    if (i == N) {
                        isCycle = true; // 음수 가중치 사이클이 발생하면 표시
                    }
                }
            }
        }

        // 출력
        if (isCycle) {
            System.out.println("-1");
        } else {
            for (int i = 2; i <= N; i++) {
                if (distance[i] == INF) {
                    System.out.println("-1");
                } else {
                    System.out.println(distance[i]);
                }
            }
        }
    }
}