개요

https://velog.io/@alwaysryu13/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
여기에서 언급했던, 벨만포드 알고리즘

한 곳에서, 다른 경로 까지의 최단거리를 구할 때 사용하는 알고리즘이다.
다익스트라와 다른 점은 음의 가중치까지 허용한다는 점이다.

알고리즘

다익스트라는 방문하지 않은 노드중 최단 거리가 가장 짧은 노드를 선택한다.
벨만-포드는 음수 까지 적용하기 때문에, 모든 경로를 살펴 보아야 한다. 돌아가더라도 음수가 있기 때문에 계산하기 전까지 모르는 것이다!
당연히 다익스트라보다는 오래 걸린다.

알고리즘

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 모두 무한대로 초기화 한다.

3. (정점의 개수-1)만큼 반복한다.
   가. 모든 간선 E개를 하나씩 확인한다.
   나. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

   계산방법 :

   1. 간선의 출발점의 거리가 INF 면 넘긴다.
   2. INF가 아닐경우 -> 간선의 가중치 + 간선의 출발점의 최단거리 // 현재 도착점의 최단거리를 비교하여 업데이트 해준다.

4. 마지막으로 거리갱신을 한 번더 수행한다.
   이때, 최단 거리 테이블이 갱신된다면 음수 간선 사이클이 존재한다는 뜻이다.

다음의 코드는 정점의 개수 만큼 반복하며, 업데이트 되는 경우가 마지막에 생기면 음수 간선 사이클이 존재한다고 판별하는 코드이다.

코드 (java)

https://www.acmicpc.net/problem/11657
벨만-포드 알고리즘을 적용하는 문제

package Y2022D05;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class J07_타임머신 {
	
	static class edges {
		int start;
		int end;
		int value;
		public edges(int start, int end, int value) {
			this.start = start;
			this.end = end;
			this.value = value;
		}
		@Override
		public String toString() {
			return "edges [start=" + start + ", end=" + end + ", value=" + value + "]";
		}
	};
	static BufferedWriter bw;
	static int N;
	static int[] distance;
	static ArrayList<edges> list;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 초기화
		distance = new int[N];
		for (int i = 0; i < distance.length; i++) {
			distance[i] = 7_000_000;
		}
		// 버스 
		list = new ArrayList<>();
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken()) -1;
			int B = Integer.parseInt(st.nextToken()) -1;
			int C = Integer.parseInt(st.nextToken());
			list.add(new edges(A, B, C));
		}
		
		// 계산하기
		// 시작은 0으로
		distance[0] = 0;
		if ( bellmanford() == false) {
			System.out.println(-1);
		} else {
			// 1번(start제외) 부터 다른 모든 노드로 가기위한 최단거리 출력
			for (int i = 1; i < N; i++) {
				if( distance[i] == 7_000_000 ) {
					System.out.println("-1");
				} else {
					System.out.println(distance[i]);
				}
			}
			
		}
		
		
	}
	
	// return false -> 음수 순환 존재
	// return true -> 순환없음
	private static boolean bellmanford() {
		System.out.println(Arrays.toString(distance));
		
		// N번 반복하는 이유는 마지막에 음의 사이클이 있는지 확인 
		for (int i = 0; i < N; i++) {
			// 모든 간선확인
			for (int j = 0; j < list.size(); j++) {
				int cur = list.get(j).start;
				int next = list.get(j).end;
				int cost = list.get(j).value;
						
				if(distance[cur] == 7_000_000) continue;
				// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우 
				if(distance[next] > (distance[cur] + cost)) {
					distance[next] = distance[cur] + cost;
							
					// n번째 라운드에서 값이 갱신된다면 음수 순환 존재 
					if (i == N-1) {
						return false;
					}
				}
				
			}
			
			System.out.println(Arrays.toString(distance));
			
		}
		return true;
	}

}

다른 문제

https://github.com/AlwaysRYU/Daily_CodingTEST/blob/master/2022/2022.05/J07.%EC%9B%9C%ED%99%80.md