#알고리즘_벨만 포드(Bellman-Ford Algorithm) - Java

벨만 포드 알고리즘은, 다익스트라에서 할 수 없었던 음의 가중치도 계산 할 수 있도록 한 방식이다. 하지만 모든 정점에서 모든 간선을 다 봐야하기 때문에 시간 복잡도가 더 높다. 필요에 맞게 잘 사용하는 것이 중요.

 

벨만 포드 알고리즘에 대한 전제 조건

•  최단 경로는 사이클을 포함할 수 없다. 따라서 최대 |V|-1개의 간선만 사용할 수 있다. 
• 최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해준다. 이때 만약 음의 값을 가지고 있는 간선으로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.) 

이를 위해 백준에 있는 https://www.acmicpc.net/problem/11657 문제를 풀어 보는 것이 좋다. 꼭 풀어 보는 것을 추천한다.

 

처음 반복문을 돌려 최소 거리를 구하여 dist 배열을 갱신한다. 그 후에는 음의 값을 가지고 있는 간선으로 인해 싸이클이 형성되는 케이스를 체크해주어 해결하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class bellmanford {
	static int INF = Integer.MAX_VALUE;
	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.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Edge e[] = new Edge[M];
		
		int dist[] = new int[N+1];
		for(int i=1; i<=N; i++)
			dist[i] = INF;
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			e[i] = new Edge(u,v,val);
		}
		
		dist[1] = 0;
		
		for(int i=0; i<N-1; i++) {
			for(int j=0; j<M; j++) {
				if(dist[e[j].u] == INF) 
					continue;
				if(dist[e[j].v] > (dist[e[j].u] + e[j].val)) {
					dist[e[j].v] = dist[e[j].u] + e[j].val;
				}
			}
		}
		
		boolean check = false;
		
		for(int i=0; i<M; i++) {
			if(dist[e[i].u] == INF)
				continue;
			if(dist[e[i].v] > dist[e[i].u] + e[i].val) {
				check = true;
				break;
			}
		}
		
		if(check)
			System.out.println(-1);
		else {
			for(int i=2; i<=N; i++) {
				if(dist[i] == INF)
					System.out.println("-1");
				else
					System.out.println(dist[i]);
			}
		}
		
	}
	
	public static class Edge{
		int u;
		int v;
		int val;
		public Edge(int u,int v, int val) {
			this.u = u;
			this.v = v;
			this.val = val;
		}
	}
}