섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (4) 벨만-포드

🔎 벨만-포드 알고리즘이란?

그래프 최단 거리 구하는 알고리즘
1. 다익스트라(Dijkstra) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 
2. 벨만-포드(Bellman-Frod) : 특정 한 정점 -> 다른 모든 정점의 최단 거리 
3. 플로이드-와셜(Floyd-Wrasahll) : 모든 정점들 간의 최단 거리 

⬛ 08-5. 벨만-포드 알고리즘

🟦 벨만- 포드 알고리즘

• 벨만-포드 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 알고리즘
• cf. 다익스트라와 다른 점 : 음수 가중치 엣지 있어도 수행 가능 !
• 보통 음수 사이클 존재 여부 판별하는 문제가 多 출제

🟧 벨만-포드 핵심 이론

• 1) 에지 리스트로 그래프 구현 후, 최단 경로 배열 초기화
• 2) 모든 엣지 확인하며 정답 배열 업데이트 하기
  • 음수 사이클이 X : N-1번의 반복으로 정답 배열 완성된다.
• 3) 음수 사이클 유무 확인하기

== 즉, 마지막에 한 번 더 모든 엣지 사용하여 사이클 확인

• • 이후에 모든 엣지를 한 번씩 다시 N번 반복했을 때 업데이트 되는 노드가 발생하는지 확인한다.
  • 업데이트 되는 노드가 있따 == 음수 사이클 때문에 가중치 감소가 나타나는 것

🟦 백준 11657번. 타임머신 - 벨만 포드

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

풀이 - 벨만 포드

[주의] cf. 다익스트라 - 인접 리스트 ‘노드’ 중심 그래프 표현

벨만 포드 - 엣지 리스트로 ‘엣지’ 중심 표현

- N-1번의 반복으로 M개의 간선에 대하여 정답 배열 업데이트 작업 수행 → 1차 정답 배열 세팅

- 1번 더 M개의 간선에 대하여 세팅했을 때 갱신되는 값이 존재할 경우 return false 를 주는 방식

package to_0705_5;

import java.util.Arrays;
import java.util.Scanner;

/*벨만 포드 정복하기 */
class Edge{
	int st, ed, val;
	Edge(int st, int ed, int val){
		this.st= st;
		this.ed =ed;
		this.val =val;
	}
}
public class Main {
	static int N, M;
	static long distance[];
	static Edge edges[];
	static final int INF = Integer.MAX_VALUE;
	
	static boolean bellmanFord(int start) {
		distance[start] = 0;
		for(int i=0; i<N-1; i++) {//N-1번 반복 수행 
			for(int j=0; j<M; j++) {
				Edge cur = edges[j];
				if(distance[cur.st] != INF && distance[cur.ed]>distance[cur.st]+cur.val) {
					distance[cur.ed] = distance[cur.st]+cur.val; //여기서 갱신처리 
				}
			}
		}
		
		//1번 더 M개의 간선에 대하여 사이클 수행하며 업데이트 여부 확인 
		for(int i=0; i<M; i++) {
			Edge cur = edges[i];
			if(distance[cur.st] != INF && distance[cur.ed]>distance[cur.st]+cur.val) {
				//갱신되는 값이 존재할 경우
				return true;
			}
		}		
		return false;//발견안됐으면 false
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb=new Scanner(System.in);
		N= kb.nextInt();
		M= kb.nextInt();
		
		distance = new long[N+1];
		edges =new Edge[M+1];
		
		Arrays.fill(distance, INF);
		//입력받기 
		for(int i=0; i<M; i++) {
			int a = kb.nextInt();
			int b= kb.nextInt();
			int c= kb.nextInt();
			edges[i] = new Edge(a, b, c);
		}
		//벨만포드 호출
		boolean flag = bellmanFord(1);
		
		if(!flag) {
			for(int i=2; i<=N; i++) {
				if(distance[i]==INF) {
					System.out.println("-1");
				}else {
					System.out.println(distance[i]);
				}
			}
		}else {//사이클 발견되어서 true리턴시
			System.out.println("-1");
		}
	}
}