벨만-포드 알고리즘

수치해석 소프트웨어 마지막 수정: 2026-08-24 04:36:44

1. 개요[편집]

벨만-포드 알고리즘 Bellman–Ford (–Moore) algorithm
푸는 문제	단일 출발점 최단경로 (SSSP)
음의 가중치	허용 — 음수 사이클이면 검출해서 보고
시간	$O(VE)$ — 완화 라운드 $V-1$ 회
공간	$O(V)$ — 거리 배열과 선행자 배열뿐
분류	라벨 수정(label-correcting)
기원	Shimbel(1955) · Ford(1956) · Bellman(1958) · Moore(1959)

다익스트라가 “한 번 정하면 끝”이라면, 벨만-포드는 “될 때까지 계속 고친다”이다.

벨만-포드 알고리즘은 간선 가중치에 음수가 섞여 있어도 단일 출발점에서 모든 정점까지의 최단경로를 구하고, 최단경로가 정의되지 않는 음수 사이클이 있으면 그 사실을 검출하는 알고리즘이다. 전체 구조가 어이없을 만큼 단순하다 — 모든 간선을 한 번씩 훑어 완화(relaxation)하는 작업을 $V-1$ 번 반복한다. 그게 전부다.

\textbf{for } i = 1 \ldots V-1: \quad \textbf{for } (u,v,w) \in E: \quad d[v] \leftarrow \min\big(d[v],\; d[u] + w\big)

다익스트라 알고리즘의 $O(E + V \log V)$ 에 비하면 $O(VE)$ 는 명백히 느리다. 그럼에도 이 알고리즘이 교과서와 현업에서 사라지지 않는 이유는 세 가지다. 음수 가중치를 먹는다, 음수 사이클을 검출한다, 그리고 지역 정보만으로 돌아가서 분산 구현이 된다. 마지막 성질이 인터넷 라우팅 프로토콜의 절반을 만들었다.

2. $V-1$ 번이면 충분한 이유[편집]

정당화는 귀납법 한 줄이다. 다음 불변식을 보자.

$i$ 번째 라운드가 끝난 뒤, $d[v]$ 는 간선 $i$ 개 이하를 쓰는 $s \to v$ 경로 중 최단값 이하다.

$i=0$ 일 때 $d[s]=0$ 이고 나머지는 $\infty$ 이므로 성립한다. 귀납 단계도 뻔하다. 간선 $i+1$ 개짜리 최단경로가 $s \leadsto u \to v$ 라면, 앞부분 $s \leadsto u$ 는 간선 $i$ 개짜리이므로 귀납 가정에 의해 $i$ 라운드 후 $d[u]$ 가 이미 충분히 작고, $i+1$ 라운드에서 간선 $(u,v)$ 를 완화하는 순간 $d[v] \le d[u] + w(u,v)$ 가 된다.

여기에 음수 사이클이 없으면 최단경로는 단순 경로이므로 간선을 최대 $V-1$ 개 쓴다는 사실을 얹으면 $V-1$ 라운드로 충분하다. 사이클을 도는 것이 이득이 아니면(가중치 합 $\ge 0$ ) 굳이 정점을 두 번 방문할 이유가 없기 때문이다.

여기서 중요한 것은 완화 순서에 아무 조건이 없다는 점이다. 간선을 어떤 순서로 훑어도 위 논증이 그대로 간다. 다익스트라가 “거리가 작은 순서”라는 정렬을 목숨처럼 지키느라 우선순위 큐를 들고 다니고 그 대가로 음수 가중치에서 무너지는 것과 정확히 대조된다. 벨만-포드는 순서를 포기하는 대신 아무것도 무너지지 않는다.

3. 음수 사이클 검출[편집]

$V-1$ 라운드가 끝났는데도 완화되는 간선이 아직 남아 있다면, 간선 $V$ 개짜리 경로가 더 짧다는 뜻이고 그건 사이클을 돌아서 이득을 봤다는 뜻이다. 즉 $V$ 번째 라운드를 한 번 더 돌려 갱신이 일어나는지 보는 것만으로 출발점에서 도달 가능한 음수 사이클의 존재 여부가 판정된다. 다른 최단경로 알고리즘이 그냥 무한 루프에 빠지거나 쓰레기값을 뱉는 상황에서 이쪽은 정직하게 “답이 없습니다”를 반환한다.

