개발

Bellman-Ford 최단 경로

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

이종관2025년 8월 16일

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

가중 그래프에서 간선 가중치가 음수이면 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단계)

모든 간선을 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, ∞, ∞, ∞, ∞]
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$ 로 발산하기 때문입니다.

flowchart LR
    S["출발점 S"] --> A["음수 사이클 A"]
    A --> B["음수 사이클 B"]
    B --> A
    B --> D["영향받는 정점 D"]
    X["도달 불가 X"] --> Y["도달 불가 음수 사이클 Y"]
    Y --> X

그림에서 A, B, D의 거리는 신뢰할 수 없습니다. S에서 닿지 않는 X, Y는 이번 단일 출발점 문제에 영향을 주지 않습니다. 위 구현은 dist[u] != INF로 출발점에서의 도달 여부를 확인합니다. 사이클을 발견하면 거리 배열 전체를 유효한 결과로 반환하지 않습니다.

응용 분야

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

정리

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

Bellman-Ford는 V-1번의 완화로 최단 거리를 확정하고, 한 번의 추가 검사로 음수 사이클을 판별합니다. 출발점에서 음수 사이클을 거쳐 도달 가능한 정점의 거리는 정의되지 않습니다.

위 구현은 사이클을 발견하면 거리 배열 전체를 실패 결과로 처리합니다. 시간 복잡도는 $O(V \times E)$ 이므로 음수 가중치나 음수 사이클 검출이 필요할 때 선택합니다.

전체 글

개발

Bellman-Ford 최단 경로

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

이종관2025년 8월 16일

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

무엇을 푸는가

한 정점에서 출발해 다른 모든 정점까지의 최단 경로를 찾습니다. 간선 가중치에 음의 값이 섞여 있어도 동작하는 점이 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단계)

모든 간선을 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, ∞, ∞, ∞, ∞]
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 구현

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
}

음수 사이클이 있을 때

flowchart LR
    S["출발점 S"] --> A["음수 사이클 A"]
    A --> B["음수 사이클 B"]
    B --> A
    B --> D["영향받는 정점 D"]
    X["도달 불가 X"] --> Y["도달 불가 음수 사이클 Y"]
    Y --> X

응용 분야

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

정리

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