algo · 12

벨만-포드

그래프음수가중치최단경로

벨만-포드(Bellman-Ford) 알고리즘은 한 출발 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다. 다익스트라와 목적은 같지만 음수 가중치 간선이 있어도 동작하고, 음수 사이클이 있는지도 알려 줍니다. 방법은 단순합니다. 모든 간선을 한 번씩 훑으며 "이 간선을 거치면 더 짧아지는가"를 확인하는 일(완화, relaxation)을 V-1번 반복합니다.

다익스트라는 한 번 확정한 거리를 다시 고치지 않는다는 가정 위에 서 있어서 음수 간선을 만나면 틀릴 수 있습니다. 벨만-포드는 확정하지 않고 거리를 계속 줄여 가므로 그 가정이 필요 없습니다. 대신 모든 간선을 여러 번 훑어서 느립니다. 이 토픽에서는 라운드가 반복되며 거리가 줄어드는 모습, 간선 하나를 완화하는 순간, 음수 사이클에서 알고리즘이 어떻게 이상을 알리는지를 봅니다.

핵심 개념

완화(relaxation)

간선 u → v에 대해 d[u] + 가중치가 d[v]보다 작으면 d[v]를 그 값으로 줄입니다. 지금까지 알려진 경로보다 짧은 길을 발견했을 때 거리를 갱신하는 연산입니다.

핵심 개념

V-1번 반복

음수 사이클이 없으면 최단 경로는 정점을 중복해서 지나지 않으므로 간선을 많아야 V-1개 씁니다. 라운드를 i번 돌리면 간선 i개 이하로 가는 최단 경로가 반영되어 V-1번이면 충분합니다.

핵심 개념

음수 가중치

간선의 가중치가 음수여도 됩니다. 거리를 확정하지 않고 계속 줄일 수 있어서, 나중에 발견한 음수 간선이 앞서 구한 값을 더 낮추는 경우도 반영됩니다.

핵심 개념

음수 사이클

가중치 합이 음수인 사이클입니다. 한 바퀴 돌 때마다 거리가 줄어서 출발점에서 닿을 수 있다면 최단 거리가 정해지지 않습니다.

핵심 개념

V번째 확인

V-1번 반복한 뒤 한 번 더 모든 간선을 완화해 봅니다. 그래도 줄어드는 간선이 있다면 출발 정점에서 닿을 수 있는 음수 사이클이 있다는 신호입니다.

핵심 개념

조기 종료

한 라운드에서 갱신이 없으면 그 뒤로도 변하지 않으므로 반복을 멈출 수 있습니다. 간선을 훑는 순서에 따라 필요한 라운드 수는 달라집니다.

시간은 O(VE)입니다 — 간선 E개를 확인하는 라운드를 V-1번 돌립니다. 간선이 정점 수의 제곱에 가까운 조밀한 그래프에서는 O(V³)에 가까워집니다.

공간은 O(V)입니다 — 입력 그래프를 빼면 추가 공간은 거리 배열 하나뿐입니다. 실제 경로까지 복원하려면 이전 정점을 기록하는 배열이 하나 더 필요합니다.

다익스트라보다 느립니다 — 이진 힙을 쓰는 다익스트라는 O((V + E) log V)입니다. 음수 간선이 없다면 다익스트라가 보통 더 빠르고, 음수 간선이 있거나 음수 사이클을 찾을 때 벨만-포드를 씁니다.

간선 순서에 민감합니다 — 같은 라운드 안에서 먼저 갱신된 값이 뒤쪽 간선에 바로 쓰입니다. 순서가 좋으면 적은 라운드에 끝나고, 나쁘면 V-1번이 모두 필요하지만 결과는 같습니다.

이 시각화에서 확인할 것 — "라운드 반복" 탭에서 라운드마다 거리가 줄어들고 마지막 확인 라운드에서 갱신이 멈추는 모습을, "간선 완화" 탭에서 d[u] + 가중치와 d[v]를 비교하는 순간을, "음수 사이클" 탭에서 확인 라운드에도 거리가 줄어드는 모습을 STEP으로 확인하세요.

벨만-포드의 배경

