Bellman-Ford 알고리즘: 음수 가중치 최단 경로

음수 가중치 그래프에서 최단 경로를 구하고 음수 사이클까지 검출하는 알고리즘이다.

가중 그래프에서 최단 경로를 구할 때, 간선 가중치가 음수이면 Dijkstra 알고리즘을 적용할 수 없다. Bellman-Ford 알고리즘은 음수 가중치를 허용하면서도 최단 경로를 구하고, 음수 사이클의 존재까지 감지하는 알고리즘이다.

무엇을 푸는가

한 정점에서 출발해 다른 모든 정점까지의 최단 경로를 찾는다. 간선 가중치에 음의 값이 섞여 있어도 동작하는 점이 Dijkstra와 다르다.

핵심 특징

음의 가중치가 있는 그래프에서도 사용 가능
음의 사이클(Negative Cycle) 존재 여부 검출 가능
시간 복잡도: $O(V \times E)$ (V는 정점 수, E는 간선 수)

Dijkstra vs Bellman-Ford

특성	Dijkstra	Bellman-Ford
시간복잡도	$O(E \log V)$	$O(V \times E)$
음수 가중치	불가	가능
음수 사이클 검출	불가	가능

알고리즘 아이디어

1단계: 거리 갱신 (Relaxation)

모든 간선을 V-1번 반복하며 거리를 갱신한다.

Relaxation(완화)은 현재까지 알려진 최단 거리보다 더 짧은 경로를 발견하면 거리 값을 갱신하는 연산이다.

python

for i in range(V-1):
    for (u, v, w) in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

V-1번 반복하는 이유: 최단 경로에 포함되는 간선은 최대 V-1개이기 때문이다.

2단계: 음수 사이클 검출

V-1번 반복 후 한 번 더 간선을 확인한다. 이때 갱신이 한 번이라도 발생하면 음수 사이클이 존재한다.

python

for (u, v, w) in edges:
    if dist[u] + w < dist[v]:
        return "음수 사이클 존재"

예시 그래프

from	to	weight
0	1	6
0	2	7
1	2	8
1	3	5
1	4	-4
2	3	-3
2	4	9
3	1	-2
4	0	2
4	3	7

동작 과정 (시작: 0)

초기: [0, ∞, ∞, ∞, ∞]
1회 반복 후: [0, 2, 7, 4, 2]
2회 반복 후: [0, 2, 7, 4, -2]
3회 반복 후: [0, 2, 7, 4, -2]

결과: [0, 2, 7, 4, -2]

위 패스별 중간값은 아래 edges 순서로 갱신한 결과이며, 간선 순서가 바뀌면 패스별 중간값도 달라질 수 있다. 최종 결과는 같다.

Python 구현

bellman_ford(start, n, edges)는 시작 정점 start, 정점 수 n, 간선 목록 edges를 받는다. INF로 초기화한 거리 배열에서 출발점만 0으로 두고, (dist, has_negative_cycle) 튜플을 돌려준다. has_negative_cycle이 True면 거리 배열은 신뢰할 수 없다.

python

import sys
 
def bellman_ford(start, n, edges):
    INF = sys.maxsize
    dist = [INF] * n
    dist[start] = 0
 
    # V-1번 반복
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    # 음수 사이클 검출
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return dist, True  # 음수 사이클 존재
 
    return dist, False
 
 
# 실행
edges = [
    (0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5),
    (1, 4, -4), (2, 3, -3), (2, 4, 9),
    (3, 1, -2), (4, 0, 2), (4, 3, 7)
]
 
dist, has_negative_cycle = bellman_ford(0, 5, edges)
 
if has_negative_cycle:
    print("음수 사이클 존재")
else:
    print(f"최단 거리: {dist}")

Java 구현

로직은 Python과 같고, 음수 사이클을 만나면 bool을 반환하는 대신 예외를 던진다.

java

import java.util.*;
 
public class BellmanFord {
    static class Edge {
        int u, v, w;
        Edge(int u, int v, int w) {
            this.u = u; this.v = v; this.w = w;
        }
    }
 
    public static int[] bellmanFord(int start, int n, List<Edge> edges) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
 
        // V-1번 반복
        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.u] != Integer.MAX_VALUE &&
                    dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                }
            }
        }
 
        // 음수 사이클 검출
        for (Edge e : edges) {
            if (dist[e.u] != Integer.MAX_VALUE &&
                dist[e.u] + e.w < dist[e.v]) {
                throw new RuntimeException("Negative cycle detected");
            }
        }
 
        return dist;
    }
}

Go 구현

Python과 동일하게 (dist, bool)을 반환하고, 무한대 자리에 math.MaxInt32를 쓴다.

func BellmanFord(start, n int, edges []Edge) ([]int, bool) {
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[start] = 0
 
    // V-1번 반복
    for i := 0; i < n-1; i++ {
        for _, e := range edges {
            if dist[e.u] != math.MaxInt32 &&
               dist[e.u]+e.w < dist[e.v] {
                dist[e.v] = dist[e.u] + e.w
            }
        }
    }
 
    // 음수 사이클 검출
    for _, e := range edges {
        if dist[e.u] != math.MaxInt32 &&
           dist[e.u]+e.w < dist[e.v] {
            return dist, true
        }
    }
 
    return dist, false
}

음수 사이클이 있을 때

음수 사이클에 도달 가능한 정점의 최단 거리는 $-\infty$ 로 발산하므로 정의되지 않는다. (반복할수록 값이 계속 줄어든다)

응용 분야

분야	활용
금융/경제	환율 차익 거래 기회 검출
네트워크	음수 비용 포함 라우팅
게임	음수 효과 포함 경로 계산

정리

V-1번 반복으로 거리 갱신
추가 1회 검사로 음수 사이클 판별
시간복잡도 $O(V \times E)$ 로 대규모 그래프에서는 비효율적
음수 가중치가 필요한 상황에서 기본 선택지

Bellman-Ford는 V-1번의 완화로 최단 거리를 확정하고, 한 번의 추가 검사로 음수 사이클을 판별한다. 음수 사이클에 도달 가능한 정점은 거리가 발산하므로 별도로 표시한다. 시간 복잡도가 $O(V \times E)$ 여서 간선이 많은 대규모 그래프에서는 느리다. 음수 가중치가 없다면 Dijkstra가 더 빠르므로, 음수 가중치나 음수 사이클 검출이 필요할 때 선택한다.