벨만-포드 알고리즘 |BLOG.INJUN.DEV

벨만-포드(Bellman-Ford) 알고리즘은 가중치가 있는 그래프에서 단일 시작점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘으로, 1950년대에 Richard Bellman과 Lester Ford Jr.에 의해 독립적으로 발견되었으며, 다익스트라 알고리즘과 달리 음수 가중치를 가진 간선을 처리할 수 있고 그래프 내에 음수 사이클이 존재하는지 여부를 탐지할 수 있다는 강력한 특징을 가진다. 동적 프로그래밍(Dynamic Programming) 접근법을 사용하여 O(VE)의 시간 복잡도로 동작하며, 네트워크 라우팅 프로토콜, 금융 시장의 차익 거래 탐지, 최소 비용 흐름 문제 등 다양한 실제 응용 분야에서 핵심적으로 활용되고 있다.

벨만-포드 알고리즘의 역사

벨만-포드 알고리즘이란?
가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘으로, 음수 가중치 간선을 처리할 수 있고 음수 사이클의 존재 여부를 탐지할 수 있다.

벨만-포드 알고리즘은 1956년 미국의 수학자 Lester Randolph Ford Jr.가 최대 흐름 문제에 관한 연구에서 처음 제안했으며, 1958년 Richard Ernest Bellman이 동적 프로그래밍 분야의 연구에서 독립적으로 같은 알고리즘을 발표하여 두 연구자의 이름을 따서 벨만-포드 알고리즘이라고 명명되었다. 특히 Richard Bellman은 동적 프로그래밍의 창시자로서 “Bellman 방정식"을 제안하고 최적화 문제를 작은 하위 문제로 분할하여 해결하는 방법론을 체계화했으며, 벨만-포드 알고리즘은 이러한 동적 프로그래밍 원리를 그래프의 최단 경로 문제에 적용한 대표적인 사례로 평가받는다.

흥미롭게도 Edward F. Moore가 1957년에 발표한 연구에서도 본질적으로 동일한 알고리즘을 기술했기 때문에, 일부 문헌에서는 이 알고리즘을 “Bellman-Ford-Moore 알고리즘"이라고 부르기도 한다. 이 알고리즘은 네트워크 흐름 이론과 라우팅 프로토콜 개발에 지대한 영향을 미쳤으며, 특히 1980년대 인터넷의 초기 라우팅 시스템으로 널리 사용된 RIP(Routing Information Protocol)의 이론적 기반이 되었다. 또한 음수 가중치를 처리할 수 있다는 특성 덕분에 금융 시장에서의 차익 거래(arbitrage) 탐지, 화폐 환율 최적화, 그리고 다양한 운영 연구(Operations Research) 문제에서 실용적으로 활용되고 있다.

알고리즘의 동작 원리

벨만-포드 알고리즘의 핵심은 간선 완화(Edge Relaxation) 연산을 그래프의 모든 간선에 대해 V-1번 반복하는 것이며, 이 과정에서 동적 프로그래밍의 최적 부분 구조(Optimal Substructure)와 중복 하위 문제(Overlapping Subproblems) 성질을 활용한다.

간선 완화(Edge Relaxation)의 개념

간선 완화란?
정점 u에서 정점 v로 가는 간선 (u, v)의 가중치가 w일 때, dist[u] + w < dist[v]이면 dist[v]를 dist[u] + w로 갱신하는 연산으로, 더 짧은 경로를 발견했을 때 거리 정보를 업데이트하는 과정이다.

간선 완화는 현재 알고 있는 v까지의 최단 거리보다 u를 경유하여 v로 가는 경로가 더 짧을 경우 거리를 갱신하는 연산이며, “완화(Relaxation)“라는 용어는 거리 제약 조건을 느슨하게 만든다는 수학적 의미에서 유래했다. 이 연산은 상수 시간 O(1)에 수행되며, 벨만-포드 알고리즘의 가장 기본적인 구성 요소이다.

V-1번 반복의 수학적 근거