이 알고리즘은 리처드 벨만(Richard Bellman)이 1958년 논문 "On a routing problem"에서 동적 계획법으로 최단 경로 문제를 푸는 방식으로 소개했고, 레스터 포드(Lester R. Ford Jr.)가 1956년 거리를 완화로 줄여 가는 일반적인 틀을 먼저 제시했습니다. 에드워드 무어(Edward F. Moore)도 1957년 학회에서 같은 방식을 발표해서(논문은 1959년) 벨만-포드-무어 알고리즘이라고 부르기도 합니다.

숫자로 확인하기

예시 그래프 — 정점 S, A, B, C, D 5개와 간선 7개(S → A 4, S → B 5, A → B -3, A → C 8, B → C 4, B → D 7, C → D 2)입니다. 출발은 S이고 A → B가 음수 간선입니다. 간선은 C → D, B → C, A → B, S → A, S → B, A → C, B → D 순서로 확인합니다.

라운드 1~2 — 라운드 1에서 A가 4, B가 5, C가 12, D가 12가 됩니다. 라운드 2에서는 C가 9, B가 1, D가 8로 줄어듭니다. 앞에서 확인한 B → C는 아직 d[B] = 5를 썼기 때문에 C를 9까지만 줄였습니다.

라운드 3~5 — 라운드 3에서 C가 5, 라운드 4에서 D가 7이 되고, 5번째 확인 라운드에서는 갱신이 없습니다. 최단 거리는 S 0, A 4, B 1, C 5, D 7입니다. 최단 경로 S → A → B → C → D의 간선 4개가 경로 반대 순서로 놓여 있어 라운드마다 간선 하나씩만 진행하므로 V-1 = 4라운드가 모두 필요했습니다.

간선 순서 — 같은 간선을 S → A, A → B, S → B, B → C, A → C, B → D, C → D 순서로 확인하면 2라운드(두 번째 라운드는 갱신 없음)에 끝납니다.

음수 사이클 — B → A(1) 간선을 더하면 A → B → A의 합이 -3 + 1 = -2입니다. 5번째 확인 라운드에서도 거리가 줄어들어 음수 사이클이 있다고 판단합니다.

코드 확인 — 파이썬과 자바 구현 모두 같은 그래프에서 [0, 4, 1, 5, 7]을 돌려주고, B → A(1)을 더하면 음수 사이클을 알립니다.

자주 하는 오해

음수 간선이 있으면 최단 경로가 없다 — 문제가 되는 것은 음수 간선이 아니라 음수 사이클입니다. 음수 간선만 있고 음수 사이클이 없으면 최단 경로가 정해지고 벨만-포드가 구합니다.

다익스트라에서 음수 간선만 조심하면 된다 — 일반적인 다익스트라 구현은 거리를 한 번 확정하면 고치지 않기 때문에 음수 간선이 있으면 틀린 값을 낼 수 있습니다. 음수 간선이 있으면 벨만-포드 같은 알고리즘을 씁니다.

무방향 그래프에서도 음수 간선을 쓸 수 있다 — 벨만-포드는 무방향 간선을 양방향 간선 둘로 바꿔 다루므로 음수 간선 하나가 u → v → u의 음수 사이클이 됩니다. 그래서 음수 간선은 방향 그래프에서 다룹니다.

V-1번 뒤 확인은 필요 없다 — 음수 사이클이 없다는 보장이 있을 때만 생략할 수 있습니다. 음수 사이클이 있으면 V-1번을 돌려도 값은 끝없이 줄 수 있어서, 확인 라운드가 있어야 알 수 있습니다.

모든 라운드가 꼭 필요하다 — 간선 순서가 좋으면 갱신이 일찍 멈춥니다. 한 라운드에서 갱신이 없으면 바로 끝내도 되지만, 최악의 경우는 여전히 V-1번입니다.

면접에서 이렇게 물어요

면접 질문

벨만-포드가 다익스트라와 다른 점은?

음수 가중치 간선을 처리하고 음수 사이클을 탐지합니다. 다익스트라는 거리를 확정하며 진행해서 음수 간선이 있으면 틀릴 수 있습니다. 대신 벨만-포드는 O(VE)로 더 느립니다.

면접 질문

왜 V-1번만 반복하면 되나요?

음수 사이클이 없으면 최단 경로는 정점을 중복해서 지나지 않아 간선을 많아야 V-1개 씁니다. 라운드를 i번 돌리면 간선 i개 이하의 최단 경로가 반영되므로 V-1번이면 모든 최단 거리가 확정됩니다.

