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

벨만포드 알고리즘(Bellman-Ford Algorithm)은 한 정점으로부터 다른 정점까지 최단경로를 계산하는 알고리즘입니다.

다익스트라 알고리즘과 다른 점은, 벨만포드 알고리즘은 음수 간선이 있어도 정상적으로 동작한다는 겁니다. 또한 음수사이클이 존재 여부도 알 수 있습니다.

장점만 있지는 않는데요, 다익스트라 알고리즘의 시간복잡도는 O(ElogV)인데, 벨만포드 알고리즘은 O(VE)로 더 오래 걸립니다.

 

벨만포드 알고리즘은 수행 과정에서 각 정점까지 최단거리의 상한값을 담은 배열 upper[]를 유지합니다. 이 값은 알고리즘이 진행되면서 점점 줄어들고, 알고리즘이 종료할 때는 실제 최단 거리가 담기게 됩니다.

 

\[dist[v] \leq dist[u] + w(u,v) \]

벨만포드 알고리즘은 최단거리의 특성을 이용합니다. 위 속성을 이용하면 \(upper[u]+w(u, v)<upper[v]\)일 때 upper[v]를 upper[u]+w(u, v)로 줄일 수 있습니다. 이 과정을 완화(relax)한다고 합니다.

 

최단 경로는 최대 V개의 정점을 가지므로 최대 V-1개의 간선을 가질 수 있고, 따라서 모든 간선에 대한 완화 과정을 V-1번 하면 최단거리를 계산할 수 있습니다.

음수사이클 존재 여부를 판정하려면 V-1번 대신 V번 완화를 시도하면 됩니다. 음수사이클이 없다면 V-1번의 반복만으로 모든 최단거리를 찾을 수 있어 마지막 반복의 완화는 전부 실패합니다. 하지만 음수사이클이 있다면 V번째 반복에서도 항상 완화가 한 번은 성공합니다.

 

int V;
vector<pair<int, int>> adj[MAX_V];	// idx, cost

// 음수 사이클이 있을 경우 텅 빈 배열 반환
vector<int> bellmanFord(int src) {
	vector<int> upper(V, INF);
	upper[src] = 0;
	bool updated = false;

	// V번 순회
	for (int iter = 0; iter < V; ++iter) {
		updated = false;

		for (int here = 0; here < V; ++here) {
			for (auto& edge : adj[here]) {
				int there = edge.first;
				int cost = edge.second;

				// 완화 시도
				if (upper[there] > upper[here] + cost) {
					upper[there] = upper[here] + cost;
					updated = true;
				}
			}
		}

		if (!updated) break;
	}

	//V번째 순회에서도 완화가 성공 --> 음수사이클
	if (updated)
		upper.clear();

	return upper;
}

음수사이클의 존재 여부 확인을 포함하는 벨만 포드 알고리즘 구현입니다. V번 완화를 반복하고, 마지막 반복에서 완화가 성공했을 경우 텅 빈 배열을 반환합니다.