기초 - 벨만 포드 (최단 경로)

참고 문헌 1
참고 문헌 2

다익스트라 알고리즘이 '음의 가중치가 있어도 최단 경로를 구할 수 있다.' 라는 것이다. 하지만 이는 개선된 다익스트라 의 경우에는 음의 간선이 있어도 최단 경로를 구할 수 있다.

✨핵심 Point

처음에는 V-1번째 노드만큼만 반복한다. 마지막 V번째 노드는 사이클 존재 파악을 위해.

for(int i = 0; i < V - 1; i++) {
	for(int j = 0; j < E; j++){
    }
}

시간 복잡도: O(VE)

모든 노드에 대해서 모든 간선을 확인하면서 최단 경로를 구하는 알고리즘이다.

import java.util.*;
import java.io.*;

public class 벨만포드 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int d[] = new int[V+1];
		Arrays.fill(d, (int)1e9);
		
		int start = Integer.parseInt(br.readLine());
		d[start] = 0;
		
		ArrayList<Node> list = new ArrayList<>();
		for(int e = 0; e < E; e++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			list.add(new Node(a, b, cost));
		}
		
		for(int v = 0; v < V - 1; v++) {
			
			for(int e = 0; e < E; e++) {
				Node node = list.get(e);
				
				if(d[node.a] != (int)1e9 && d[node.b] > d[node.a] + node.cost) {
					d[node.b] = d[node.a] + node.cost;
				}
			}
		}
		
		// 음수 사이클 확인
		for(int e = 0; e < E; e++) {
			Node node = list.get(e);
			if(d[node.a] != (int)1e9 && d[node.b] > d[node.a] + node.cost) {
				System.out.println("음수 사이클 존재");
				return;
			}
		}
		
		for(int i = 1; i <= V; i++) {
			System.out.print(d[i] + " ");
		}
	}
	
	public static class Node{
		int a;
		int b;
		int cost;
		
		public Node(int a, int b, int cost) {
			this.a = a;
			this.b = b;
			this.cost = cost;
		}
	}

}