벨만-포드 알고리즘

# 벨만-포드 최단 경로 알고리즘

다익스트라 알고리즘과 같은 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며 그래프에 음수 사이클이 있어 최단거리가 제대로 정의되지 않은 경우도 찾을 수 있다.

수행 과정에서 각 정점까지의 최단 거리 상한을 담은 배열 upper[]를 유지한다. 이 값은 알고리즘이 진행됨에 따라 점점 감소하고, 최종적으로 각 정점까지의 최단거리를 담게 된다.

# 동작 과정

알고리즘이 시작할 때 알 수 있는 사실은 시작점 -> 시작점까지의 최단거리가 0이라는 것 뿐이다. 따라서 upper[s] = 0 으로 초기화하고, 나머지 원소들은 아주 큰 수(무한으로 상정되는) 로 초기화 한다.

이 예측 값을 실제 최단 거리에 더 가깝게 갱신하기 위해 아래와 같은 최단 거리의 특성을 이용한다. 

dist[v] <= dist[u] + w(u,v)

시작점 s에서 v까지 가는 최단거리는, s에서 u까지 가는 최단거리에 u->v 가중치를 더한 값보다 클 수 없다는 의미이다. 만약 전자가 더 크다면 그보다 작은 값이 있다는 것이기에 최단거리가 될 수없으므로 모순이다. 

# 종료 조건과 정당성 증명

S -> a -> b -> c -> u 라는 최단거리가 있다고 가정하자. upper[]가 실제 최단 거리와 같음이 보장된 정점은 대문자로 표시했다.
이제 모든 간선을 순회하면서 한 번식 완화를 시도하면 s -> a에 대한 '완화'도 이루어진다. 따라서

upper[a] <= upper[s] + w(s, a)가 항상 성립한다.

여기서 upper[s]는 0이므로 

upper[a] <= w(s, a) 가 된다.

w(s, a)는 s -> a 에서의 최단거리여야 한다. 이보다 짧은 경로가 있다면 애초에 S -> a -> b -> c -> u가 최단경로라는 사실이 거짓이 되기 때문이다. 따라서 upper[a] = w(s, a) 이며 이로써 s -> a의 최단 거리를 찾았음을 알 수 있다.

이 과정을 모든 간선에 대해 한번씩 반복하면 최종적으로 upper[u] = dist[u]가 됨을 알 수 있다. 이를 일반화하면 모든 간선에 대해 완화를 시도하는 작업을 x번 반복하면 x개 이하의 간선을 사용하는 최단 경로들은 전부 찾을 수 있다는 말이 된다. 따라서 모든 간선이 전부 완화가 실패할 때까지 반복하면 모든 최단 경로를 찾을 수 있다.

음수 사이클이 없는 경우 최단 경로가 한 정점을 두 번 지나는 일이 없으므로, 최대 V개의 정점이 있을 경우 V-1개의 간선을 가질 수 있다. 따라서 모든 간선에 대한 완화 과정은 V-1번 반복하면 된다.

# 음수 사이클

음수 사이클의 존재를 알려면 결과적으로 모든 간선에 대한 완화 과정을 V-1 이 아닌 V번 반복하면 된다. 그래프에 음수 사이클이 없다면 V-1째 반복까지 모든 최단거리를 찾아낼 수 있으므로 마지막 V번째 바놉ㄱ에서는 완화과정이 한번도 발생하지 않아야 한다. 하지만 음수 사이클이 있다면 V번째 반복에서도 최소 한 번은 성공하므로 이것을 이용하면 된다.

예를 들어 s -> a -> b -> s 라는 전체 가중치가 -1인 음수 사이클이 있다. 이 때 세 번 완화한 후 완화가 전부 실패한다고 가정해보자 (최단거리를 전부 찾았다고 가정). 그렇다면 아래와 같은 세 개의 부등식이 성립할 것이다.

upper[a] <= upper[s] + 10

upper[b] <= upper[a] -21

upper[s] <= upper[b] + 10

부등식들의 좌변과 우변을 각각 더하면 아래와 같다.

upper[a] + upper[b] + upper[s] <= upper[s] + upper[a] + upper[b] - 1

중복된 항을 지우면 0 <= -1 이므로 모순임을 알 수 있다.
따라서 V번째 반복에서 음수사이클은 항상 완화가 최소 1번 이상 성공한다.

# Template

알고리즘의 기본적인 구현은 아래와 같다.

package swcertificate;

import java.util.ArrayList;
import java.util.List;

public class Interstellar2 {
	
	public static class Pair{
		
		public int linkedNode;
		public int weight;
		public Pair(int linkedNode, int weight) {
			this.linkedNode = linkedNode;
			this.weight = weight;
		}
		
	}
	
	// 정점의 수
	public static int V;	
	// 각 정점에서의 간선 리스트
	public static List<Pair>[] adj;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		for(int i=0; i<V; i++){
			// 각 정점에 연결된 간선을 전부 add한다.
			adj[i] = new ArrayList<Pair>();
			int n = 2;	// 연결딘 노드
			int w = 10;	// 가중치
			Pair pair = new Pair(n, w);
			
			//TODO 각 노드에 간선들 추가
			
		}
		
		List<Integer> result = bellmanFord(0);
		

	}
	
	public static List<Integer> bellmanFord(int src){
		
		// 시작점을 제외한 모든 정점가지의 최단 거리 상한을 INF로 둔다.
		List<Integer> upper = new ArrayList<Integer>();
		for(int i=0; i<V; i++){
			upper.add(Integer.MAX_VALUE);
		}
		upper.set(src, 0);
		boolean updated = false;
		
		// V번 순회한다.
		for(int i=0; i<V; i++){
			updated = false;
			for(int here=0; here<V; here++){
				for(int j=0; j<adj[here].size(); j++){
					int there = adj[here].get(j).linkedNode;
					int cost = adj[here].get(j).weight;
					
					// (here, there) 간선을 따라 완화를 시도한다.
					if(upper.get(there) > upper.get(here) + cost){
						// 성공
						upper.set(there, upper.get(here) + cost);
						updated = true;
					}
				}
				
				// 모든 간선에 대해 완화가 실패했을 경우 V-1번도 돌 필요 없이 곧장 종료.
				if(!updated) break;
			}
			
			
		}
		
		// V번째 순회에서도 완화가 성공했다면 음수 사이클이 있다.
		if(updated) upper.clear();
		return upper;
		
	}

}

각 반복마다 모든 간선을 순회하므로 O(|E|)수행되고, 전체적으로 V번 반복되므로 전체 시간복잡도는 O(|V||E|) 이다.

# 실제 경로 계산

각 정점을 마지막으로 완화시킨 간선들을 모드면 스패닝 트리를 얻을 수 있다. 각 정점에서부터 스패닝 트리의 루트인 시작점까지 거슬러 올라가는 경로는 항상 시작점에서 해당 경로까지의 최단 경로이다.

# 빠지기 쉬운 함정

s -> u 까지 경로의 존재 자체를 확인하고 싶다면, 알고리즘 종료 후 upper[u] 가 초기값(무한)만 아니면 경로가 존재한다고 판단하는 오류를 범하기 쉽다. 이는 음수 가중치가 있을 수 있다는 사실을 간과했기 때문이다.

따라서 u로 가는 경로가 존재하는지 확인하려면 적당히 큰 값 M에 대해 upper[u] < INF - M 임을 확인해야 한다.

* 알고리즘 문제해결 전략 Vol2 기반으로 작성됨