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

벨만 포드 알고리즘이란?

벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 마찬가지로 시작점을 정해주면 시작점 기준으로 다른 모든 정점으로의 최단 거리를 구해주는 알고리즘이다.

 

이때, 벨만 포드 알고리즘의 최대 특징은 다익스트라 알고리즘과는 달리 간선의 가중치가 음수일 때도 사용할 수 있다는 것이다.

 

벨만 포드 알고리즘의 구조

그럼 벨만 포드 알고리즘은 무엇이 다르기에 음수의 가중치가 있어도 최단경로를 구할 수 있는 것일까?

벨만 포드 알고리즘은 2중 for문을 이용하여 가능한 모든 경우를 전부 다 체크한다. 우선 최단 경로의 정의를 알아볼 필요가 있다.

 

최단 경로란 같은 정점을 두 번 지날 일이 없다는 것을 의미한다. 즉, 가능한 최단 경로의 간선 개수는 많아봐야 V - 1개이다.

 

이 말은 반복문이 V - 1번 루프를 돌았다면 모든 정점에 대한 최단 경로가 구해져야 한다는 것이다. 즉, V번 반복을 돌고 해당 루프에서 최단 경로의 값이 갱신이 된다면 이는 무한 루프 즉, 음수 싸이클이 존재한다는 것을 의미한다.

 

우선 첫 번째 경우를 보도록 하겠다.

우선 벨만 포드 알고리즘은 존재하는 모든 간선을 돌아보면서 해당 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것이다.

 

첫 번째 그래프의 경우 방문 순서에 따라서 V - 1번 루프를 돌지 않고도 2번 정점까지의 최단 경로를 구할 수 있다.

 

하지만 다음 그래프의 경우를 보도록 하겠다.

위의 그래프의 경우에는 방문 순서에 따라 e 정점이 먼저 방문하게 되어 정점 c의 최단 경로를 4로 갱신했다고 가정해보자. 이에 따라 정점 d도 (4, c)의 영향을 받아 5가 되었다고 가정해보자.

 

이렇게 될 경우 벨만 포드 알고리즘은 모든 간선을 검사하기 때문에 (2, b)에서 오는 정점 c로 가는 경로도 검사하게 될 것이다. 이렇게 될 경우 정점 c의 최단 경로는 (2, b) - 2로 c는 0으로 갱신하게 되고 추후 반복문에서 d도 (0, c) + 1로 1이라는 최단 경로를 갱신하게 될 것이다.

 

이렇듯 모든 경우의 수를 돌아보며 최단 경로를 찾는 것이 벨만 포드 알고리즘의 구조라고 할 수 있다.

 

그렇다면 다음 경우는 어떨까?

 

위의 경우는 정점 b→c→d를 빙글빙글 돌게 되면 최단 경로가 무한히 갱신하게 될 것이다. 이것이 앞에서 얘기했던 음수 싸이클을 의미한다.

 

앞에서도 얘기했지만 최단 경로란 같은 정점을 두 번 지날일이 없다는 것을 의미한다. 즉, V - 1번 반복문을 전부 돌게 된다면 시작점으로 부터 모든 정점으로의 최단 경로가 구해져야 한다는 것이다.

 

하지만 위의 상황에서는 반복문을 돌면 돌수록 계속해서 최단 경로가 갱신되는 것을 볼 수 있다. 이런 경우 V번째 루프를 돌 때 갱신이 일어난다면 음수 싸이클이 존재한다고 결론을 내릴 수 있는 것이다.

시간 복잡도

시간 복잡도는 결론적으로 말하면 O(VE)가 된다.

 

모든 정점 V와 모든 간선 E를 검사하는 구조이기 때문에 시간 복잡도는 O(V) * O(E) = O(VE)가 되는 것이다.

코드

std::vector<std::pair<int, int> > varr[V];
long long dist[V];
bool minCycle = false;

void bellman_ford(int S)
{
	dist[S] = 0; // 시작점 초기화
	for (int i = 0; i < V; i++)
	{
		for (int here = 0; here < V; here++)
		{
			for (auto& it : varr[here])
			{
				int there = it.first;
				int nCost = it.second;
				if (dist[here] != INF && dist[there] > dist[here] + nCost)
				{
					dist[there] = dist[here] + nCost;
					if (i == V - 1)
						minCycle = true;
				}
			}
		}
	}
}

주의할 점

위의 코드의 dist배열의 자료형을 주의 깊게 봐야한다.

 

4바이트 정수 자료형인 int로 선언하게 될 경우 정점의 개수에 따라 오버플로우가 발생할 수도 있다. 위의 코드를 살펴보도록 하자.

 

커다란 반복문 안에서 한 번 반복문을 돌 때마다 dist[S]의 값은 -C·V 만큼 증가하게 된다. 즉, 커다란 반복문을 전부 다 돌게 되었을 경우 dist[S]의 값은 -C·(V^2)만큼 값이 커진다는 것이다.

 

이렇게 될 경우 4바이트 정수 만으로는 전부 다 담을 수 없게 된다. 그렇기에 8바이트 정수 자료형으로 선언해줘야 하는 이유다.