벨만-포드(Bellman-Ford) 알고리즘은 그래프 이론에서 시작 정점(소스)으로부터 나머지 모든 정점까지의 최단 거리를 구하는 데 사용되는 대표적인 알고리즘입니다. 널리 알려진 다익스트라(Dijkstra) 알고리즘과의 가장 큰 차이점은 음수 가중치의 처리 여부입니다. 다익스트라 알고리즘은 음수 가중치를 가진 간선이 포함된 그래프에서 올바른 결과를 보장할 수 없지만, 벨만-포드 알고리즘은 이러한 경우에도 정확한 최단 경로를 손쉽게 구할 수 있습니다.
벨만-포드 알고리즘은 상향식(bottom-up) 방식으로 최단 거리를 계산합니다. 먼저 경로에 간선이 하나뿐인 경우의 거리를 구한 뒤, 반복을 통해 경로 길이를 하나씩 늘려가며 가능한 모든 해를 탐색합니다. 모든 간선에 대해 (정점 수 − 1)번의 릴랙스(relaxation) 작업을 수행한 후, 마지막으로 한 번 더 검사하여 음수 사이클(negative cycle)의 존재 여부까지 확인할 수 있다는 점이 큰 장점입니다.
입력과 출력
아래는 5개의 정점을 가진 유향 그래프의 비용 행렬을 입력으로 사용한 예시입니다.
Input: 그래프의 비용 행렬: 0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ 0 Output: Source Vertex: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 The graph has no negative edge cycle
알고리즘
bellmanFord(dist, pred, source)
입력 − 거리 리스트(dist), 선행자 리스트(pred), 시작 정점(source)
출력 − 음수 사이클이 발견되면 true(참)를 반환
Begin
iCount := 1
maxEdge := n * (n - 1) / 2 //n은 정점의 개수
for all vertices v of the graph, do
dist[v] := ∞
pred[v] := ϕ
done
dist[source] := 0
eCount := number of edges present in the graph
create edge list named edgeList
while iCount < n, do
for i := 0 to eCount, do
if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i),
then dist[edgeList[i].v] := dist[edgeList[i].u] + cost[u,v]
pred[edgeList[i].v] := edgeList[i].u
done
done
iCount := iCount + 1
for all vertices i in the graph, do
if dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] for edge i),
then return true
done
return false
EndC++ 구현 예제
#include<iostream>
#include<iomanip>
#define V 5
#define INF 999
using namespace std;
//그래프의 비용 행렬 (유향 그래프), 정점 5개
int costMat[V][V] = {
{0, 6, INF, 7, INF},
{INF, 0, 5, 8, -4},
{INF, -2, 0, INF, INF},
{INF, INF, -3, 0, 9},
{2, INF, 7, INF, 0}
};
typedef struct {
int u, v, cost;
}edge;
int isDiagraph() {
//그래프가 유향 그래프인지 확인
int i, j;
for(i = 0; i<V; i++) {
for(j = 0; j<V; j++) {
if(costMat[i][j] != costMat[j][i]) {
return 1; //유향 그래프인 경우
}
}
}
return 0; //무향 그래프인 경우
}
int makeEdgeList(edge *eList) {
//그래프의 간선 정보로 에지 리스트 생성
int count = -1;
if(isDiagraph()) {
for(int i = 0; i<V; i++) {
for(int j = 0; j<V; j++) {
if(costMat[i][j] != 0 && costMat[i][j] != INF) {
count++; //유향 그래프일 때 간선 추가
eList[count].u = i; eList[count].v = j;
eList[count].cost = costMat[i][j];
}
}
}
}else {
for(int i = 0; i<V; i++) {
for(int j = 0; j<i; j++) {
if(costMat[i][j] != INF) {
count++; //무향 그래프일 때 간선 추가
eList[count].u = i; eList[count].v = j;
eList[count].cost = costMat[i][j];
}
}
}
}
return count+1;
}
int bellmanFord(int *dist, int *pred,int src) {
int icount = 1, ecount, max = V*(V-1)/2;
edge edgeList[max];
for(int i = 0; i<V; i++) {
dist[i] = INF; //무한대로 초기화
pred[i] = -1; //아직 선행자 없음
}
dist[src] = 0; //시작 정점의 거리는 0
ecount = makeEdgeList(edgeList); //에지 리스트 생성
while(icount < V) { //반복 횟수는 (정점 수 - 1)
for(int i = 0; i<ecount; i++) {
if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) { //간선 릴랙스 후 선행자 설정
dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v];
pred[edgeList[i].v] = edgeList[i].u;
}
}
icount++;
}
//음수 사이클 검사
for(int i = 0; i<ecount; i++) {
if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) {
return 1; //음수 사이클이 존재함을 의미
}
}
return 0; //음수 사이클 없음
}
void display(int *dist, int *pred) {
cout << "Vert: ";
for(int i = 0; i<V; i++)
cout <<setw(3) << i << " ";
cout << endl;
cout << "Dist: ";
for(int i = 0; i<V; i++)
cout << setw(3) << dist[i] << " ";
cout << endl;
cout << "Pred: ";
for(int i = 0; i<V; i++)
cout << setw(3) << pred[i] << " ";
cout << endl;
}
int main() {
int dist[V], pred[V], source, report;
source = 2;
report = bellmanFord(dist, pred, source);
cout << "Source Vertex: " << source<<endl;
display(dist, pred);
if(report)
cout << "The graph has a negative edge cycle" << endl;
else
cout << "The graph has no negative edge cycle" << endl;
}실행 결과
Source Vertex: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 The graph has no negative edge cycle
시간 복잡도
벨만-포드 알고리즘의 시간 복잡도는 O(V × E)입니다. 여기서 V는 정점의 개수, E는 간선의 개수를 의미합니다. 다익스트라 알고리즘(O(E log V))보다는 느리지만, 음수 가중치 그래프에서의 최단 경로 계산과 음수 사이클 감지가 필요한 상황에서는 필수적인 선택입니다. 참고로 그래프에 음수 사이클이 존재하면 해당 사이클에 도달하는 정점들의 최단 거리는 무한히 작아질 수 있으므로, 위 예제처럼 알고리즘이 이를 감지해 알려주는 것이 중요합니다.