그래프에서 사이클을 포함하지 않는 단순 경로(Simple Path)는 최대 V-1개의 간선을 포함할 수 있으며, 이는 시작 정점에서 출발하여 다른 정점으로 가는 경로가 같은 정점을 두 번 이상 방문하지 않을 때 최대 V-1개의 정점을 거쳐갈 수 있기 때문이다. 만약 경로가 V개 이상의 간선을 포함한다면 비둘기집 원리(Pigeonhole Principle)에 의해 반드시 같은 정점을 두 번 이상 방문하게 되어 사이클이 형성되며, 음수 사이클이 아닌 일반적인 사이클에서는 사이클을 제거한 더 짧은 경로가 존재하므로 최단 경로가 될 수 없다.

따라서 첫 번째 반복에서는 시작 정점에서 최대 1개의 간선으로 도달할 수 있는 정점들의 최단 거리가 올바르게 계산되고, 두 번째 반복에서는 최대 2개의 간선으로 도달할 수 있는 정점들의 최단 거리가 계산되며, 이러한 방식으로 i번째 반복 후에는 최대 i개의 간선을 사용하는 최단 경로가 확정된다. 이것이 동적 프로그래밍의 핵심 원리로, 더 작은 하위 문제(더 적은 간선을 사용하는 최단 경로)의 해를 이용하여 더 큰 문제(더 많은 간선을 사용하는 최단 경로)를 점진적으로 해결하는 상향식(Bottom-up) 접근법이다.

알고리즘 수행 단계

1단계: 초기화

시작 정점에서 각 정점까지의 거리를 저장하는 배열 dist[]를 생성하고, 시작 정점의 거리는 0으로 설정하며 다른 모든 정점의 거리는 무한대(INF)로 초기화한다.

2단계: 간선 완화 반복 (V-1회)

모든 간선에 대해 간선 완화를 수행하고, 이 전체 과정을 V-1번 반복한다. 각 간선 (u, v, w)에 대해 dist[u] + w < dist[v]이면 dist[v] = dist[u] + w로 갱신한다.

3단계: 음수 사이클 검사

V-1번의 반복이 완료된 후, 모든 간선에 대해 한 번 더 완화를 시도한다. 만약 이 V번째 반복에서 거리가 갱신되는 간선이 존재한다면 그래프에 음수 사이클이 있는 것이며, 최단 경로가 정의되지 않는다.

동작 예시

다음과 같은 그래프가 있다고 가정한다. 정점 1에서 시작하여 모든 정점까지의 최단 거리를 구한다.

정점: 1, 2, 3, 4
간선: 1→2(가중치 4), 1→3(가중치 3), 2→3(가중치 -2), 3→4(가중치 2)

초기화: dist = [0, INF, INF, INF]
1번째 반복:
- 1→2: dist[2] = 0 + 4 = 4
- 1→3: dist[3] = 0 + 3 = 3
- 2→3: dist[3] = min(3, 4 + (-2)) = 2
- 3→4: dist[4] = 2 + 2 = 4
2번째 반복:
- 변화 없음
3번째 반복:
- 변화 없음
음수 사이클 검사: 갱신되는 간선 없음
결과: dist = [0, 4, 2, 4]

구현 예제

벨만-포드 알고리즘의 C++ 구현이다.

#include <iostream>
#include <vector>
using namespace std;

#define INF 1e9

int main() {
    int n, m; // n: 정점 수, m: 간선 수
    cin >> n >> m;

    vector<tuple<int, int, int>> edges; // (시작, 도착, 가중치)
    vector<long long> dist(n + 1, INF);

    // 간선 입력
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    int start;
    cin >> start;

    dist[start] = 0;

    // V-1번 간선 완화 반복
    for (int i = 0; i < n - 1; i++) {
        for (auto& [u, v, w] : edges) {
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
            }
        }
    }

    // 음수 사이클 검사
    bool hasNegativeCycle = false;
    for (auto& [u, v, w] : edges) {
        if (dist[u] != INF && dist[v] > dist[u] + w) {
            hasNegativeCycle = true;
            break;
        }
    }

    if (hasNegativeCycle) {
        cout << "음수 사이클이 존재합니다." << '\n';
    } else {
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) {
                cout << "INF" << '\n';
            } else {
                cout << dist[i] << '\n';
            }
        }
    }

    return 0;
}

코드 설명

