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

 최단 경로를 구하는 두번째 알고리즘 벨만 포드 알고리즘이다. 이 알고리즘은 다익스트라와 마찬가지로 하나의 시작점에서 다른 정점들간의 최소 시간을 구하는 알고리즘이다. 최악 시간 복잡도는 O(|V||E|)이다. 여기서 |V|는 정점의 개수, |E|는 간선의 개수이다. 다익스트라는 최악 시간 복잡도가 O(|E| + |V| log|V|) 인데 이 알고리즘을 사용하는 이유는 음수 가중치에 대해서도 적용할 수 있기 때문이다. 또한 음수 사이클의 존재 유무까지 판단할 수 있다.

 

 이 알고리즘은 다익스트라와 같이 BFS 기반의 연산을 하는 것이 아닌 플로이드 워셜 알고리즘같이 다중 반복을 통해 문제를 해결한다. 그래서 우선순위 큐를 사용하지 않는다.

 이 알고리즘은 초기에 start의 dist가 0이라는 것 빼고 모든 정점간의 시간을 INFINITY로 놓고 시작한다. 그 다음 |V|번 동안 모든 간선에 대해서 완화를 시작한다. |V|번의 완화 이후에는 시작점으로부터 모든 정점간의 최소 시간이 나오게 된다. 이 때 |V|번 이후에도 완화가 가능하다면 음수 사이클이 존재한다는 의미가 된다.

 아이디어는 상당히 간단하지만, 구현에 있어서는 문제가 있다. C++로 구현한 코드는 다음과 같다.

#define INF INT64_MAX / 2

int n;
vector<vector<pair<int, int>>> edges;

vector<long long> bellman_ford(int start)
{
	vector<long long> dist(n + 1, INF);
	dist[start] = 0;

	// 정점 개수만큼 반복
	for (int vertex = 1; vertex <= n; vertex++)
	{
		// 모든 간선에 대해서 수행
		for (int present = 1; present <= n; present++)
		{
			for (int i = 0; i < edges[present].size(); i++)
			{
				int next = edges[present][i].first;
				int cost = edges[present][i].second;

				if (dist[present] == INF)
				{
					continue;
				}

				if (dist[next] > dist[present] + cost)
				{
					dist[next] = dist[present] + cost;
				}
			}
		}
	}

	// 음수 사이클 판정
	for (int present = 1; present <= n; present++)
	{
		for (int i = 0; i < edges[present].size(); i++)
		{
			int next = edges[present][i].first;
			int cost = edges[present][i].second;

			if (dist[present] == INF)
			{
				continue;
			}

			if (dist[next] > dist[present] + cost)
			{
				return vector<long long>();
			}
		}
	}

	return dist;
}

 22번과 43번에 INFINITY인지 확인하는 if문이 꼭 있어야 하는데, 이는 음수 가중치가 가능하기 때문이다. INF를 10억으로 가정하고, dist[next]와 dist[present]가 INF이고 cost가 -100이라고 가정하면, 개념상으로는 dist[present]가 INF라는 것은 present로 가는 길이 없다는 의미인데, 여기서 cost가 -100이기 때문에 100이 빠져 27번, 48번 줄 if문이 성립하게 되고, 10억 - 100이 dist[next]에 들어가게 되어 엉뚱한 답을 내놓게 된다. 그렇기 때문에 그 전에 dist[present]가 INF라면 무시해야한다. 

 음수 사이클 판정에서 완화가 또 가능하다면 음수 사이클이 있다는 것이므로, 빈 벡터를 리턴하는 방식으로 구현하였다.

 

 

 

참고

- 알고리즘 문제 해결 전략(구종만 저)

- https://ko.wikipedia.org/wiki/%EB%B2%A8%EB%A8%BC-%ED%8F%AC%EB%93%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98