BellmanFord(벨만포드) 알고리즘

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

Shortest Path(최단 경로)

최단 경로 문제란 가장 짧은 경로에서 두 꼭지점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치의 합이 최소가 되도록 하는 경로를 찾는 문제이다.

예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.

보통은 주어진 가중 그래프에서 (V는 꼭지점, E는 변, 가중치 함수 f : E → R)

가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다.

출처 : 위키백과

최단 경로 문제의 유형

- Single-Source : one to all

하나의 출발노드 S로부터 다른 모든 노드까지의 최단 경로를 찾아라.

예 : Dijkstra의 알고리즘

- Single-destination : 

모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라.

Single-Source 문제와 동일

문제 예 :

- 입력 : 음수 사이클이 없는 가중치 방향 그래프 G=(V, E)와 출발노드 s ∈ V

- 목적 : 각 노드 v ∈ V에 대해서 다음을 계산한다.

d[v] : distance estimate

- 처음에는 d[s] = 0, d[v] = ∞ 로 시작한다.

- 알고리즘이 진행됨에 따라서 감소해간다. 하지만 항상 d[v] >= ∂(s, v)를 유지한다.

- 최종적으로 d[v] = ∂(s, v)가 된다.

- 그런 노드가 없는 경우 π[v] = NIL

π[v] : s에서 v까지의 최단 경로 상에서 v의 직전노드(predecessor)

- 기본 연산 : Relaxation

RELAX(u, v, w){
	if d[v] > d[u] + w(u, v)
		then d[v] <- d[u] + w(u, v)
			π[v] <- u
}

- 대부분의 Single-Source 최단 경로 알고리즘의 기본 구조

1) 초기화 : d[s]=0, 노드 v != s에 대해서 d[v] = ∞, π[v] = NIL

2) 에지들에 대한 반복적인 Relaxation

- 알고리즘들 간의 차이는 어떤 에지에 대해서, 어떤 순서로 Relaxtion을 하느냐에 있음

- 기본 알고리즘

Generic-Single-Source(G, w, s){
	INITIALISE-SINGLE-SOURCE(G, s)
		repeat
			for each edge(u, v) ∈ E
				RELAX(u, v, w)
		until there is no change
}

- Bellman-Ford 알고리즘 의사코드

BELLMAN-FORD(G, w, s){
	INITIALIZE-SINGLE-SOURCE(G, s)
	for i <- 1 to |V[G]|-1
		do for each edge(u, v) ∈ E[G]
			do RELAX(u, v, w)
	for each edge(u, v) ∈ E[G]
		do if d[v] > d[u] + w(u, v)
			then return FALSE
	return TRUE
}

시간복잡도 : O(nm)

예제를 통해 구현 소스 코드(Java)

	package Sort;
	// 벨만포드의 최단 경로 알고리즘 구현
	// 연결되고, 가중치가 있는 그래프를 나타내느 클래스
	public class BellmanFordGraph {
	// 그래프의 가중치를 나타내는 클래스
	class Edge{
	int src, dest, weight;
	Edge(){
	src = dest = weight = 0;
	}
	};
	int V, E;
	Edge edge[];
	// V, E가 있는 그래프 생성
	BellmanFordGraph(int v, int e) {
	// TODO Auto-generated constructor stub
	V = v;
	E = e;
	edge = new Edge[e];
	for(int i=0; i<e; ++i) {
	edge[i] = new Edge();
	}
	}
	// 벨만포드 알고리즘을 이용하여 src에서 다른 정점들까지의 최단거리를 찾는 메인 기능
	// 음의 무게 주기 감지
	void BellmanFord(BellmanFordGraph graph, int src) {
	int V = graph.V, E = graph.E;
	int dist[] = new int[V];
	// 1단계 : src에서 다른 정점으로 모든 정점 초기화
	for(int i=0; i<V; ++i) {
	dist[i] = Integer.MAX_VALUE;
	}
	dist[src] = 0;
	// 2단계 : 모든 edge|V|-1회,
	// src에서 다른 정점들까지의 간단한 최단경로는 |V|-1 선을 가질 수 있다.
	for(int i=1; i<V; ++i) {
	for(int j=0; j<E; ++j) {
	int u = graph.edge[j].src;
	int v = graph.edge[j].dest;
	int weight = graph.edge[j].weight;
	if(dist[u] != Integer.MAX_VALUE && dist[u]+weight< dist[v]) {
	dist[v] = dist[u]+weight;
	}
	}
	}
	// 3단계 : 비 가중치 사이클 점검
	// 만약 더 짧은 길을 가진다면 순환이 이루어진다
	for(int j=0; j<E; ++j) {
	int u = graph.edge[j].src;
	int v = graph.edge[j].dest;
	int weight = graph.edge[j].weight;
	if(dist[u] != Integer.MAX_VALUE && dist[u]+weight < dist[v]) {
	System.out.println("Bellman-Ford Graph contains negative weight cycle");
	}
	}
	printArr(dist, V);
	}
	// 배열 출력
	void printArr(int dist[], int V) {
	System.out.println("Vertex Distance from Source");
	for(int i=0; i<V; ++i) {
	System.out.println(i+"\t\t"+dist[i]);
	}
	}
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	int V = 5; // 그래프의 점의 수
	int E = 8; // 그래프의 선의 수
	BellmanFordGraph graph = new BellmanFordGraph(V, E);
	// add edge 0-1
	graph.edge[0].src = 0;
	graph.edge[0].dest = 1;
	graph.edge[0].weight = -1;
	// add edge 0-2
	graph.edge[1].src = 0;
	graph.edge[1].dest = 2;
	graph.edge[1].weight = 4;
	// add edge 1-2
	graph.edge[2].src = 1;
	graph.edge[2].dest = 2;
	graph.edge[2].weight = 3;
	// add edge 1-3
	graph.edge[3].src = 1;
	graph.edge[3].dest = 3;
	graph.edge[3].weight = 2;
	// add edge 1-4
	graph.edge[4].src = 1;
	graph.edge[4].dest = 4;
	graph.edge[4].weight = 2;
	// add edge 3-2
	graph.edge[5].src = 3;
	graph.edge[5].dest = 2;
	graph.edge[5].weight = 5;
	// add edge 3-1
	graph.edge[6].src = 3;
	graph.edge[6].dest = 1;
	graph.edge[6].weight = 1;
	// add edge 4-3
	graph.edge[7].src = 4;
	graph.edge[7].dest = 3;
	graph.edge[7].weight = -3;
	graph.BellmanFord(graph, 0);
	}
	}

view raw BellmanFordGraph.java hosted with ❤ by GitHub

- Single-Pair : one to one

주어진 하나의 출발 노드 S로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라.

최악의 경우 시간복잡도에서 Single-Source 문제보다 나은 알고리즘이 없음

- All-Pairs : all to all

모든 노드 상에 대해서 최단 경로를 찾아라.

예 : Floyd의 알고리즘이 가장 유명하다.

최단 경로의 기본 특성

- 최단 경로의 어떤 부분 경로도 역시 최단 경로이다.

- 최단 경로는 사이클을 포함하지 않는다.(음수 사이클이 없다는 가정하에서)