[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)

최단경로 알고리즘

최단 경로 문제는 다음과 같이 분류할 수 있다.

1.  모든 간선이 양수인 경우
2.  음수 간선이 있는 경우
   1. 음수 간선 순환은 없는 경우
   2. 음수 간선 순환이 있는 경우 

 

위의 분류를 3가지 알고리즘을 통해 구할 수 있다.

1. 벨만포드 알고리즘 (Bellman-Ford Algorithm) → 2-1),2-2) 음수 간선이 있는 경우
2. 다익스트라 알고리즘(Dijkstra Algorithm) → 1)모든 간선 양수
3. 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) → 1)모든 간선 양수

 

벨만포드 알고리즘

벨만포드 최단 경로 알고리즘은 음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 

 

동작 과정

1. 출발 노드를 설정한다. (to, from, cost)
2. 최단 거리 테이블을 초기화한다. (dist[] : 최단 거리 갱신할 때마다 저장)
3. 다음의 과정을 N-1번 반복한다. (for 반복문)
   1. 전체 간선 E개를 하나씩 확인한다.
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
4. N번째 조회 : 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다.
   1. 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재 (왜냐하면 음수 간선 순환은 돌면 돌수록 값이 작아지기 때문이다.)

// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우 
if(dist[next] > (dist[cur] + cost)) {
	dist[next] = dist[cur] + cost;
							
	// n번째 라운드에서 값이 갱신된다면 음수 순환 존재 
	if (i == n-1) {
	return true;
	}
}

 

벨만 포드 vs 다익스트라

다익스트라

•  매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 
•  음수 간선이 없다면 최적의 해를 찾을 수 있다.

 

벨만 포드

• 매번 모든 간선을 전부 확인한다.
  • 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.
• 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있다.

 

벨만포드 알고리즘에서는 다익스트라에서 할 수 없었던 음의 가중치도 계산 할 수 있도록 한 방식이지만 다익스트라보다 시간 복잡도가 높기에(더 느리기에) 어떤 상황에서 이용해야 할 지 잘 생각하여 써야한다.

• 다익스트라 기본 시간 복잡도는 O(|E||log|V|), 벨만 포드의 기본 시간 복잡도는 O(VE)이다.

 

다익스트라 코드

public class DijkstraExample {

	static List<Node>[] list;
	static int[] dp;
	static boolean[] check; 
	
	public static void main(String[] args) {
		int[][] a = {{1,2,2}, {1,4,1}, {1,3,5}, {2,3,3}, {2,4,2},
				{3,4,3}, {3,5,1}, {4,5,1}, {5,6,2}, {3,6,5}};
		int n =6;
		solution(n,a);
	}
	
    // Dijkstra 배열 초기화
	static void solution(int n , int maps[][]) {
		check = new boolean[n+1];
		dp = new int[n+1];
		
		list = new ArrayList[n+1];
		
		for(int i=1; i<n+1; i++	) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<maps.length; i++) {
			int a = maps[i][0];
			int b = maps[i][1];
			int c = maps[i][2];
			
			list[a].add(new Node(b,c));
			list[b].add(new Node(a,c));
		}
		
		dijkstra(1);
		
		for(int num : dp) {
			System.out.print(num +" ");
		}
	}
	
	
    // Dijktstra 알고리즘 (우선순위 큐(Heap)을 이용한 알고리즘)
	static void dijkstra(int start) {
		Queue<Node> q = new PriorityQueue<>();
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		q.add(new Node(start,0));
		
		dp[start] = 0;
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int to = node.to;
			
			if(check[to]) continue;
			else check[to] = true;
			
			for(Node nxt : list[to]) {
				if(dp[nxt.to]  >= dp[to] + nxt.weight) {
					dp[nxt.to] = dp[to] + nxt.weight;
					q.add(new Node(nxt.to, dp[nxt.to]));
				}
			}
		}
	}
}

class Node implements Comparable<Node>{
	int to;
	int weight;
	
	Node(int to, int weight){
		this.to = to;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.weight, o.weight);
	}
}

 

벨만포드 코드

// BOJ #11657 graph 타임머신 (벨만포드)
import java.io.*;
import java.util.StringTokenizer;

class Bus{
	int u;
	int v;
	int val;
	public Bus(int u,int v, int val) {
		this.u = u;
		this.v = v;
		this.val = val;
	}
}

public class TimeMachine {
	static int n,m;
	static Bus[] e;
	static long[] dist;
	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());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		e = new Bus[m];
		
		
		// 1. 출발 노드 설정
		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 Bus(u,v,val);
		}
		
		// 2. 최단거리 테이블 초기화
		dist = new long[n+1];
		for(int i=1; i<n+1; i++) {
			dist[i] = INF;
		}
		
		// 벨만포드 알고리즘 실행 (true: 음수 순환 존재, false: 음수 순환 존재x)
		if(bellmanford(1)) { // 음수 순환 존재하면 -1 출력 
			System.out.println(-1);
		}
		else {
			// 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단거리 출력 
			for(int i=2; i<n+1; i++) {
				if(dist[i] == INF) {// 도달할 수 없으면 -1 
					System.out.println("-1");
				}
				else { // 최단 거리 출력 
					System.out.println(dist[i]);
				}
			}
		}
		
	}
	static boolean bellmanford(int start){
		
		dist[start] = 0;
		
		// n번 반복 (음수 간선 순환 체크안하려면 n-1번 반복)
		for(int i=0; i<n; i++) {
			// 매 반복마다 모든 간선을 확인 
			for(int j=0; j<m; j++) {
				int cur = e[j].u;
				int next = e[j].v;
				int cost = e[j].val;
						
				if(dist[e[j].u] == INF) 
					continue;
				// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우 
				if(dist[next] > (dist[cur] + cost)) {
					dist[next] = dist[cur] + cost;
							
					// n번째 라운드에서 값이 갱신된다면 음수 순환 존재 
					if (i == n-1) {
						return true;
					}
				}
			}
		}
		return false;
	}
	
	
}