벨만-포드 알고리즘이란?

그래프의 한 정점에서 다른 정점까지 가는 최단거리를 구하는 알고리즘이다.
이전 시간에 다뤄봤던 다익스트라 알고리즘과 매우 비슷하지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다.

이전에 배웠던 최단 경로 알고리즘을 정리해보자.

1. 가중치가 없을 때(=동일할 떄) : BFS
2. 가중치가 다를 때 :
   a) 모두 양수 가중치 일 때 : 다익스트라
   b) 음수 가중치가 포함될 때 : 벨만-포드

벨만-포드 알고리즘 동작

1. 간선을 입력받고 출발 정점과 도착 정점 설정.
2. 1~N까지 정점의 최단 거리 테이블을 INF(무한)로 초기화
3. 
   a) 모든 간선을 하나씩 탐색하여 최단 거리 테이블을 갱신
   b) a번 과정을 N - 1번 반복(정점이 5개인 경우 a정점에서 b정점으로 갈 수 있는 최대 간선은 4개이므로)
   
   
4. 3번 과정이 끝났다면 간선 수만큼 탐색하여 최적의 해가 갱신될 수 있는지 확인
   (만약 갱신이 된다면 음의 사이클이 존재)

벨만-포드 알고리즘 그림으로 알아보기

1~5번 정점으로 구성된 그래프가 있다.
처음에 distance 값을 INF로 초기화 시켜준다.
시작 정점을 1번 정점으로 모든 정점까지의 최단 거리를 구해보자.

초기화

시작 정점 1의 distance를 0으로 초기화 해준다.
이 때 다른 값이 INF라는 뜻은 초기 상태에는 자신 이외의 정점은 갈 수 없다라는 의미이다.

1번째

시작 정점 1번에서 갈 수 있는 정점은 2번 정점과 3번 정점이다.
각각의 값은 5, 4로 INF보다 작으므로 갱신 시켜준다.

2번째

이제 2, 3번 정점에서 갈 수 있는 경로를 찾아보자.
2번 정점에서 갈 수 있는 정점은 3, 5번 정점이다.
2->3으로 갈 때 값은 -3으로 1->3(4) 경로보다 1->2->3(2) 가중치가 더 짧다는 것이 핵심이다.

따라서 간선을 더 많이 쓰지만 가중치 값이 작으므로 갱신 시켜준다.
2->5 가중치 값도 18로 갱신하여주고 마찬가지로 3->4 가중치 값도 9로 갱신 시켜준다.

3번째

다음 그림을 보면 4번 정점의 가중치 값이 9->7로 갱신된다.
이 말은 즉, 1->3->4(9)의 경로보다 1->2->3->4(7)의 경로의 가중치 값이 작다는 것이다.

마찬가지로 5번 정점의 가중치 값이 18->16으로 갱신되는데 1->2->5(18) 경로보다 1->3->4->5(16) 경로의 가중치 값이 작으므로 갱신된다.

4번째(N-1번째 = 마지막)

5번 정점의 가중치 16->14로 갱신되는데 1->3->4->7(16) 경로보다 1->2->3->4->5(14) 경로의 가중치 값이 더 작다는 것을 알 수 있다.

따라서 1에서 각 정점의 최단 거리는 다음과 같다.

N-1번 갱신을 하여 최적의 해를 구했지만 끝난 것이 아니다.
음의 싸이클이 있는지 체크를 해줘야 한다.

위 그래프는 싸이클이 없지만 음의 싸이클이 있는 다음 그림을 보자.

2->3->4번 싸이클을 보면 음의 싸이클이 발생한다.
최솟값을 만들기 위해 음의 사이클을 계속 반복하면 음의 무한대가 발생한다.
우리는 이 음의 싸이클이 있는지 체크를 해줘야 한다.

N-1번 값을 갱신한 후 그 값이 더 갱신된다면 이것은 음의 싸이클이 존재하는 것이다.
N-1번 갱신했을 때 최적의 해가 나오는데, 이 최적의 해보다 작아진다는 것은 바로 음의 싸이클이 존재하므로 작아질 수 있는 것이다.

소스코드

#include<iostream>
#include<vector>
#include<algorithm>

#define INF 2147000000

using namespace std;

typedef pair<int, int> p;

vector <pair<int, p>> v;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M, s, e, d;
	int sVertex, eVertex;
	cin >> N >> M;
	vector<int>res(101, INF);

	for (int i = 0; i < M; i++) {
		cin >> s >> e >> d;
		v.push_back(make_pair(d, make_pair(s, e)));
	}

	cin >> sVertex >> eVertex; //시작 정점과 끝 정점
	res[sVertex] = 0;	//시작 정점의 값을 0으로 초기화

	for (int i = 1; i < N; i++) { // N-1번 반복문을 통해 값 갱신
		for (int i = 0; i < v.size(); i++) {
			int nextDis = v[i].first;
			int from = v[i].second.first;
			int to = v[i].second.second;

			if (res[from] != INF && res[from] + nextDis < res[to]) // INF(시작 정점부터 i번만에 갈 수 없는 정점)가 아니고
				res[to] = res[from] + nextDis;				//값을 갱신 할 수 있다면 갱신
		}
	}

	//음의 싸이클이 있는지 체크
	for (int i = 0; i < v.size(); i++) {
		int nextDis = v[i].first;
		int sv = v[i].second.first;
		int ev = v[i].second.second;

		if (res[sv] != INF && res[sv] + nextDis < res[ev]) { // 만약 값이 갱신된다면 음의 싸이클 존재하므로 -1출력 후 종료!
			cout << "-1";
			return 0;
		}
	}
	cout << res[eVertex];

	return 0;
}