edges: 모든 간선을 (시작 정점, 도착 정점, 가중치) 튜플로 저장하며, 인접 리스트 대신 간선 리스트를 사용하면 구현이 더 간단해진다.
dist: 시작 정점에서 각 정점까지의 최단 거리를 저장하는 배열로, 음수 가중치로 인한 오버플로우를 방지하기 위해 long long 타입을 사용한다.
V-1번의 외부 루프에서 모든 간선을 순회하며 간선 완화를 수행하고, 마지막에 한 번 더 순회하여 음수 사이클을 검사한다.

음수 가중치 처리

벨만-포드 알고리즘의 가장 큰 특징은 음수 가중치를 가진 간선을 올바르게 처리할 수 있다는 점이며, 이것이 다익스트라 알고리즘과의 가장 본질적인 차이점이다.

다익스트라가 음수 가중치에서 실패하는 이유

다익스트라 알고리즘은 탐욕적(Greedy) 접근법을 사용하여 매번 현재까지 발견된 최단 거리를 가진 정점을 선택하고 그 정점의 최단 거리를 “확정"하는데, 이는 한 번 확정된 정점의 최단 거리는 더 이상 갱신되지 않는다는 것을 전제로 한다. 모든 간선의 가중치가 양수일 때는 이 전제가 성립하지만, 음수 가중치가 있으면 이미 확정된 정점을 경유하는 더 짧은 경로가 나중에 발견될 수 있어 알고리즘이 올바른 결과를 보장하지 못한다.

벨만-포드의 음수 가중치 처리 원리

벨만-포드 알고리즘은 모든 정점의 최단 거리를 “동시에” 갱신하는 방식을 사용하며, 다익스트라처럼 정점을 확정하는 개념 없이 V-1번의 반복을 통해 모든 간선에 대한 완화를 반복적으로 수행한다. 음수 가중치로 인해 나중에 더 짧은 경로가 발견되더라도 다음 반복에서 거리가 갱신될 수 있으므로, 음수 사이클만 존재하지 않는다면 정확한 최단 거리를 찾을 수 있다.

음수 가중치의 실제 응용

음수 가중치는 다양한 실제 문제에서 자연스럽게 등장한다.

화폐 환율 변환: 환율을 로그 변환하면 곱셈이 덧셈으로 바뀌고, 환차익은 음수 사이클로 표현된다.
네트워크 흐름 문제: 비용을 최소화하기 위해 잔여 그래프(Residual Graph)에서 음수 비용 간선을 사용한다.
게임 이론과 최적화: 손실이나 페널티를 나타내기 위해 음수 가중치가 자연스럽게 모델링된다.

음수 사이클 탐지

음수 사이클이란?
사이클을 구성하는 간선들의 가중치 합이 음수인 사이클로, 음수 사이클이 존재하면 그 사이클을 계속 돌면서 거리를 무한히 줄일 수 있기 때문에 최단 경로가 정의되지 않는다.

음수 사이클의 영향

음수 사이클이 존재하면 해당 사이클에 포함된 정점들은 사이클을 한 번 돌 때마다 거리가 감소하므로, 이론적으로 사이클을 무한히 반복하면 거리를 음의 무한대(-∞)로 만들 수 있다. 따라서 명확한 최단 거리를 정의할 수 없으며, 실제 문제에서 이는 차익 거래 기회가 존재하거나 모델링에 논리적 오류가 있음을 의미할 수 있다.

V번째 반복을 통한 음수 사이클 탐지

벨만-포드 알고리즘에서 V-1번의 반복으로 모든 최단 경로가 확정되어야 하므로, V번째 반복에서 여전히 거리가 갱신되는 간선이 있다면 이는 V개 이상의 간선을 사용하는 경로가 더 짧다는 의미이다. V개 이상의 간선을 사용한다는 것은 반드시 사이클을 포함해야 하고, 사이클을 포함하면서 거리가 감소한다는 것은 그 사이클이 음수 사이클임을 의미한다. 따라서 알고리즘의 마지막에 모든 간선을 한 번 더 검사하여 거리가 갱신되는지 확인함으로써 음수 사이클의 존재 여부를 O(E) 시간에 판별할 수 있다.

음수 사이클 존재 시 처리

음수 사이클이 탐지되면 일반적으로 알고리즘을 종료하고 음수 사이클이 존재함을 보고한다. 만약 시작 정점에서 음수 사이클에 도달할 수 없는 정점들이 있다면 그 정점들에 대한 최단 거리는 여전히 유효할 수 있지만, 대부분의 응용에서는 음수 사이클의 존재 자체가 문제 상황을 나타내므로 별도의 처리가 필요하다.

