벨만-포드 알고리즘
위키백과 ― 우리 모두의 백과사전.
 |
이 문서는 en:Bellman-Ford algorithm에서 한국어로 번역 중입니다. 원문은 글 안에 주석 처리되어 있습니다. 같이 번역해 주세요. |
벨만-포드 알고리즘(Bellman-Ford algorithm)은 가중 방향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 간선의 가중치는 음수일 수도 있다. 데이크스트라 알고리즘은 벨만-포드 알고리즘과 동일한 작업을 수행하고 실행속도도 더 빠르다. 하지만 데이크스트라 알고리즘은 가중치가 음수인 경우는 처리할 수 없으므로, 이런 경우에는 벨만-포드 알고리즘을 사용한다.
V와 E가 각각 그래프에서 꼭지점과 모서리의 개수라고 한다면, 벨만-포드 알고리즘의 실행시간은 O(VE)이다.
// 그래프의 자료구조 정의
record vertex {
list edges
real distance
vertex predecessor
}
record edge {
node source
node destination
real weight
}
function BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices
// and edges, and modifies the vertices so that their distance and
// predecessor attributes store the shortest paths.
// Step 1: 그래프 초기화
for each vertex v in vertices:
if v is source then v.distance = 0
else v.distance := infinity
v.predecessor := null
// Step 2: 이완 작업 반복
for i from 1 to size(vertices):
for each edge uv in edges:
u := uv.source
v := uv.destination // uv is the edge from u to v
if v.distance > u.distance + uv.weight
v.distance := u.distance + uv.weight
v.predecessor := u
// Step 3: 음의 가중치를 갖는 사이클 찾기
for each edge uv in edges:
u := uv.source
v := uv.destination
if v.distance > u.distance + uv.weight
error "Graph contains a negative-weight cycle"
목차 |
[편집] 알고리즘 증명
[편집] 응용: 라우팅
[편집] 구현
[편집] C
#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
int source;
int dest;
int weight;
}Edge;
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
{
int i,j ;
int* distance = (int*) malloc(nodecount*sizeof(int));
for(i = 0; i < nodecount; i++)
{
if(i == source) distance[i] = 0;
else distance[i] = INFINITY;
}
for(i = 0; i < nodecount; i++)
{
for(j = 0; j < edgecount; j++)
{
/*
* Note that INFINITY is actually a finite number in this code, so because of overflow
* "distance[edges[j].source] + edges[j].weight" can be a very small number,
* in fact smaller than "distance[edges[j].dest]".
*
* One solution is to skip the following if-statement,
* if "distance[edges[j].source]" == INFINITY
*/
if(distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight)
{
distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
}
}
}
for(i = 0; i < edgecount; i++)
{
if(distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight)
{
printf("Error occurred. Negative edge weight cycles detected");
break;
}
}
for(i = 0; i < nodecount; i++)
{
printf("The shortest distance between nodes %i and %i is %i\n", source, i, distance[i]);
}
}
[편집] 참고문헌
- Richard Bellman: On a Routing Problem, in Quarterly of Applied Mathematics, 16(1), pp.87-90, 1958.
- Lestor R. Ford jr., D. R. Fulkerson: Flows in Networks, Princeton University Press, 1962.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 24.1: The Bellman-Ford algorithm, pp.588–592.
