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

☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로를 구해도 될까? -> 정당성에 성립되지 않습니다. 

 

따라서 음수 간선이 존재하고 음수 사이클이 존재한다는 것을 확인하고 싶을 때 Bellman-Ford Algorithm을 사용해야합니다. 

 

☞ 벨만-포드 알고리즘이란 무엇일까?

 

벨만포드 알고리즘 원리는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식입니다.  여기서 상한은 upper 배열에 저장하며 이 upper의 값은 알고리즘이 진행됨에 따라 점점 줄어들고 알고리즘이 종료되면 실제 최단 거리를 담게 되는 원리입니다.

 

☞ 벨만-포드 알고리즘 동작 과정

 

우리는 시작점에서 시작점까지의 최단 거리는 0임을 알기 때문에, upper[s]=0 으로 초기화하고 나머지는 ∞로 초기화해주며 최단 거리의 특성을 이용해 계속 upper 배열을 갱신해준다. 

최단 거리 특성

따라서 upper[v]를 upper[u]+w(u,v)로 감소하는 과정을 완화(relax)라고 부른다.

 

☞ 자 이 과정을 몇번 반복해야 최단거리를 찾을 수 있을까?

 

모든 간선에 대해 완화를 시도하는 작업을 x번 반복하면 x개 이하의 간선을 사용하는 최단 경로들을 찾을 수 있다.

여기서, 만약 그래프에 음수 사이클이 없다면 최단 경로가 한 정점을 두 번 지나는 일은 없기 때문에 이 경로는 V개의 정점을 갖게 되며 이 때의 간선의 개수는 V-1개이므로, V-1번 작업을 반복하며 V개를 지나는 최단 경로를 구할 수 있다.

 

☞ 만약 그래프에 음수 사이클이 존재하면?

 

벨만-포드 알고리즘은 그래프에 음수 사이클이 존재할시, 존재한다는 오류를 반환할 수 있습니다.

음수 사이클의 존재여부 판정은 V-1번 모든 간선에 대해 완화를 시도하는 대신 V번 완화를 시도하면 됩니다. 

 

음수 사이클일시 완화 과정을 돌린 값들을 더하면 0<=-1 이라는 모순된 값이 나오는 것을 알 수 있습니다. 

 

벨만-포드 알고리즘 (C++)

//정점의 개수
int V;

//인접배열로 표현한 그래프
vector<pair<int, int>> adj[MAX_V];

vector<int> bellmanFord(int src) {
	vector<int> upper(V, INF); //upper배열과 시작점을 제외한 모든 정점은 최대 상한으로 초기화
	upper[src] = 0; //시작점은 0으로 초기화
	bool updated; 

	for (int iter = 0; iter < V; ++iter) {
		updated = false;
		for(int here = 0; here < V; ++here)
			for (int i = 0; i < adj[here].size(); ++i) {
				int there = adj[here][i].first;
				int cost = adj[here][i].second;
				//완화(Relax) 과정
				if (upper[there] > upper[here] + cost) {
					upper[there] = upper[here] + cost;
					updated = true;
				}
			}
		//모든 간선에 대해 완화가 실패했을 경우 V-1번 돌 필요 없이 종료
		if (!updated) break;
	}
	//만약 V번째에도 완화(Relax)가 성공했다면 음수 사이클이 있다. -> upper배열을 클리어해준다.
	if (updated) upper.clear();
	return upper;
}