벨만 - 포드 알고리즘

Bellman - Ford 알고리즘은 다익스트라 알고리즘과 달리 

모든 노드를 주기적으로 갱신시켜주기 때문에 \(O(V*E)\)가 걸리지만

음의 가중치를 포함한 노드들에 대해서도 성공적으로 탐색할 수 있다.

 

www.acmicpc.net/problem/11657

11657번: 타임머신

 

대표적인 벨만 - 포드를 사용한 문제이다.

우선 각 간선의 수만큼 입력을 받는데 편하게 계산하기 위해 좌표들에 -1씩 해서 받아줬다.

 

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		ar[a - 1].push_back({ b - 1,c });
	}

 

문제 조건 중 

 

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.

 

라는 조건이 있다.

 

이 문제를 풀 때에는 조심해야 할 점이 있는데 그래프에 음의 사이클이 포함되어 있는가?이다.

음의 사이클이 포함되어 있다면 그 사이클이 나오기 전까지의 노드들만 정상으로 갱신될 것이고 그 이후의

값들은 모두 음의 무한대 값이 나올 것이다.

 

void bellmanford() {
	cost[0] = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n; j++) {
			for (auto& i : ar[j]) {
				int nxt = i.first, d = i.second;
				if (cost[j] != INF && cost[nxt] > cost[j] + d) {
					cost[nxt] = cost[j] + d;
				}
			}
		}
	}
}

 

위와 같은 코드가 기본적인 벨만 - 포드의 틀이라 할 수 있는데 이 코드는 음의 가중치가 포함되어있는 그래프를

찾지 못한다.

 

• 각 vertax - 1 만큼 돌려주는 중첩 문에 대해서 (vertax - 1) + 1 만큼 돌려준다
• 현재 vertax -1까지 돌렸으면 모든 갱신이 완료된 것이다. 하지만,
• 맨 마지막(vertax ( -1 + 1))에 갱신이 된다면 사이클에 빠져 무한히 갱신하게 된다는 뜻이다

위와 같은 접근법으로 해결한다.

 

bool bellmanford(int start) {
	dst[start] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (auto& v : ar[j]) {
				int nxt = v.first;
				int d = v.second;
				if (dst[j] != INF && dst[nxt] > dst[j] + d) {
					dst[nxt] = dst[j] + d;
					if (i == n - 1) return true;
				}
			}
		}
	}
	return false;
}

 

n -1 이 아닌 n 번 돌리며 마지막에 갱신이 된다면 음의 가중치를 포함하고 있다는 뜻이다.

 

전체적인 소스 코드

 

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const ll INF = 1e18;
int n, m, a, b, c;
vector<ll> dst(501, INF);
vector<pair<int, int>> ar[501];

bool bellmanford(int start) {
	dst[start] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (auto& v : ar[j]) {
				int nxt = v.first;
				int d = v.second;
				if (dst[j] != INF && dst[nxt] > dst[j] + d) {
					dst[nxt] = dst[j] + d;
					if (i == n - 1) return true;
				}
			}
		}
	}
	return false;
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		ar[a - 1].push_back({ b - 1,c });
	}
	
	if (bellmanford(0)) {
		cout << -1 << endl;
	}
	else {
		for (int i = 1; i < n; i++) {
			int ans = dst[i] != INF ? dst[i] : -1;
			cout << ans << '\n';
		}
	}

	return 0;
}