면접 질문

음수 사이클은 어떻게 찾나요?

V-1번 완화한 뒤 한 번 더 모든 간선을 완화해 봅니다. 거리가 갱신되는 간선이 있으면 출발 정점에서 닿을 수 있는 음수 사이클이 있다는 뜻입니다.

면접 질문

환율 차익거래(arbitrage)를 찾으려면?

환율에 로그를 취하고 부호를 바꾼 값을 간선 가중치로 두면 환율의 곱이 1보다 큰 순환이 가중치 합이 음수인 사이클이 됩니다. 벨만-포드의 음수 사이클 탐지로 찾습니다.

실제 시스템에서는

거리 벡터 라우팅 — RIP(Routing Information Protocol)는 벨만-포드(거리 벡터) 알고리즘에 기반한 라우팅 프로토콜로, 라우터가 이웃과 거리 정보를 주고받으며 각자 경로를 갱신합니다.

차익거래 탐지 — 통화 사이의 환율을 그래프로 보고 음수 사이클을 찾는 문제가 알고리즘 교재의 문제로 나옵니다.

존슨 알고리즘 — 음수 간선이 있는 그래프에서 모든 쌍의 최단 거리를 구할 때, 먼저 벨만-포드로 정점 가중치(포텐셜)를 구해 간선 가중치를 음수가 없도록 바꾼 뒤 다익스트라를 돌립니다.

함께 보면 좋은 토픽

다익스트라 — 음수 간선이 없을 때 쓰는 더 빠른 최단 경로 알고리즘을 봅니다.

그래프 — 방향 그래프와 가중치 간선의 표현을 봅니다.

DP 기초 — 작은 부분 문제의 결과를 쌓아 가는 방식을 봅니다.

라우팅 — 거리 벡터 방식 라우팅을 봅니다.

참고 자료

논문 — Bellman, R., "On a routing problem", Quarterly of Applied Mathematics 16(1), 1958

논문 — Ford, L. R., Jr., "Network flow theory", RAND Corporation Paper P-923, 1956

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 3rd ed., Section 24.1 The Bellman-Ford algorithm

표준 문서 — RFC 2453 RIP Version 2

Python — 벨만-포드와 음수 사이클 탐지

INF = float('inf')

def bellman_ford(n, edges, src):
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):                       # V-1번 반복
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w              # 완화(relax)
    for u, v, w in edges:                          # 한 번 더 확인
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None                           # 음수 사이클
    return dist

# S=0, A=1, B=2, C=3, D=4 · (출발, 도착, 가중치)
E = [(3, 4, 2), (2, 3, 4), (1, 2, -3), (0, 1, 4),
     (0, 2, 5), (1, 3, 8), (2, 4, 7)]
print(bellman_ford(5, E, 0))                       # [0, 4, 1, 5, 7]
print(bellman_ford(5, E + [(2, 1, 1)], 0))         # None  (A → B → A 합 -2)

벨만-포드는 모든 간선을 한 번씩 완화하는 일을 V-1번 반복합니다. 완화는 출발 쪽 거리에 가중치를 더한 값이 도착 쪽의 현재 거리보다 작으면 도착 쪽 거리를 그 값으로 줄이는 연산입니다. 음수 가중치 간선 A → B(-3)이 있어도 정답 [0, 4, 1, 5, 7]이 나옵니다. 다익스트라는 거리를 한 번 확정하면 고치지 않기 때문에 이런 그래프에서 틀릴 수 있습니다. 음수 사이클이 없으면 최단 경로는 간선을 많아야 V-1개 지나므로 V-1번이면 거리가 확정됩니다. 그 뒤 한 번 더 확인했을 때도 줄어드는 간선이 있으면 출발 정점에서 닿을 수 있는 음수 사이클이 있다는 뜻이고, 함수는 None을 돌려줍니다. 간선 B → A(1)을 더하면 A → B → A의 합이 -3 + 1 = -2라 음수 사이클이 생겨 None이 나옵니다. 시각화의 라운드 반복 탭과 음수 사이클 탭이 보여 주는 과정과 같고, 간선 E개를 V번 훑으므로 O(VE)입니다.