시간 복잡도 분석

벨만-포드 알고리즘의 시간 복잡도는 O(VE)이며, 여기서 V는 정점의 개수이고 E는 간선의 개수이다.

O(VE) 상세 분석

알고리즘은 V-1번의 외부 반복을 수행하고, 각 반복마다 모든 E개의 간선에 대해 완화를 시도하므로 총 연산 횟수는 (V-1) × E가 된다. 음수 사이클 검사를 위한 E번의 추가 연산이 필요하지만 이는 점근적으로 O(VE)에 포함된다. 각 간선 완화는 상수 시간 O(1)에 수행되므로 전체 시간 복잡도는 O(VE)이다.

그래프 유형별 분석

그래프 유형	간선 수	시간 복잡도	특징
희소 그래프	E ≈ V	O(V²)	트리, 도로 네트워크
일반 그래프	E ≈ V log V	O(V² log V)	소셜 네트워크
밀집 그래프	E ≈ V²	O(V³)	완전 그래프

밀집 그래프에서는 시간 복잡도가 O(V³)까지 증가하여 매우 느려질 수 있으며, 이런 경우 음수 가중치가 없다면 다익스트라 알고리즘을 사용하는 것이 훨씬 효율적이다.

다익스트라 알고리즘과의 비교

비교 항목	벨만-포드	다익스트라
시간 복잡도	O(VE)	O(E log V)
음수 가중치	처리 가능	처리 불가
음수 사이클 탐지	가능	불가
접근 방식	동적 프로그래밍	탐욕 알고리즘
구현 복잡도	간단 (3중 루프)	복잡 (우선순위 큐 필요)
일반적인 속도	느림	빠름

알고리즘 선택 가이드

모든 가중치가 양수이고 속도가 중요: 다익스트라 알고리즘
음수 가중치가 존재: 벨만-포드 알고리즘
음수 사이클 탐지 필요: 벨만-포드 알고리즘
구현 간단함 중시, 그래프 크기 작음: 벨만-포드 알고리즘

실제 응용 사례

벨만-포드 알고리즘은 음수 가중치나 음수 사이클 탐지가 필요한 영역에서 필수적으로 사용된다.

네트워크 라우팅 프로토콜 (RIP)

RIP(Routing Information Protocol)는 1988년 RFC 1058로 표준화된 거리 벡터 라우팅 프로토콜로, 벨만-포드 알고리즘을 기반으로 한다. 각 라우터는 주기적으로(일반적으로 30초마다) 자신의 라우팅 테이블을 이웃 라우터와 교환하며, 이 정보를 바탕으로 벨만-포드 알고리즘의 분산 버전(Distributed Bellman-Ford)을 실행하여 네트워크 상의 모든 목적지까지의 최단 경로를 계산한다. RIP는 인터넷의 초기 라우팅 시스템에서 널리 사용되었으며, 단순성 때문에 현재도 소규모 네트워크에서 활용되고 있다.

차익 거래(Arbitrage) 탐지

금융 시장에서 여러 화폐 간의 환율을 그래프로 모델링할 때, 환율 r을 -log(r)로 변환하면 환전 과정의 곱셈이 덧셈으로 바뀐다. 예를 들어, USD → EUR → JPY → USD의 환전 경로에서 환율의 곱이 1보다 크면 차익 거래 기회가 존재하며, 로그 변환 후에는 이것이 음수 사이클로 표현된다. 벨만-포드 알고리즘으로 음수 사이클을 탐지함으로써 무위험 수익 기회를 찾을 수 있으며, 이는 고빈도 거래(HFT) 시스템에서 실제로 사용되는 기법이다.

최소 비용 최대 흐름 문제

네트워크 흐름 문제에서 각 간선에 용량(capacity)뿐만 아니라 단위 비용(cost)이 있을 때, 최소 비용으로 최대 흐름을 보내는 문제를 해결하는 여러 알고리즘(예: Successive Shortest Paths, Cycle-Canceling)은 벨만-포드를 내부적으로 사용한다. 잔여 그래프(Residual Graph)에서 역방향 간선은 음수 비용을 가질 수 있으므로 다익스트라 대신 벨만-포드가 필요하며, 이는 물류, 운송, 통신 네트워크 최적화 등에 응용된다.

