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

Bellman-Ford Algorithm

벨만 포드 알고리즘은 음수 간선이 존재하고 그것이 사이클을 만들어낸다고 해도 최단거리를 만들 수 있는 알고리즘이다.

다익스트라 알고리즘은 익히 알다시피, 음수 간선이 존재하면 사용할 수 없는 것을 알고 있을 것이다.

다익스트라와 벨만 포드의 차이

다익스트라와 벨만 포드는 둘 다 1차원 dist 배열을 갱신하며 최소치를 기록하는 스킬은 똑같다. 그러나, 다익스트라는 모든 노드를 살펴보지 않는다. 가능한 경우에만 다음 노드로 이동하기 때문이다. 그러나 이 효율적인 방식 때문에 음수 간선이 있으면 다익스트라를 사용할 수 없다.

 

그러나 벨만 포드는 효율적이지 않게도 모든 노드를 살펴본다. 그래서 시간복잡도가 N*M이다. 그리고 음수간선이 있어도 사용이 가능하다.

 

바로 아래 그래프로 예를 들어보자.

시작을 1이라고 하자.

 

1번으로 시작하여 인접 노드를 업데이트한다.

dist[2] = 3

dist[4] = 1

 

2번 노드로 이동해 인접 노드를 업데이트하자.

dist[3] = 8

 

3번 노드로 이동해 인접 노드를 업데이트하자.

업데이트가 이뤄지지 않는다. 모든게 최소이다.

 

4번 노드로 이동해 인접 노드를 업데이트 하자.

dist[2] = -2

 

5번 노드로 이동해 인접 노드를 업데이트 하자.

5번노드는 아직 방문하지 않았다. 즉, 1번이 아직 도달하지 못했으므로 업데이트를 하지 않는다.

 

이것을 N - 1번 반복한다. 두번째 반복을 보자.

 

1번에서는 당연히 갱신되지 않는다.

2번에서도 갱신되지 않는다.

3번에서도 갱신되지 않는다.

4번에서는 갱신이된다. dist[2] = -5

5번에서는 갱신되지 않는다.

 

왜 N - 1 번?

→ 이 과정은 N - 1번 반복해야한다. 왜냐하면 1번에서 모든 정점을 잇는다. 이것이 전재조건이기 때문인데, 다음 그래프를 보자.

 

 

만약 순서가 3에서 4를 잇고, 2에서 3을 잇고, 1에서 2를 잇는다고 생각해보자. 그렇다면 2→3는 아직 3이 1에서 도달하지 못했기 때문에 업데이트가 이뤄지지 않는다. 그런데 이후 1→2 가 이뤄진 후 다시 연산하면 2→3이 업데이트를 이룰 수 있다.

그러므로 N - 1번의 계산이 필요하다.

 

그렇다면 어떻게 음수 사이클을 확인하는가?

위를 이해했다면 다음은 쉽다. 왜냐하면 스테이블한 간선들이라면 N - 1번으로 최적해가 만들어진 상태이기 때문에 더 이상 최소 값이 갱신 되지 않아야 한다. 그러므로 한 번 더 갱신을 했을 때 최소값이 생긴다면 그것은 사이클이 있는 그래프라고 판단이 가능하다.

 

#include <iostream>
#include <vector>
#define INF 13513512
using namespace std;

vector<pair<pair<int, int>, int>> node;
int N, M;

int dist[501];

bool Bellman_Ford() {
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < node.size(); j++) {
			int here = node[j].first.first;
			int next = node[j].first.second;
			int cost = node[j].second;

			if (dist[here] == INF) continue;
			if (dist[next] > dist[here] + cost) dist[next] = dist[here] + cost;
		}
	}

	for (int j = 0; j < node.size(); j++) {
		int here = node[j].first.first;
		int next = node[j].first.second;
		int cost = node[j].second;

		if (dist[here] == INF) continue;
		if (dist[next] > dist[here] + cost) {
			return false;
		}
	}

	return true;
}

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

	cin >> N >> M;

	for (int i = 0; i <= N; i++) dist[i] = INF;
	
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		node.push_back({{ a, b },c });
	}

	dist[1] = 0;

	if (Bellman_Ford()) {
		for (int i = 2; i <= N; i++) {
			if (dist[i] == INF)
				cout << -1 << '\\n';
			else
				cout << dist[i] << '\\n';
		}
	}
	else {
		cout << -1 << '\\n';
	}
}