Python — 일찍 끝내기와 간선 순서의 영향

def bellman_ford(n, edges, src):
    dist = [INF] * n
    dist[src] = 0
    rounds = 0
    for _ in range(n - 1):
        rounds += 1
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:                              # 한 라운드 동안 갱신이 없으면 끝
            break
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None, rounds
    return dist, rounds

print(bellman_ford(5, E, 0))                       # ([0, 4, 1, 5, 7], 4)
good = [(0, 1, 4), (1, 2, -3), (0, 2, 5), (2, 3, 4),
        (1, 3, 8), (2, 4, 7), (3, 4, 2)]
print(bellman_ford(5, good, 0))                    # ([0, 4, 1, 5, 7], 2)

한 라운드 동안 갱신이 하나도 없으면 이후 라운드에서도 거리가 변하지 않으므로 V-1번을 채우지 않고 끝낼 수 있습니다. 이 조기 종료를 넣으면 간선을 확인하는 순서가 라운드 수에 영향을 줍니다. 같은 그래프에서 간선을 앞쪽 정점에서 뒤쪽 정점 쪽으로 가는 순서(S → A, A → B, …)로 놓으면 라운드 1에서 모든 거리가 확정되고 라운드 2에서 갱신이 없음을 확인하며 끝납니다. 시각화처럼 불리한 순서로 놓으면 4라운드가 모두 필요합니다. 최악의 경우는 순서와 상관없이 V-1번이라 시간 복잡도는 그대로 O(VE)입니다.

Java — 벨만-포드

record Edge(int from, int to, int w) {}

static final int INF = Integer.MAX_VALUE;

static int[] bellmanFord(int n, List<Edge> edges, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (Edge e : edges) {
            if (dist[e.from()] != INF && dist[e.from()] + e.w() < dist[e.to()]) {
                dist[e.to()] = dist[e.from()] + e.w();
            }
        }
    }
    for (Edge e : edges) {                          // 음수 사이클 확인
        if (dist[e.from()] != INF && dist[e.from()] + e.w() < dist[e.to()]) {
            return null;
        }
    }
    return dist;
}

// 같은 그래프: [0, 4, 1, 5, 7], B → A(1)을 더하면 null

자바 버전도 구조가 같습니다. INF를 Integer.MAX_VALUE로 두면 INF에 양의 가중치를 더할 때 넘쳐 음수가 되고, 음의 가중치를 더하면 INF보다 작아져 닿지 못한 정점이 갱신된 것처럼 됩니다. 그래서 출발 쪽 거리가 INF가 아닐 때만 더하도록 검사합니다. 위의 파이썬 예와 같은 그래프에서 결과는 [0, 4, 1, 5, 7]이고, B → A(1) 간선을 더하면 확인 단계에서 null을 돌려줍니다. 실무에서는 음수 가중치가 없다면 보통 다익스트라가 더 빠르지만, 환율이나 비용처럼 음수 간선이 생길 수 있는 문제나 음수 사이클 자체를 찾고 싶은 문제에는 벨만-포드를 씁니다.

벨만-포드 알고리즘이 다익스트라 알고리즘과 달리 처리할 수 있는 것은?

다익스트라는 한 번 확정한 거리를 다시 고치지 않습니다.

다익스트라는 가중치가 모두 0 이상이라는 가정 아래 정점의 거리를 한 번 확정합니다. 벨만-포드는 모든 간선을 반복 완화해 음수 가중치가 있어도 최단 경로를 구할 수 있습니다.

벨만-포드 알고리즘의 시간 복잡도는? (V: 정점 수, E: 간선 수)

모든 간선을 V-1번 반복해서 확인합니다.

간선 E개를 모두 확인하는 과정을 V-1번 반복하므로 O(VE)입니다. 다익스트라보다 느리지만 음수 간선을 처리할 수 있습니다.

벨만-포드로 음수 사이클을 탐지하는 방법은?

최단 경로는 최대 V-1개의 간선으로 이뤄집니다.

음수 사이클이 없다면 V-1번의 완화로 모든 최단 거리가 확정됩니다. 그 뒤에도 갱신이 되는 간선이 있다면 돌수록 거리가 줄어드는, 출발 정점에서 닿을 수 있는 음수 사이클이 있다는 뜻입니다.