7주차 알고리즘 스터디 - 벨만 포드 알고리즘 (Bellman - Ford Algorithm)

1) 벨만포드 알고리즘 개념

갓키백과에 따르면 벨만포드 알고리즘은  가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다.

다익스트라 알고리즘과 같이 한 정점에서부터 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용한다. 

모든 경우의 수를 다 탐색하며 확인한다.

정점이 1,2,3,4가 있다면 1에서 각 점 2,3,4로 가는데 걸리는 각각의 최소비용을 구하는데 사용할 수 있다.

시간복잡도도 다익스트라보다 크지만 벨만포드의 장점은 가중치가 음수일 때 사용가능하다는 것이다. 

2) 벨만포드 알고리즘의 원리 

기본 아이디어는 a라는 시작노드에서 z라는 정점까지의 최소비용을 구하려면 이미 y까지의 경로가 최단경로라 믿고
a에서 y까지의 최단경로 + y에서 z까지의 가중치를 더하는 것이다.  

 

그렇다면 시작노드가 a이고 b ~ z 까지 총 26개의 정점을 가지는 그래프가 있다고 가정해보자.

그렇다면 각각 b까지의 최단경로 , c까지의 최단경로 ,,,,,, z까지의 최단 경로 총 25번 연산을 수행해야한다.

이말은 곧 총 정점 중 시작노드인 1개를 뺀 V -1 만큼 연산을 반복해야한다는 것이다. 

이거만 알면 어렵지 않다. 

 

1. 맨 처음 시작노드로부터 모든 정점까지의 거리 혹은 비용을 무한대 INF로 초기화해준다. 

2. 시작노드로부터 간선을 따라 갈 수 있는 정점까지의 최소비용을 계산한다. 

3. 새로 계산한 값 (시작노드 -> 이전 노드까지 오는 최소비용 + 이전 노드로부터 현재까지 오는 간선의 가중치)과 이미 계산되어있는 최소비용 중 더 작은 값을 선택한다. 

2 ~ 3 번 과정을 V-1번 반복한다. 

4. 한 번 더 반복 해 음의 사이클이 존재하는지 확인한 후 값을 반환해준다.

 

* 3번과 같은 과정을 edge relaxation이라고 하며 최소비용을 이전노드에 오기까지의 최소비용들로 쪼개 보는 것이다. 

  그리고 새로 계산한 값이 이전 값보다 작은 지 확인한다 . 

말보다는 그림으로 보는 게 더 빠르다.

지금 특이한 점이 있다면 시작노드를 제외한 모든 노드들까지의 최소비용이 계속 최소로 업데이트 되고 있다.

이런 경우가 왜 생기냐? 아래와 같은 음의 사이클이 존재하기때문이다. 

사이클에 있는 가중치들의 합이 음수면 음의 사이클이라고 한다. 현재 -4 + -4 + 5 = -3으로 음의 사이클이 존재한다. 

이렇게 계속 반복을 하다보면 결국 -INF까지 가게되어 진짜 최솟값을 찾을 수 없다. 

그렇기 때문에 맨 마지막에 음의 사이클이 존재하는 지 꼭 확인해주어야한다. 어떻게 ? 

V - 1 번의 루프 이후 한 번 더 즉, v번째 루프를 돌아 확인해준다. 

만약 v-1 번 이후에도 값이 최소로 갱신이 된다면 음의 사이클이 존재한다는 뜻이기 때문이다. 

 

3) 시간복잡도 : O( VE )

다익스트라 알고리즘보다 시간이 오래걸리지만 간선이 음수일때 사용할 수 있다는 장점이 있다. 

 

4) 코드 구현 c++

예제로 백준 11657번 타임머신 풀이 (www.acmicpc.net/problem/11657)

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


using namespace std;
vector<pair<int, int>> graph[500]; //그래프
vector<pair<int, int>> temp;
long long min_cost[505]; //최소비용이 담긴 배열
//INF로 1e9가 들어가야하기에 longlong으로 바꿔줘야한다

int main() {
	int n, m;
	scanf("%d %d", &n, &m); //n = 정점 , m = 간선
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a - 1].push_back({ b - 1,c }); //간선은 1부터 시작이지만 배열은 0부터 시작
	}

	//////////////////벨만 포드 알고리즘////////////////////

	//1. 거리비용을 INF로 초기화 시켜준다.
	fill(min_cost, min_cost + n, 1e9);
	//시작노드 자기 자신은 거리비용이 0이다.
	min_cost[0] = 0;

	bool flag = false; ///음의 사이클 확인하는 함수

	//2. 노드 -1 번 반복한다 .
	//4. 이후 음의 사이클 판별을 위해 한 번 더 반복한다.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < graph[j].size(); k++) {
				int depart = j;
				int arrive = graph[j][k].first;
				int cost = graph[j][k].second;
				//만약 도착할 정점의 최소비용보다 출발 정점의 최소비용 + 출발->도착의 가중치가 더 작다면 업데이트해줌
				if (min_cost[depart] != 1e9 && min_cost[arrive] > min_cost[depart] + cost) {
					min_cost[arrive] = min_cost[depart] + cost;

					if (i == n - 1) flag = true; //i가 n-1일때 업데이트가 되었다면 음의 사이클이 존재한다는 뜻
				}
			}
		}
	}

	if (flag) printf("-1\n");
	else {
		for (int i = 1; i < n;i++) {
			if (min_cost[i] == 1e9) printf("-1\n"); //음의 사이클이 존재하지 않지만 값이 inf라면 이어진 간선이 없단 뜻
			else printf("%lld\n", min_cost[i]);
		}
	}
}