제약 조건 차이 시스템

선형 프로그래밍의 특수 형태인 제약 조건 차이 시스템(System of Difference Constraints)은 x_j - x_i ≤ c_ij 형태의 제약들로 구성되며, 이를 그래프로 모델링하여 벨만-포드 알고리즘으로 해결할 수 있다. 제약을 만족하는 해가 존재하면 최단 거리가 하나의 해가 되고, 음수 사이클이 존재하면 제약을 만족하는 해가 없음을 의미한다.

최적화 기법

벨만-포드 알고리즘의 기본 형태는 항상 V-1번의 완전한 반복을 수행하지만, 실제로는 더 빠르게 수렴하도록 여러 최적화 기법을 적용할 수 있다.

조기 종료 최적화

특정 반복에서 어떤 간선도 완화되지 않았다면 모든 최단 거리가 이미 확정된 것이므로 남은 반복을 건너뛰고 알고리즘을 종료할 수 있다. 이 최적화는 구현이 매우 간단하면서도 많은 실제 그래프에서 V-1번보다 훨씬 적은 반복으로 종료되어 평균 성능을 크게 향상시킨다.

bool updated = false;
for (auto& [u, v, w] : edges) {
    if (dist[u] != INF && dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        updated = true;
    }
}
if (!updated) break; // 조기 종료

SPFA(Shortest Path Faster Algorithm)

SPFA는 벨만-포드 알고리즘의 최적화된 변형으로, 1994년 중국의 Duan Fanding이 제안했으며, 큐(Queue) 자료구조를 사용하여 거리가 갱신된 정점만을 선택적으로 처리한다. 모든 간선을 매 반복마다 검사하는 대신 거리가 변경된 정점의 인접 간선만 완화하므로 평균적으로 O(E) 시간에 동작하지만, 최악의 경우에는 여전히 O(VE)이다. 특정 형태의 그래프(특히 격자 그래프)에서 최악의 경우가 발생할 수 있어, 최근에는 경쟁 프로그래밍에서 의도적으로 SPFA를 느리게 만드는 테스트 케이스가 포함되기도 한다.

결론

벨만-포드 알고리즘은 1950년대에 Richard Bellman과 Lester Ford Jr.에 의해 독립적으로 발견된 알고리즘으로, 동적 프로그래밍의 원리를 그래프의 최단 경로 문제에 적용한 대표적인 사례이다. O(VE)의 시간 복잡도로 다익스트라 알고리즘보다 일반적으로 느리지만, 음수 가중치를 가진 간선을 올바르게 처리할 수 있고 그래프 내의 음수 사이클 존재 여부를 탐지할 수 있다는 강력한 특징을 가진다. RIP 라우팅 프로토콜, 금융 시장의 차익 거래 탐지, 최소 비용 흐름 문제, 제약 조건 차이 시스템 등 다양한 실제 응용 분야에서 핵심적인 역할을 하며, 특정 문제 영역에서는 대체 불가능한 중요한 알고리즘이다.

벨만-포드 알고리즘의 역사#

알고리즘의 동작 원리#

간선 완화(Edge Relaxation)의 개념#

V-1번 반복의 수학적 근거#

알고리즘 수행 단계#

동작 예시#

구현 예제#

코드 설명#

음수 가중치 처리#

다익스트라가 음수 가중치에서 실패하는 이유#

벨만-포드의 음수 가중치 처리 원리#

음수 가중치의 실제 응용#

음수 사이클 탐지#

음수 사이클의 영향#

V번째 반복을 통한 음수 사이클 탐지#

음수 사이클 존재 시 처리#

시간 복잡도 분석#

O(VE) 상세 분석#

그래프 유형별 분석#

다익스트라 알고리즘과의 비교#

알고리즘 선택 가이드#

실제 응용 사례#

네트워크 라우팅 프로토콜 (RIP)#

차익 거래(Arbitrage) 탐지#

최소 비용 최대 흐름 문제#

제약 조건 차이 시스템#

최적화 기법#

조기 종료 최적화#

SPFA(Shortest Path Faster Algorithm)#

결론#