Bellman-Ford 알고리즘 - 이론적 배경, 코드 구현, 시간 복잡도

목차 (눌러서 이동)

https://en.wikipedia.org/wiki/Bellman–Ford_algorithm 

Bellman–Ford algorithm - Wikipedia

 

 

Bellman-Ford Algorithm

Richard Bellman 과 Lester Ford Jr. 에 의해 출간되었다. 

 

방향 그래프에서 Single Source Shortest Path 문제를 해결하는 대표적 알고리즘 중 하나로, 하나의 vertex 에서 출발하여 다른 vertices 로의 최단 경로들을 구한다. 단방향, 양방향 그래프 모두에서 사용할 수 있다.

 

Dijkstra 알고리즘보다 느리지만 음의 가중치를 가지는 그래프에도 적용할 수 있다. 단, 음의 순환을 가진다면 최단 경로는 알 수 없고 음의 순환의 존재 여부를 파악할 수 있다. 

 

음의 순환이란 간선의 합이 음수인 순환 경로로, 음의 순환을 지날 때마다 경로 비용이 낮아져 최소 비용의 경로가 존재하지 않는다.

이론적 배경

최적 부분 구조 (Optimal Substructure)

최단 거리를 구하는 문제에서 중요한 속성이다. 최단 경로의 부분 경로 역시 최단 경로라는 속성인데

 

쉽게 말해 서울에서 대구를 거쳐 부산에 가는 최단 경로를 구했다면, 서울에서 대구까지의 경로 역시 최단 경로라는 의미이다.

 

식으로 표현해 보면 D(src, dst) = src 에서 dst 까지의 최단 거리일 때, 그 중간에 지나는 mid 에 대해서 다음의 식이 성립한다. D(src, dst) = D(src, mid) + D(mid, dst). 아래의 Edge Relaxation 에서 위 식을 이용해 보자.

간선 가중치 합 경감 (Edge Relaxation)

최단 경로를 구하는 알고리즘은 Edge Relaxation 을 기본 연산으로 한다. D(src, dst) 에 대해 어떤 값을 최소로 알고 있었는데 중간에 어떤 새로운 지점을 지나서 갔더니 그 값이 더 작다면

 

즉, D(src, dst) > D(src, mid) + D(mid, dst) 라면 D(src, dst) = D(src, mid) + D(mid, dst) 로 갱신하면 된다. 

구현 방법

주어진 정점 집합 V 와 간선 집합 E 에 대해서 E 의 모든 간선에 대한 edge relaxation 을 |V| - 1 번 반복하면 출발 정점으로부터 나머지 정점으로의 최단 경로를 기록할 수 있다. 

시간 복잡도

정점 집합 V 와 간선 집합 E 가 주어질 때, E 의 모든 간선에 대한 edge relaxation 을 |V| - 1 번 반복하므로 O(|V|*|E|) 의 시간 복잡도를 가진다.

 

정점 간의 가능한 모든 간선이 존재하는 밀집 그래프의 경우 간선의 수가 정점 수의 제곱에 근사하므로 O(|V|^3) 의 시간 복잡도를 가진다. 

C++ 코드

다음과 같이 edge list 가 주어진다. ({2,5,2} 는 2번 정점에서 5번 정점으로 가는데 2의 가중치가 든다는 뜻.)

 

	int n = 5; // Number of vertices
	int s = 1; // Start edge

	// Weights of edges
	vector<vector<int>> edges = {
		{2,5,2}, 
		{4,2,1}, 
		{2,4,2}, 
		{1,2,-1}, 
		{1,3,4}, 
		{4,3,5}, 
		{2,3,3}, 
		{5,4,-3} 
	};

 

 

이제 거리를 저장할 배열을 선언하고 출발점을 제외한 모든 vertex 까지의 도달 비용은 Infinite 로 초기화한다. (1번 부터 시작하는 정점 번호와 인덱스를 맞추기 위해 n+1 개의 배열을 사용했다.) 

 

출발 정점인 s 의 거리를 0 으로 저장한 뒤 본격적인 알고리즘을 시작한다.

 

vector<int> BellmanFord(int n, int s, vector<vector<int>>& edges) {
	// n + 1 to match the index
	vector<int> dist(n + 1, 0);
	for (int i = 1; i <= n; ++i) dist[i] = INF;
	dist[s] = 0;
	...

 

주어진 모든 edge 에 대해 relaxation 을 수행한다. edge relaxation 은 위의 이론에서 설명한 바와 같다. edge list 의 순서는 무작위이기 때문에 처음에는 edge relaxation 으로 갱신되지 않는 거리가 있다.

 

첫 edge 정보를 아래의 과정에 대입하면 dist[5] = min(dist[5], dist[2] + 2) 인데, dist[5] = dist[2] = Infinite 이므로 갱신되지 않고 Infinite 로 남는다.

 

이 때문에 출발지를 제외한 vertex 개수만큼 전체 edge relaxation 을 반복한다. 최소 |V| - 1 번의 edge relaxation 을 반복했을 때, 모든 거리가 최단 경로로 갱신된다.

 

	for (int i = 0; i < n - 1; ++i) {
		for (auto& e: edges) {
			vector<int> v = e;
			int s = v[0], d = v[1], w = v[2];
			dist[d] = min(dist[d], dist[s] + w);
		}
	}

 

위의 알고리즘 소개에서 음의 순환을 발견할 수 있다고 설명했는데 그 의미를 설명하자면, 음의 순환이 없는 그래프에서는

위의 과정까지 완료된 경우 dist 배열에 각 정점으로의 최단 거리가 기록된다.

 

그런데, 음의 순환이 있다면 edge relaxation 을 한 번 더 수행할 때 최단 거리가 더 줄어드는 구간이 생긴다. 사실, 음의 순환은 반복할 수록 음의 무한대로 줄어드므로 최단 거리가 존재하지 않는다.

 

따라서, edge relaxation 을 마지막 한 번 수행해 갱신되는 구간이 생기면 음의 순환이 있는 것으로 보고한다.

 

	for (auto& e: edges) {
		vector<int> v = e;
		int s = v[0], d = v[1], w = v[2];
		if (dist[s] + w < dist[d]) {
			cout << "Negative cycle detected" << '\n'; 
			break;
		}
	}

 

전체적인 코드는 다음과 같다.