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

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

Bellman-Ford 알고리즘이란?

Bellman-Ford 알고리즘은 음의 가중치가 포함될 수 있는 그래프에서 한 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.

핵심 특징

음의 가중치가 있는 그래프에서도 사용 가능
음의 사이클(Negative Cycle) 존재 여부 검출 가능
시간 복잡도: $O(V \times 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]

Python 구현

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 구현

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 구현

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는 Dijkstra가 처리할 수 없는 음수 가중치 그래프에서 최단 경로를 찾고, 음수 사이클을 검출하는 강력한 알고리즘이다.