벨만-포드 알고리즘

하나의 시작점에서 하나의 도착점으로 가는 최단경로 문제를 해결하는 알고리즘이다.

음의 간선이 있는 경우에도 문제를 해결한다.
간선을 중심으로 문제를 해결한다.

 

import java.util.*;

public class Main{
	static int INF = 100000000;
	static ArrayList<Edge> list = new ArrayList<Edge>();
	static int[] d;	//최단 거리
	static int v;
	static int e;
	
	public static class Edge{
		int src;
		int dest;
		int weight;
		
		Edge(int src, int dest, int weight){
			this.src = src;
			this.dest = dest;
			this.weight = weight;
		}
	}
	
	public static boolean bellmanFord(int start) {
		boolean cycle = false;
		d[start] = 0;
		
		// 간선의 수 만큼 순회
		for(int i=0; i<=v; i++) {
			for(int j=0; j<e; j++) {
				int src = list.get(j).src;
				int dest = list.get(j).dest;
				int w = list.get(j).weight;
				
				// 시작점 최단경로가 무한대가 아닐 경우, 시작점 최단경로 + 목적지까지 가중치가 목적지 최단경로보다 작을때  
				if(d[src] != INF && d[src] + w < d[dest]) {
					d[dest] = d[src] + w;
					// v번째 순회에서 완화가 되면 음의 사이클 존재
					if(i == v)
						cycle = true;
				}
			}
		}
		
		// 음의 사이클 점검
		 return cycle;
		
	}
    public static void main(String[] args) throws Exception {
    	Scanner sc = new Scanner(System.in);
    	v = sc.nextInt();	// 정점의 개수
    	e = sc.nextInt();	// 간선의 개수
    	
    	d = new int[v+1];
    	
    	// 변수 초기화
    	Arrays.fill(d, INF);
    	
    	// 출발 노드, 도착 노드, 간선 가중치 입력
    	for(int i=0; i<e; i++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int w = sc.nextInt();
    		
    		list.add(new Edge(a, b, w));
    	}
    	
    	if(bellmanFord(1)) {
    		System.out.println(-1);
    	}else {
    		for(int i=2; i<=v; i++) {
    			if(d[i] == INF)
    				System.out.println(-1);
    			else{
    				System.out.println(d[i]);
    			}
        	}	
    	}

    	
    	sc.close();
    }
}