벨만-포드(Bellman-Ford) 알고리즘은 동적 계획법(Dynamic Programming)에 기반한 최단 경로 알고리즘입니다. 시작 정점(출발점)으로 삼은 하나의 정점에서 출발하여, 그래프에 있는 모든 정점까지의 최단 거리를 반복적인 방식(iterative method)으로 점진적으로 찾아냅니다. 이 알고리즘은 가중치가 부여된 그래프(weighted graph)에 적용할 수 있습니다.
알고리즘의 역사
이 알고리즘은 1955년 알폰소 시멜(Alphonso Shimbel)에 의해 처음 제안되었습니다. 이후 리처드 벨만(Richard Bellman)과 레스터 포드(Lester Ford)가 1956년과 1958년에 걸쳐 개선 작업을 진행했으며, 이 덕분에 오늘날 벨만-포드 알고리즘이라는 이름으로 널리 알려지게 되었습니다. 또한 1957년에는 에드워드 F. 무어(Edward F. Moore)가 알고리즘을 다시 수정했기 때문에 벨만-포드-무어(Bellman-Ford-Moore) 알고리즘이라고 부르기도 합니다.
벨만-포드 알고리즘의 가장 큰 강점은 음수 가중치를 가진 간선도 처리할 수 있다는 점입니다. 다익스트라(Dijkstra) 알고리즘에 비해 실행 속도는 다소 느리지만, 더욱 다양한 유형의 그래프에 적용할 수 있어 실용적인 선택지가 됩니다.
알고리즘 개요
입력 : 가중치 그래프와 시작 정점(src) 출력 : 시작 정점으로부터 모든 정점까지의 최단 거리 음수 가중치 사이클이 존재하는 경우, 가중치를 계산할 수 없으므로 해당 사이클의 존재를 반환합니다.
알고리즘 수행 단계
1단계 : 초기화 단계입니다. 시작 정점으로부터 모든 정점까지의 거리를 저장할 배열 dist[]를 생성합니다. 배열의 크기는 그래프의 정점 개수와 같습니다.
2단계 : 각 정점의 최단 거리를 계산합니다. 3단계를 n-1번 반복 수행합니다 (n은 그래프의 정점 개수).
3단계 : 각 간선 i-j에 대해 다음을 수행합니다.
3.1단계 : dist[v] > dist[u] + weight[uv] 라면, dist[v] = dist[u] + weight[uv] 로 갱신합니다.
4단계 : 음수 사이클(negative cycle)이 존재하는지 검사하고 표시합니다. 만약 3.1단계가 여전히 실행된다면 음수 사이클이 존재하는 것입니다.음수 사이클(Negative Cycle): 일반적인 간선 순회보다 더 짧은 경로가 계속해서 발견되는 경우, 그래프 안에 음수 사이클이 존재한다고 판단할 수 있습니다.
예제로 이해하기
그래프 문제를 직접 풀어보면서 알고리즘의 동작 방식을 자세히 살펴보겠습니다.
위 그림에서 그래프를 구성하는 모든 정점과 간선, 그리고 각 간선에 부여된 가중치를 확인할 수 있습니다.
이제 벨만-포드 알고리즘을 사용하여 정점 A에서 정점 E까지의 최단 거리를 구해 보겠습니다.
먼저 시작 정점인 A의 거리를 0으로 설정하고, 나머지 정점들의 거리는 모두 무한대(∞)로 초기화합니다.
A B C D E 0 ∞ ∞ ∞ ∞
간선 A-B의 가중치를 확인한 뒤, 이어서 A-C를 확인합니다.
A-B로 가는 경로는 하나뿐이지만, A-C로 가는 경로는 두 가지가 존재하므로 어느 쪽이 더 짧은지 비교하게 됩니다.
A B C D E 0 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ - (A-B) 갱신 후 0 -2 3 ∞ ∞ - (A-C) 갱신 후
다음 정점들에 대해서도 같은 방식으로 시작 정점으로부터의 최단 거리를 계산합니다.
A B C D E 0 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ 0 -2 3 3 10
알고리즘을 통해 구한 최종 최단 거리는 10이며, 이는 A-B-E 경로를 따라 이동할 때 얻어지는 값입니다. 이 과정에서 그래프에 음수 사이클이 존재한다는 사실도 함께 확인할 수 있었습니다.
C++ 구현 예제
#include <bits/stdc++.h>
struct Edge {
int src, dest, weight;
};
struct Graph {
int V, E;
struct Edge* edge;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V;
graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void BellmanFord(struct Graph* graph, int src) {
int V = graph->V;
int E = graph->E;
int dist[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V - 1; 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] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return;
}
}
printf("Vertex : ");
for (int i = 0; i < V; ++i)
printf("%d ", i);
printf("
Distance From Source : ");
for (int i = 0; i < V; ++i)
printf("%d ",dist[i]);
return;
}
int main() {
int V = 5;
int E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = -1;
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 4;
graph->edge[2].src = 1;
graph->edge[2].dest = 2;
graph->edge[2].weight = 3;
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 2;
graph->edge[4].src = 1;
graph->edge[4].dest = 4;
graph->edge[4].weight = 2;
graph->edge[5].src = 3;
graph->edge[5].dest = 2;
graph->edge[5].weight = 5;
graph->edge[6].src = 3;
graph->edge[6].dest = 1;
graph->edge[6].weight = 1;
graph->edge[7].src = 4;
graph->edge[7].dest = 3;
graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}실행 결과
Vertex : 0 1 2 3 4 Distance From Source : 0 -1 2 -2 1