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)

- Single-Pair : one to one

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

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

- All-Pairs : all to all

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

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

최단 경로의 기본 특성

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

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