벨만 포드 알고리즘 (Bellman-Ford algorithm)

벨만 포드 알고리즘(Bellman-Ford algorithm)은 다익스트라 알고리즘과 마찬가지로 하나의 정점에 대한 모든 정점의 최단 거리를 찾는 문제에 적용됩니다.

다익스트라는 음수간선이 존재하면 사용할 수 없지만 벨만 포드 알고리즘은 음수간선이 존재해도 사용할 수 있습니다.

가중치의 합이 0보다 작은 싸이클을 음수 싸이클이라고 하는데, 그래프에 음수 싸이클이 존재하면 벨만 포드 알고리즘을 사용할 수 없습니다.

 

다음은 벨만 포드 알고리즘이 적용되는 문제입니다. 

https://www.acmicpc.net/problem/11657

11657번: 타임머신

이 문제에서는 음수의 간선이 주어질 수 있다는 부분에서, 우리는 다익스트라가 아닌 벨만 포드 알고리즘을 적용시킬 준비가 되어 있어야 합니다.

또한, 이 문제에서는 음수 싸이클이 그래프 내에 존재한다면 -1을 출력하라고 명시 해놓았기 때문에, 이 부분만 유의해서 문제를 해결하면 쉽게 맞았습니다!!!를 받을 수 있습니다.

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
vector<pii> edge[501];
ll d[501];
bool negative_cycle = false;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m; //노드 갯수, 엣지 갯수
	for (int i = 0; i < m; i++) {
		int a, b, c; //시작노드, 목적지노드, 가중치
		cin >> a >> b >> c;
		edge[a].push_back({ b,c });
	}
	for (int i = 0; i < 501; i++) d[i] = INT_MAX; //모든 최단경로 INF로 초기화
	d[1] = 0; //시작 노드의 최단경로 0으로 초기화
	for (int i = 0; i < n; i++) { //n - 1 + 1번 반복
		for (int j = 1; j <= n; j++) { //노드 인덱스
			for (int k = 0; k < edge[j].size(); k++) { //노드와 연결된 엣지 인덱스
				int dest = edge[j][k].first; //연결된 노드의 인덱스
				int weight = edge[j][k].second; //연결된 노드의 가중치
				if (d[dest] > d[j] + weight && d[j] != INT_MAX) {
					d[dest] = d[j] + weight;
					if (i == n - 1) negative_cycle = true;
				}
			}
		}
	}
	if (negative_cycle) { //음수 싸이클이 존재한다면
		cout << -1 << "\n";
		return 0;
	}
	for (int i = 2; i <= n; i++) {
		if (d[i] == INT_MAX) cout << -1 << "\n"; //최단거리가 INF이면 방문불가한 노드
		else cout << d[i] << "\n";
	}
	return 0;
}