사이클을 찾아내고 싶으면 조금 더 하면 된다. $V$ 번째 라운드에서 갱신된 정점 $x$ 를 하나 잡고 선행자 포인터를 $V$ 번 거슬러 올라간다. $V$ 번 올라가면 반드시 사이클 안의 정점에 들어와 있고, 거기서부터 다시 거슬러 올라가 같은 정점을 만날 때까지가 음수 사이클이다.¹

이 검출 기능이 알고리즘의 절반쯤 되는 가치를 차지한다. 실제 응용에서 “음수 사이클이 있느냐”가 곧 문제의 답인 경우가 많다.

차분 제약 시스템. $x_j - x_i \le b_k$ 형태의 부등식 뭉치는 간선 $i \to j$ 의 가중치를 $b_k$ 로 둔 그래프의 최단경로 문제와 동치다. 해가 존재할 필요충분조건이 음수 사이클이 없는 것이며, 존재하면 최단거리 자체가 해다. 스케줄링·타이밍 검증에서 그대로 쓰인다.
환차익 검출. 환율 곱을 최대화하는 문제에 $-\log$ 를 씌우면 합의 최소화가 되고, 무위험 차익거래가 곧 음수 사이클이다. 알고리즘 강의의 단골 예제.

4. 조기 종료와 상수 줄이기[편집]

교과서 의사코드를 그대로 쓰면 항상 $V-1$ 라운드를 다 도는데, 현실 그래프에서는 대개 몇 라운드 만에 수렴한다. 실무 최적화는 셋이다.

조기 종료. 한 라운드에서 완화가 한 번도 일어나지 않으면 즉시 종료. 한 줄짜리 플래그로 대부분의 그래프에서 라운드 수를 극적으로 줄인다.
갱신된 정점만 훑기. 이전 라운드에 $d$ 가 바뀐 정점에서 나가는 간선만 다음 라운드에서 본다. 이게 발전하면 아래의 SPFA다.
옌(Yen)의 개선. 정점에 번호를 매기고 간선을 “번호가 커지는 방향”과 “작아지는 방향”으로 두 뭉치로 나눈 뒤, 각 라운드에서 앞 뭉치를 번호 오름차순으로, 뒤 뭉치를 내림차순으로 훑는다. 한 라운드에 최단경로의 단조 구간이 통째로 전파되므로 필요한 라운드 수가 대략 절반으로 준다.²

무엇을 해도 최악 복잡도 $O(VE)$ 는 그대로다. 상수만 줄어들 뿐이다.

5. SPFA — 빠르지만 저격당한다[편집]

큐를 하나 두고 “ $d$ 가 갱신된 정점”만 넣었다 빼며 그 정점의 나가는 간선만 완화하는 방식을 SPFA(Shortest Path Faster Algorithm)라 부른다. 1994년 돤판딩(段凡丁)이 이름을 붙였고, 발상 자체는 무어(1959)의 큐 기반 라벨 수정법으로 거슬러 올라간다.

무작위·희소 그래프에서는 정점당 큐 진입 횟수가 작은 상수에 그쳐 체감상 다익스트라급으로 빠르다. 그래서 한동안 “벨만-포드는 SPFA로 쓰는 것”이 국룰이었다. 문제는 최악 사례가 $O(VE)$ 그대로이고, 그 최악을 만들기가 쉽다는 것이다. 격자 모양에 가중치를 특정 패턴으로 배치하면 한 정점이 큐에 수십 번씩 다시 들어오게 만들 수 있다. 알고리즘 대회에서 “SPFA 저격 데이터”가 표준 관행이 되면서, 원래 벨만-포드로 풀어야 하는 문제가 아니면 SPFA를 쓰지 않는 쪽으로 분위기가 정리됐다.³

완충 장치로 SLF(Small Label First — 큐 앞의 값보다 작으면 앞에 삽입)와 LLL(Large Label Last — 평균보다 큰 값은 뒤로 돌림) 휴리스틱이 쓰인다. 평균 성능은 좋아지지만 최악 보장은 여전히 없다.

6. 존슨 알고리즘 속의 벨만-포드[편집]

모든 쌍 최단경로(APSP)를 구할 때 벨만-포드가 조연으로서 결정적인 역할을 한다. 존슨 알고리즘의 절차는 이렇다.

