[PS일지]백준 11657번 타임머신, 벨만-포드 알고리즘

전에 배웠던 다익스트라는 치명적인 결점이 있었다...

바로 음수간선에는 제대로 된 최솟값을 찾지못한다는 것이다!

그리고 무엇보다 음의 사이클(음수가 포함된 회로)를 찾지 못한다.

음의 사이클이 존재하는 그래프에서는 어떤 알고리즘도 정확하게 최솟값을 찾기가 불가능하다

 

예를 들어 보자 

1번에서 2번으로 가는 것의 가중치가 1이고

2번에서 3번으로 가는 것의 가중치가 -10이고

3번에서 1번으로 가는 것의 가중치가 1이라 하자

이의 최단경로는 구할 수 없다. 음의 무한대이기 때문이다. 

1번-2번-3번-1번-2번-3번- .... 순으로 가면 음의 무한대가 된다...

 

이러한 문제들을 해결하는 아주 좋은 도구인 벨만-포드 알고리즘을 배울 것이다.

 

벨만-포드 알고리즘의 원리는 생각보다 간단하다.

W(u, v)를 u-v로 가는 간선의 가중치(길이)라고 가정하자.

또한 dist[x]를 시작점부터 x까지의 최단경로라고 하자.

dist[v] ≤ dist[u]+W(u, v)

동작과정은 위 식으로부터 시작된다

 

증명하면

예를 들어 저 식을 직통으로 위배하는 값, W(u, v) = 30, dist[v] = 50, dist[u] = 10 이라고 가정해보자

그 말은 s에서 u로 오는 거리가 10이 되는 경로가 있다는 것이다.

그 경로 뒤에 u와 v를 붙히면 u와 s 사이의 경로 거리는 즉 40이 되는데

그에 u와 v는 40보다 커질 수 없지만 40보다 크기 때문에 모순이다.

이 논리를 식으로 적용하면 위 식이 나옴을 알 수 있다.

(처음에 이 증명보고 감탄했다.)

 

그렇다면, 배열 upper[x]를 선언하여(거리의 최솟값의 상한을 갱신/저장하는 배열이다)

상한을 낮춰가는 방법을 사용하면 어떨까?

 

어떤 정점 x와 인접한 정점 y를 검사하여 upper[x]+W(x, y) < upper[y] 라면 upper[y] =  upper[x]+W(x, y)로 갱신하는 것이다. 처음에는 시작 정점을 제외하고 upper는 INF(매우 큰 값)이다.

정점을 모두 순회하여 인접한 정점을 갱신한 후, 그걸 또 루프를 V-1번 돌리면(V-1번을 돌리는 이유는 갱신을 모두 하는데 드는 최대 반복횟수가 V-1번이기 때문이다.(종만북을 참고하면 증명이 있습니다! 음의 사이클이 존재하지않는 한 최단경로는 같은 간선을 2번 이상 지나지 않는다는 성질로 증명이 가능합니다.))  어느샌가 upper에는 모든 최솟값이 저장되게 된다.

 

여기서, V-1번 돌리고도 아직 갱신할게 남아있다면(V번 반복 가능) 바로 음의 사이클이 존재한다는 뜻이다.

벨만-포드 알고리즘은 음의 사이클의 존재성까지 알아낼 수 있는 것이다.

또한

이것은 양수간선이라는 조건이 없어 다익스트라보다 좋다, 물론 시간복잡도는

O(V*E)라 사실상 V^3이라 할 수 있어 조금 느리다.

 

백문이 불여일견 문제를 풀어보자

 

 

기본에 충실한 벨만-포드 문제다.

벨만-포드 알고리즘을 통해 최단경로를 찾고, 음의 사이클이 존재하는지 확인하는 작업을 거치면 된다.

#include <iostream>
#include <vector>
using namespace std;
#define INF 900000000
vector<pair<int, int>>state[510];
long long upper[510] = {0, };
int n, m;
int pan = 0;
void bmf(){
	int x, y, z;
	for(x = 0; x < n; x++){
		pan = 0;
		for(y = 0; y < n; y++){
			for(z = 0; z < state[y].size(); z++){
				if(upper[y] == INF||upper[y]+state[y][z].second >= upper[state[y][z].first])continue;
				pan = 1;
				upper[state[y][z].first] = upper[y]+state[y][z].second;
			}
		}
		if(!pan)break;
	}
}
int main() {
	int i, a, b, w;
	cin >> n >> m;
	for(i = 0; i < m; i++){
		cin >> a >> b >> w;
		state[a-1].push_back(make_pair(b-1, w));
	}
	for(i = 0; i < n; i++)upper[i] = INF;
	upper[0] = 0;
	bmf();
	if(pan){
		cout << "-1";
		return 0;
	}
	for(i = 1; i < n; i++){
		if(upper[i] >= INF)cout << "-1";
		else cout << upper[i];
		cout << "\n";
	}
}

귀여운 무끝 >.<

 

댓좀요