Bellman-Ford: 간선이 음수일 수 있을 때

"Dijkstra는 멀리 갈수록 비용이 더해지기만 한다고 믿어. 음수 간선이 그 믿음을 깨뜨리지. Bellman-Ford는 그런 가정을 아예 하지 않는, 느리지만 참을성 있는 알고리즘이야. 게다가 '가장 싼 경로'라는 게 아예 성립하지 않는 경우까지 잡아내."

Dijkstra가 못 다루는 경우

어떤 간선은 진짜로 음수 가중치를 가져. 이득이 나는 환전, 크레딧으로 들어오는 금융 흐름, 체력을 회복시켜 주는 게임 속 수 같은 것들이지. 여기서 Dijkstra가 실패해. 가장 가까운 노드를 확정해도 안전하다는 핵심 가정이 모든 간선은 비용을 더하기만 한다는 전제 위에 서 있거든. 음수 간선이 있으면 이미 확정한 노드에 나중에 더 싸게 닿는 길이 생길 수 있어. Bellman-Ford는 그 가정을 통째로 버려. 대신 더 느려지는 값을 치르고.

알고리즘: 모든 간선을 V−1번 완화

Bellman-Ford는 거의 무식할 만큼 단순해. 그래프의 모든 간선을 완화하고, 그걸 V−1번 반복해. 간선 u→v를 완화한다는 건 u를 거쳐 v에 닿는 게 v의 현재 거리보다 싸면 값을 갱신한다는 뜻이야. 왜 하필 V−1번일까. 정점이 V개인 그래프에서 최단 경로는 간선을 많아야 V−1개 쓰고, 모든 간선을 한 바퀴 완화할 때마다 올바른 거리가 출발지로부터 간선 하나만큼 더 바깥으로 퍼지는 게 보장되거든. 그러니 V−1바퀴를 돌면 간선을 V−1개까지 쓰는 모든 최단 경로가 완전히 확정돼. 전체는 O(V·E)야. Dijkstra의 O((V+E) log V)보다 느리지만 음수를 견디지.

Bellman-Ford는 모든 간선을 V−1번 완화해. 간선을 V−1개 이하로 쓰는 어떤 최단 경로든 올바른 거리가 퍼지기에 충분한 횟수지. O(V·E)라 Dijkstra보다 느리지만 음수 가중치를 다루고 음의 순환까지 검출해. 기본은 Dijkstra로 가되, 음수가 나올 수 있으면 Bellman-Ford를 꺼내.

초능력: 음의 순환 검출

Bellman-Ford는 출발점에서 도달할 수 있는 음의 순환을 검출할 수 있어. V−1바퀴를 다 돌고도 도달 가능한 간선이 여전히 완화된다면 그런 순환이 있다는 뜻이야. 그 순환에 닿았다가 다시 빠져나갈 수 있는 정점들은 최단 거리가 아예 정의되지 않아. 다만 그래프의 모든 정점이 자동으로 영향을 받는 건 아니라는 것도 같이 기억해. 차익거래에서는 환율 r을 -log(r) 가중치로 바꾸면 곱셈으로 불어나는 이득이 음수 가중치의 합으로 바뀌어서, 음의 순환 검출을 그대로 쓸 수 있어.

피파의 고백

음의 순환은 내 머리를 한참 헤집었어. 최단 경로가 어떻게 음의 무한대일 수가 있지? 아빠가 차익거래 그림을 그려줬어. 달러를 유로로, 유로를 엔으로, 엔을 다시 달러로 바꿨는데 시작보다 돈이 늘어 있는 거야. 그럼 영원히 돌면 무한히 부자가 되고, 언제나 더 싼 게 있으니 '최단'이라는 게 존재하지 않지. Bellman-Ford의 추가 한 바퀴는 변덕이 아니라 '이 질문에는 답이 없다'고 정직하게 보고하는 알고리즘이었어. 불가능하다는 걸 검출하는 게 실패가 아니라 기능이라는 걸 그때 배웠어.

Code

음의 순환까지 잡아내는 Bellman-Ford·python

def bellman_ford(nodes, edges, source):
    """음의 무게 허용 최단 거리. 음의 순환 검출.
    edges: (u, v, weight) 리스트. O(V * E)."""
    dist = {n: float('inf') for n in nodes}
    dist[source] = 0

    # 모든 엣지를 V-1 번 relax.
    for _ in range(len(nodes) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:      # relax: u 거쳐 v 로 더 싼 경로
                dist[v] = dist[u] + w

    # 한 번 더 라운드: 여전히 개선되면, 음의 순환이 있음.
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle detected — no shortest path exists")
    return dist

nodes = ["A", "B", "C", "D"]
edges = [("A","B",4), ("A","C",5), ("B","C",-3), ("C","D",2)]  # B->C 가 음수
print(bellman_ford(nodes, edges, "A"))   # {'A':0,'B':4,'C':1,'D':3} (A->B->C=1)

# 음의 순환은 '최단' 을 무의미하게 만들어:
cyc_nodes = ["X", "Y", "Z"]
cyc_edges = [("X","Y",1), ("Y","Z",-3), ("Z","X",1)]   # 순환 총합 = -1
try: bellman_ford(cyc_nodes, cyc_edges, "X")
except ValueError as e: print(e)   # negative cycle detected

Exercise

Bellman-Ford가 왜 정확히 V−1번의 완화 라운드를 필요로 하는지 직접 설명해 봐. 힌트는 최단 경로가 간선을 최대 몇 개까지 쓸 수 있느냐야. 그다음 V번째 라운드가 어떻게 음의 순환을 잡아내는지 설명하고, 거리보다 그 순환 검출 자체가 진짜 목적인 현실 사례를 하나 들어.

Hint

단순한 최단 경로는 간선을 많아야 V−1개 쓰니까 V−1바퀴면 충분해. 그러고도 출발점에서 도달 가능한 간선이 계속 개선된다면 음의 순환이 있다는 뜻이고. 차익거래가 그 사례인데, 환율을 -log로 바꾸면 곱셈으로 불어나는 이득이 가중치의 합으로 변환돼.

Dijkstra가 못 다루는 경우

알고리즘: 모든 간선을 V−1번 완화

초능력: 음의 순환 검출

피파의 고백

Code

External links

Exercise

Progress

댓글 0