가상 정점 $q$ 를 만들어 모든 정점으로 가중치 0인 간선을 건다.
$q$ 에서 벨만-포드를 한 번 돌려 $h(v) = \delta(q, v)$ 를 구한다(음수 사이클이면 여기서 종료).
모든 간선을 재가중한다. $\hat{w}(u,v) = w(u,v) + h(u) - h(v)$ .
이제 모든 간선이 비음수이므로 각 정점에서 다익스트라를 $V$ 번 돌린다.

3단계의 비음수성은 최단경로의 삼각 부등식 $h(v) \le h(u) + w(u,v)$ 에서 곧바로 나온다. 그리고 경로 전체에 대해 $h$ 의 중간항이 망원경처럼 상쇄되므로 재가중은 경로 간의 대소 관계를 바꾸지 않는다. 즉 벨만-포드가 한 번 만들어 준 퍼텐셜 $h$ 가 “음수를 지운다”는 일회성 작업을 해 주고, 이후 무거운 반복은 전부 빠른 다익스트라에게 넘긴다. 결과가 $O(VE + V^2 \log V)$ 로, 희소 그래프에서 플로이드-워셜 알고리즘의 $O(V^3)$ 을 이긴다. 느린 알고리즘을 딱 한 번 쓰고 빠른 알고리즘의 전제조건을 만들어 준다는 이 설계가 존슨 알고리즘의 전부다.

7. 분산 벨만-포드와 count-to-infinity[편집]

완화가 순서에 무관하다는 성질은 각 정점이 이웃과만 정보를 주고받아도 된다는 뜻이다. 정점마다 “각 목적지까지의 현재 추정 거리” 벡터를 들고, 이웃에게 그 벡터를 보내고, 받은 벡터로 자기 값을 완화한다. 이것이 거리 벡터 라우팅(distance-vector routing)이고 RIP가 대표 구현이다. 중앙 조정자도, 전역 그래프 지식도 필요 없다.

대가가 유명한 count-to-infinity다. 어떤 목적지로 가는 링크가 끊어졌다고 하자. 이웃 $B$ 는 “나는 $A$ 를 거쳐 3에 간다”는 옛 정보를 아직 들고 있고, 그것을 $A$ 에게 광고한다. $A$ 는 그 경로가 자기를 지나간다는 것을 모르므로 4로 갱신하고, $B$ 는 5로, 다시 $A$ 는 6으로… 끊어진 목적지의 거리가 둘이 사이좋게 무한대를 향해 기어 올라간다. 문제의 근원은 거리 값 하나에는 경로 정보가 들어 있지 않다는 것이다. 중앙집중식 벨만-포드에서는 라운드가 동기화돼 있어 이런 일이 안 생기지만, 비동기 분산 환경에서는 옛 정보가 되먹임된다.

땜질이 여럿 있다.

무한대를 작게 정의하기. RIP는 홉 수 16을 무한대로 본다. 카운트가 16까지만 올라가면 되므로 수렴은 하지만, 네트워크 지름이 15홉을 넘을 수 없다는 치명적 제약이 생긴다.
스플릿 호라이즌 / 포이즌 리버스. “너에게서 배운 경로를 너에게 다시 광고하지 않는다” 또는 “무한대로 광고한다”. 두 노드 사이의 루프는 막지만 세 노드 이상이 만드는 루프는 못 막는다.
트리거드 업데이트. 주기적 광고를 기다리지 않고 변화 즉시 알린다. 수렴을 빠르게 하지만 원인은 그대로다.

근본적 해법은 두 방향이다. 경로 정보를 값에 함께 실어 루프를 즉시 판정하거나(BGP의 AS-PATH), 아예 각 노드가 전체 위상을 갖고 스스로 다익스트라를 돌리는 링크 상태 방식으로 가거나(OSPF). EIGRP의 DUAL은 그 중간에서 무루프 조건을 명시적으로 검사하는 절충이다.

8. 값 반복과 같은 골격[편집]

수식을 나란히 놓으면 정체가 드러난다. 최단거리 $\delta$ 가 만족하는 벨만 방정식은

\delta(v) = \min_{(u,v) \in E} \{\delta(u) + w(u,v)\}

