벨만포드 알고리즘 : 백준 11657 ( 타임머신)

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

11657번: 타임머신

NlogN 인 다잌스트라 알고리즘보다 N^3 인 시간복잡도를 가지지만 음수의 가중치를 가지는 그래프에 대해서도 최단경로를 구할 수 있는 벨만포드 알고리즘이다.

구하는 방법은 모든 간선들을 순환하면서 현재의 간선이 INF 값이 아니라면 연결된 간선들을 최신화를 해주는 방법이다.

이러한 최신화를 N-1번 반복하면 그게 벨만 포드 알고리즘이다 N-1번하면 그이상은 최신화 할필요가 없다고 생각한다.

어떤 맵상에 1~N에 가선들이 있는데 처음에 1노드만 digit = 0 이된다 따라서 1과 연결되 있는 노드들만 최신하된다 첫번째 사이클에 두번째 사이클은 1->n 최신화 되잇는 애들만 최신화가 된다. 이런경우 만약 
1->2->3->4 로 연결된 단일 경로에대해서 N-1번을 반복학게되면 최신화 된다는 것이다.

하지만 N번째에서 최신화됫다는것은 음수인 사이클이 존재한다고 판단한다.
이러한 경우에는 Cycle을 true로 반환하고 음수 가중치의 사이클이 존재한다고 생각한다.

package day0308;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class B11657 {
    static int N, M;
    static final int INF = Integer.MAX_VALUE;
 
    static class VER {
        int u;
        int w;
 
        public VER(int u, int w) {
            super();
            this.u = u;
            this.w = w;
        }
    }
 
    static ArrayList<VER> ver[];
    static int digit[];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        ver = new ArrayList[N + 1];
        for (int n = 1; n <= N; n++) {
            ver[n] = new ArrayList<VER>();
        }
 
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            ver[u].add(new VER(v, w));
        }
 
        digit = new int[N + 1];
        Arrays.fill(digit, INF);
        boolean Cycle = false;
        
        digit[1] = 0;
        for(int i =1;i<=N;i++) {
            for(int j=1;j<=N;j++) {
                if(digit[j]==INF)continue;
                for(VER p : ver[j]) {
                    if(digit[p.u] > digit[j] + p.w) {
                        digit[p.u] = digit[j] + p.w;
                        
                        //V-1반복을 다돌앗으면 최신화 될수 있는것은 다되었다고 생각한다.
                        if(i==N) {
                            //N번재 인데도 갱신한다?? 그러면 Cycle이 있는것
                            //벨만포드는 N-1번 반복하면 갱신 다되는 알고리즘 그이상 갱신하면 Cyclye
                            Cycle = true;
                        }
                    }
                }
            }
        }
        
        
        
        
        if (!Cycle) {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= N; i++) {
                digit[i] = digit[i]!=INF ? digit[i] : -1;
                sb.append(digit[i] + "\n");
            }
            System.out.println(sb.toString());
        } else {
            System.out.println(-1);
        }
    }
 
}