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

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

벨만-포드 알고리즘은 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘으로 길이가 음수인 사이클을 포함하지 않는 모든 종류의 그래프를 처리할 수 있다. 
그래프에 음수 사이클이 있는 경우에는 이를 찾아낼 수도 있다.

이 알고리즘에서는 시작 노드에서 다른 모든 노드까지의 길이를 모두 추적한다.
거리의 초기값은 시작 노드의 경우 0이고 다른 모든 노드의 경우 무한대의 값으로 설정된다.
그리고 이 값을 계속해서 줄여나가는 과정을 더는 줄일 수 있는 값이 없을 때까지 반복한다. 

초기 시작	거리가 1인 노드 탐색
거리가 2인 노드 탐색	거리가 3인 노드 탐색

위와 같은 식으로 거리를 줄여나간다. 이후에 거리를 더 줄일 수 없게 되면 종료하게 된다.

 

구현

노드 x에서 다른 모든 노드로 가는 최단 경로를 구하는 코드이다. 그래프는 간선 리스트 edges에 (a, b, w)의 형식으로 저장되어 있다고 가정한다. distance [] 배열은 노드 x에서 각 노드로 향하는 거리를 저장하는 데 사용된다.

간선 리스트에 3개의 값을 저장해야 하므로 다음과 같은 class를 만들었다.

public class Triple{
	int a;
	int b;
	int c;
	public Triple(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}

	public int getA() {
		return a;
	}
	public void setA(int a) {
		this.a = a;
	}
	public int getB() {
		return b;
	}
	public void setB(int b) {
		this.b = b;
	}
	public int getC() {
		return c;
	}
	public void setC(int c) {
		this.c = c;
	}
	
}

 그리고 이 Triple을 이용하여 다음과 같이 구현할 수 있다.

import java.util.ArrayList;

import util.Triple;

public class BellmaFord {

	public static void main(String[] args) {
		//edge 생성
		ArrayList<util.Triple> edges = new ArrayList<util.Triple>();
		edges.add(new Triple(0, 1, 2));
		edges.add(new Triple(0, 2, 3));
		edges.add(new Triple(0, 3, 7));
		edges.add(new Triple(1, 3, 3));
		edges.add(new Triple(1, 4, 5));
		edges.add(new Triple(2, 3, 1));
		edges.add(new Triple(3, 4, 2));

		//distance배열 생성, 노드가 5개
		int distance[] = new int[5];
		
		//각 노드까지의 거리 무한대로 초기화
		for(int i = 0 ; i < 5 ; i++ ) {
			distance[i] = (int) Double.POSITIVE_INFINITY;
		}
		
		//시작 노드의 거리 0으로 설정 ( 1번 노드 )
		distance[0] = 0 ;
		
		//각 노드까지의 거리 계산
		for(int i = 1; i <= 4 ; i++) {
			for(Triple e : edges) {
				int a, b, w;
				a = e.getA();
				b = e.getB();
				w = e.getC();
				
				distance[b] = Math.min(distance[b], distance[a]+w);
			}
		}

		for(int i = 0 ; i < 5 ; i++ ) {
			System.out.println(i+"노드 거리: "+distance[i]);
		}
	}

}

 이 알고리즘은 n-1번(전체 노드의 수 - 1)의 라운드로 구성되어 있고, 라운드마다 m개의 간선을 모두 처리해야 한다. 
따라서 시간 복잡도는 O(nm)이다. 
음수 사이클이 존재하는 경우를 제외하면, n-1번의 라운드가 끝나면 모든 노드에 대한 최종 거리를 구할 수 있다. 각 노드까지의 간선이 최대 n-1개를 포함하기 때문이다.

이 알고리즘을 최적화하는 방법은 여러 가지가 있다. 그중 하나는 n-1번 진행하는데, 한 라운드를 진행하는 동안 거리가 줄어드는 경우가 없다면 알고리즘을 즉시 종료해도 된다.
다른 방법으로는 SPFA(Shortest Path Faster Algorithm)이 있는데 이 알고리즘은 거리를 줄이는 데 사용될 수 있는 노드를 별도의 큐로 관리하며, 그 노드만 처리함으로써 탐색 과정을 더 효율적으로 진행하는 방법이다.

음수 사이클이 존재하면, 최단 거리를 구하는 것은 의미가 없다. 벨만-포드 알고리즘을 n번 진행해 마지막 라운드에서도 거리가 줄어든다면 음수 사이클이 있다고 판단하면 된다.