이고, 마르코프 결정 과정의 값 반복은

V_{k+1}(s) = \min_a \Big\{ c(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V_k(s') \Big\}

이다. 전이가 결정적이고 $\gamma = 1$ 이면 두 번째 식이 첫 번째 식으로 축약된다. 벨만-포드의 한 라운드는 값 반복의 한 스윕이고, 알고리즘 전체는 “고정점에 도달할 때까지 백업을 반복한다”는 동적 계획법의 표준 골격이다. 이름이 같은 벨만인 것은 우연이 아니다.

세부에서 다른 점도 뚜렷하다. 할인 MDP의 값 반복은 $\gamma$ -수축 덕에 기하급수적으로 수렴하되 유한 스텝에 정확히 끝나지 않는다. 반면 음수 사이클이 없는 최단경로는 $V-1$ 라운드에 정확히 끝난다. 사이클을 도는 것이 절대 이득이 아니라는 구조 자체가 할인율을 대신하기 때문이다. 반대로 음수 사이클은 $\gamma=1$ 인 MDP에서 값이 $-\infty$ 로 발산하는 상황에 정확히 대응한다. 그리고 간선을 훑을 때 갱신된 값을 즉시 반영하는 것(가우스-자이델 스윕)이 라운드를 새 배열에 따로 쓰는 것(야코비 스윕)보다 대개 빠른 것도 반복법의 상식 그대로다.

이 관점에서 A* 알고리즘의 휴리스틱은 존슨의 퍼텐셜과 같은 물건이고, 연속 공간으로 극한을 보내면 해밀턴-야코비-벨만 방정식이 된다. 격자에서 벨만-포드로 최단경로를 푸는 것과 아이코널 방정식을 고속 행진법으로 푸는 것이 닮아 보이는 이유가 여기 있다.

9. 여담[편집]

이름에 붙은 사람이 넷이라 호칭이 늘 시끄럽다. 시임벨(1955)이 가장 먼저 발표했고, 포드(1956), 벨만(1958), 무어(1959)가 각자 독립적으로 냈다. 무어의 기여를 존중해 벨만-포드-무어라 부르는 교과서도 많다.
$O(VE)$ 가 오랫동안 음수 가중치 SSSP의 벽이었는데, 2022년 번스타인·나농카이·울프-닐센이 거의 선형 시간 알고리즘을 내놓으며 이론적 지형이 바뀌었다. 다만 로그 인자가 두툼해서 현실 코드가 벨만-포드를 버릴 일은 아직 없다.⁴
코딩 테스트에서 “가중치에 음수가 있을 수 있다”는 한 줄은 사실상 벨만-포드를 쓰라는 지시문이다. 그 한 줄을 못 보고 다익스트라를 제출해 틀리는 것이 이 바닥의 통과의례다.

10. 관련 문서[편집]

왜 하필 $V$ 번 거슬러 올라가는가? 선행자 사슬을 따라가면 반드시 어떤 사이클로 빨려 들어가는데, 정점이 $V$ 개뿐이므로 $V$ 번 이동하면 이미 그 사이클 위에 있다는 것이 보장되기 때문이다. 비둘기집 원리의 가장 실용적인 용례 중 하나. ↩
Yen (1970). 그 뒤 Bannister & Eppstein(2012)이 정점 번호를 무작위로 매기면 기대 라운드 수가 $V/3$ 정도로 더 준다는 것을 보였다. 정렬을 포기한 알고리즘에 다시 정렬을 살짝 얹어 상수를 깎는 셈이라 어딘가 짓궂다. ↩
논문의 평균 복잡도 주장이 근거가 약하다는 지적이 반복적으로 나왔고, 지금은 “SPFA is dead”라는 제목의 글이 검색 상위에 뜰 정도다. 물론 죽은 것은 SPFA를 다익스트라 대용으로 쓰던 관행이지, 음수 가중치 그래프에서의 SPFA 자체가 아니다. ↩
Bernstein, Nanongkai, Wulff-Nilsen (2022), FOCS 최우수 논문. $O(m \log^8 n \log W)$ 급이라 “거의 선형”의 로그가 여덟 개다. 이론 논문에서 로그 지수는 후속 연구가 깎아 내리는 것이 관례이므로, 언젠가 실용화될 여지는 있다. ↩