벨만 포드 정리 C++

벨만 포드 알고리즘은 음수인 가중치를 갖는 엣지가 있을 때 한 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘입니다.

 

다익스트라와의 차이는 음수 가중치 유무인데, 다익스트라 알고리즘을 동일하게 적용 시, 가장 짧은 거리를 갖는 노드 선택으로 인해 제대로 계산이 되지 않습니다.

 

따라서 음수 가중치가 존재하는 경우, 벨만 포드 알고리즘을 사용하면 되며, 전체 복잡도는 O(VE) 입니다.

 

벨만 포드 알고리즘은 모든 edge를 대상으로 노드 수만큼 지속적으로 업데이트를 합니다. 

즉, dist[to] > dist[from] + arr[from][to] 인 경우 업데이트를 합니다. (dist : 시작 노드로부터 각 노드까지 거리)

 

단, 음수 사이클이 존재할 수도 있으므로, 이러한 경우를 판단해주어야 합니다.

loop를 노드 수만큼 돌릴 때까지도 지속적으로 업데이트되는 경우, 음수 사이클이 존재하는 경우입니다.

 

따라서 코드는 다음과 같습니다.

#include <iostream>
#include <vector>

using namespace std;

#define INF 987654321

int bellman_ford(vector<pair<pair<int, int>, int>> &edges, int dist[], int startNode, int nodeNum)
{
	// 음수 사이클 시 -1, 아니면 0 리턴
	 
	// 초기값 갱신 
	dist[startNode] = 0;
	
	// 모든 노드 수만큼 모든 엣지에 대해 업데이트 체크 
	for(int i = 0; i < nodeNum; i++) {
		for(auto e : edges) {
			// from -> to dist = d
			int from = e.first.first;
			int to = e.first.second;
			int d = e.second;
			
			// start -> from 가는 경로 없음 
			if(dist[from] == INF)
				continue;
			
			// start -> to > (start -> from, from -> to) 인 경우 업데이트 
			if(dist[to] > dist[from] + d) {
				dist[to] = dist[from] + d;
				
				// 전체 노드 수만큼 loop에도 업데이트되는 경우 = 음수 사이클 존재 
				if(i == (nodeNum - 1))
					return -1; 
			} 
		}
	}
	
	return 0;
}

int main()
{
	int nodeNum = 6;
	int graph[6][6] = {
		{0,   3,     2,  -2, INF, INF},
		{INF, 0,   INF, INF,   5, INF},
		{INF, 1,     0,  -6,  -3,   1},
		{INF, INF, INF,   0, INF,   2},
		{INF, INF, INF, INF,   0,   4},
		{INF, INF, INF, INF, INF,   0}
	};
	
	vector<pair<pair<int, int>, int>> edges;
	for(int i = 0; i < nodeNum; i++) {
		for(int j = 0; j < nodeNum; j++) {
			if(i != j && graph[i][j] != INF) {
				edges.push_back({{i, j}, graph[i][j]});
			}
		}
	}
	
	for(int startNode = 0; startNode < nodeNum; startNode++) {
		int *dist = new int[nodeNum];
		for(int i = 0; i < nodeNum; i++) {
			dist[i] = INF;
		}
		
		int res = bellman_ford(edges, dist, startNode, nodeNum);
		
		if(res == -1) {
			cout << "negative cycle exist!";
            		break;
		}
		else {
			cout << "start node " << startNode << " : ";
			for(int i = 0; i < nodeNum; i++) {
				if(dist[i] == INF)
					cout << "." << " ";
				else 
					cout << dist[i] << " ";
			}
			cout << "\n";
		}
		
		delete[] dist;
	}
}

 

아래는 음수 사이클인 경우의 예시입니다.