단일 출발점 최단 경로(Single Source Shortest Path) 알고리즘은 양수든 음수든 임의의 가중치를 가진 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최소 거리를 구하는 알고리즘이며, 일반적으로 벨만-포드(Bellman-Ford) 알고리즘이라고 불립니다. 다익스트라(Dijkstra) 알고리즘과의 가장 큰 차이점은, 다익스트라 알고리즘에서는 음수 가중치를 처리할 수 없지만 벨만-포드 알고리즘에서는 이를 손쉽게 처리할 수 있다는 점입니다.
동작 원리
벨만-포드 알고리즘은 상향식(bottom-up) 방식으로 거리를 계산합니다. 먼저 경로에 간선이 하나만 있는 경우의 거리부터 구하고, 이후 경로 길이를 한 단계씩 늘려가며 가능한 모든 해를 찾아냅니다. 핵심 연산은 간선 완화(relaxation)로, 어떤 간선 (u, v)에 대해 dist[u] + cost(u, v)가 현재 dist[v]보다 작으면 dist[v]를 갱신하는 과정을 말합니다. 이 과정을 정점 수에서 1을 뺀 횟수만큼 반복하면 최단 거리가 확정되며, 마지막에 간선 완화가 더 이상 일어나지 않는지 검사하여 음수 사이클(negative cycle)의 존재 여부까지 판별할 수 있습니다.
입력 및 출력 예시
입력 − 그래프의 비용 행렬:
0 6 ∞ 7 ∞ ∞ 0 5 8 -4 ∞ -2 0 ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ 0
출력 − 출발 정점(Source Vertex): 2
Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 그래프에는 음수 간선 사이클이 없습니다
여기서 Vert는 정점 번호, Dist는 출발 정점으로부터의 최단 거리, Pred는 해당 정점 직전의 선행자(predecessor) 정점을 의미합니다.
알고리즘
bellmanFord(dist, pred, source)
입력 − 거리 리스트(dist), 선행자 리스트(pred), 출발 정점(source).
출력 − 음수 사이클이 발견되면 true, 아니면 false.
Begin
iCount := 1
maxEdge := n * (n - 1) / 2 // n은 정점의 개수
for 그래프의 모든 정점 v에 대해, do
dist[v] := ∞
pred[v] := ϕ
done
dist[source] := 0
eCount := 그래프에 존재하는 간선의 개수
edgeList라는 이름의 간선 리스트 생성
while iCount < n, do
for i := 0 to eCount, do
if dist[edgeList[i].v] > dist[edgeList[i].u] + (간선 i의 비용 cost[u,v]), then
dist[edgeList[i].v] := dist[edgeList[i].u] + (간선 i의 비용 cost[u,v])
pred[edgeList[i].v] := edgeList[i].u
done
done
iCount := iCount + 1
done
for 그래프의 모든 간선 i에 대해, do
if dist[edgeList[i].v] > dist[edgeList[i].u] + (간선 i의 비용 cost[u,v]), then
return true // 음수 사이클 존재
done
done
return false // 음수 사이클 없음
End
C++ 구현 예제
#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]){
// 간선 완화(relaxation) 후 선행자 설정
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)입니다. 정점 수에서 1을 뺀 만큼 전체 간선을 순회하기 때문입니다. 다익스트라 알고리즘(O(E log V))보다는 느리지만, 음수 가중치 간선을 다룰 수 있고 음수 사이클의 존재 여부까지 검출할 수 있다는 강력한 장점이 있습니다. 따라서 음수 가중치가 포함된 그래프의 최단 경로 문제나 환율 차익거럼 탐지 등 음수 사이클 검출이 필요한 문제에서 널리 활용됩니다.