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

Bellman-Ford 알고리즘이란?

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

핵심 특징

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

Dijkstra vs Bellman-Ford

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

알고리즘 아이디어

1단계: 거리 갱신 (Relaxation)

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

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

V-1번 반복하는 이유: 최단 경로의 간선 최대 개수가 V-1개

2단계: 음수 사이클 검출

V-1번 반복 후, 추가로 한 번 더 간선을 확인했을 때 갱신이 발생하면 음수 사이클 존재

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

예시 그래프

간선 (방향 그래프):
0 → 1 (6)    1 → 4 (-4)   3 → 1 (-2)
0 → 2 (7)    2 → 3 (-3)   4 → 0 (2)
1 → 2 (8)    2 → 4 (9)    4 → 3 (7)
1 → 3 (5)

동작 과정 (시작: 0)

반복	dist[1]	dist[2]	dist[3]	dist[4]
초기	∞	∞	∞	∞
1회	2	7	4	2
2회	2	7	4	-2
3회	2	7	4	-2

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

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

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
}

음수 사이클이 있을 때

음수 사이클에 도달 가능한 모든 정점은 최단 거리가 **-∞**로 정의되지 않습니다. (값이 계속 줄어듦)

응용 분야

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

정리

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

Bellman-Ford는 Dijkstra가 처리할 수 없는 음수 가중치 그래프에서 최단 경로를 찾고, 음수 사이클을 검출하는 강력한 알고리즘입니다.