[최단 경로] 벨만-포드 알고리즘

leeeha·2022년 8월 18일

목록 보기

17/20

참고 영상: https://www.youtube.com/watch?v=Ppimbaxm8d8

백준 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을 출력한다.

음수 간선이 포함된 최단 거리 문제

✔ 다익스트라 알고리즘 먼저 알아보기

위의 그래프에서 2, 3, 5번 노드 사이에는 음수 사이클이 생긴다. (간선의 가중치 합을 모두 더해보면) 이런 상황에서는, 1번에서 다른 모든 노드로 가는 최소 비용이 전부 음의 무한대가 된다. 최솟값을 만들기 위해 음수 사이클을 계속 반복해서 돌면, 음의 무한대가 되기 때문이다.

이처럼 음수 간선이 존재하는 그래프에서 음수 사이클이 발생하는지 확인하기 위해, 벨만 포드 알고리즘을 사용할 수 있다.

벨만 포드 알고리즘

최단 경로 문제

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

Case1) 한 노드에서 다른 모든 노드까지의 최단 경로 구하기 (single source shortest path)

가중치가 없거나 모두 동일한 경우: BFS

가중치가 다른 경우

음수 가중치가 없을 때: 다익스트라

음수 가중치가 있을 때: 벨만 포드 (음수 사이클의 유무 탐지 가능)

벨만 포드 알고리즘은 음수 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 사이클이 발생하는지도 확인할 수 있다. 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다.

Case 2) 모든 노드 사이의 최단 경로 구하기 (all pairs shortest path)

플로이드 워셜 알고리즘

벨만 포드 알고리즘의 동작 과정

출발 노드를 설정한다.

최단 거리 테이블을 초기화 한다.

다음의 과정을 (N-1)번 반복한다.
1) 간선 E개를 전부 하나씩 확인한다.
2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

만약 음수 사이클이 발생하는지 확인하고 싶다면, 3번의 과정을 한번 더 수행하면 된다. 이때 최단 거리 테이블이 갱신된다면, 음수 사이클이 존재하는 것이다.

cf) 더 자세한 설명: https://yabmoons.tistory.com/365 (인내심을 갖고 차근차근 읽어보자!)

다익스트라 vs. 벨만 포드

다익스트라 알고리즘은 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다는 점에서 그리디 알고리즘으로 분류된다. 그리고 음수 간선이 없는 상황에서 최적의 해를 보장한다.

반면에, 벨만 포드 알고리즘은 매번 '모든 간선'을 하나씩 확인한다. 따라서, 다익스트라 알고리즘에서의 최적해를 항상 포함한다. 이런 점에서 다익스트라 알고리즘에 비해 시간은 더 오래 걸리지만, 음수 사이클의 유무를 탐지할 수 있다.

C++ 코드로 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#define INF 1e9 
#define MAX 501  
using namespace std; 

int n, m; 
vector<pair<int, pair<int, int>>> edges; 
long long d[MAX]; // 오버 플로우 및 언더 플로우 방지

bool bellmanFord(int start){
	d[start] = 0; 

	// (n-1)번의 라운드 반복 
	for(int i = 1; i <= n; i++){ 
		// 매 반복마다 '모든 간선'을 하나씩 확인한다. 
		for(int j = 0; j < m; j++){ 
			int from = edges[j].first; 
			int to = edges[j].second.first; 
			int cost = edges[j].second.second; 

			// 한번이라도 계산된 정점에 대해서만 (단절된 정점은 제외) 
			if(d[from] == INF) continue; 
			
			// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 
			if(d[to] > d[from] + cost){ 
				d[to] = d[from] + cost; // 최단 거리 테이블 갱신 
				
				// n번째에도 최단 거리가 갱신된다면 음수 사이클 존재!  
				if(i == n) return true; 
            }
		}
	}
    
	return false; 
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c; 
		edges.push_back({a, {b, c}}); 
	}
	
	fill_n(d, MAX, INF); 

	bool negativeCycle = bellmanFord(1);

	if(negativeCycle){
		cout << "-1\n";
		return 0; 
	}

	// 1번을 제외한 다른 모든 노드로 가기 위한 최단 거리 출력 
	for(int i = 2; i <= n; i++){
		if(d[i] == INF){
			cout << "-1\n";
		}else{
			cout << d[i] << "\n"; 
		}
	}
	
	return 0; 
}