티스토리 뷰

알고리즘

BellmanFord(벨만포드) 알고리즘

llilliiillliill 2017. 12. 21. 17:43

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


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);
}
}


- Single-Pair : one to one

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

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


- All-Pairs : all to all

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

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


최단 경로의 기본 특성

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

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

댓글