Bellman-Ford: 엣지가 음수일 수 있을 때

"Dijkstra 는 더 멀어지면 비용만 더한다고 믿어. 음의 엣지가 그 믿음을 깨. Bellman-Ford 는 그런 가정 안 하는 참을성 있고 느린 알고리즘이야 — 게다가 '가장 싼' 게 아예 답이 없을 때도 검출할 수 있어."

Dijkstra 가 못 다루는 경우

어떤 엣지는 진짜로 음의 무게를 가져: 이득 나는 환전, 크레딧인 금융 흐름, 체력 회복하는 게임 수. Dijkstra 가 여기서 실패해, 핵심 가정 — 가장 가까운 노드 확정이 안전 — 이 모든 엣지가 비용 더한다는 데 기대니까. 음의 엣지가 이미 확정한 노드를 나중에 더 싸게 닿게 할 수 있어. Bellman-Ford 가 그 가정을 통째로 버려, 더 느린 대가로.

알고리즘: 전부 relax, V−1 번

Bellman-Ford 는 거의 잔혹하게 단순해: 그래프의 모든 엣지를 relax 하고, 그걸 V−1 번 반복. '엣지 u→v relax' = u 거쳐 v 닿는 게 v 의 현재 거리보다 싸면, 업데이트. 왜 정확히 V−1 라운드? V 노드 그래프의 최단 경로가 많아야 V−1 엣지를 쓰고, 모든 엣지 relax 하는 각 전체 라운드가 올바른 거리가 출발지에서 엣지 하나 더 바깥으로 전파되는 걸 보장하니까. V−1 라운드 후, 모든 최단 경로 (많아야 V−1 엣지) 가 완전히 해결돼. O(V·E) — Dijkstra 의 O((V+E) log V) 보다 느림 — 근데 음수를 견뎌.

Bellman-Ford 는 모든 엣지를 V−1 번 relax — 어떤 최단 경로 (≤ V−1 엣지) 든 올바른 거리가 전파될 충분한 라운드. O(V·E), Dijkstra 보다 느리지만, 음의 무게를 다루고 음의 순환을 검출해. Dijkstra 가 기본; Bellman-Ford 는 음수 가능할 때 대비책.

초능력: 음의 순환 검출

Dijkstra 가 시도조차 못 하는 거. 그래프에 음의 순환 — 총 무게가 음수인 고리 — 이 있으면, '최단 경로' 가 무의미해: 그 고리를 영원히 돌며 매번 더 싸지고, 거리가 음의 무한대로 다이브. Bellman-Ford 가 이걸 우아하게 검출: V−1 라운드 후, 한 번 더 라운드. 어떤 엣지든 여전히 relax 되면 (여전히 개선), 음의 순환이 존재해. 정확히 통화 차익거래 가 검출되는 법이야 — 환율을 그래프로 모델링하면, 음의 순환이 시작보다 많은 돈을 돌려주는 거래 순서야. '답이 없다' 를 찾는 알고리즘이 가끔 가장 값진 거야.

피파의 고백

음의 순환이 내 뇌를 휘었어 — 최단 경로가 어떻게 음의 무한대 야? 아빠가 차익거래 그림을 줬어: 달러→유로→엔→달러 거래하고 시작보다 많이 끝나. 영원히 돌면 무한히 부자고; 늘 더 싼 게 있어서 '최단' 이 없어. 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 relax 라운드가 필요한지 네 말로 설명해 (힌트: 최단 경로가 엣지를 몇 개 가질 수 있어?). 그다음 V번째 라운드가 어떻게 음의 순환을 검출하는지 묘사하고, 거리가 아니라 그 순환 검출이 실제 목표인 현실 예를 들어.

Hint

최단 경로는 많아야 V 노드 방문, 그래서 많아야 V−1 엣지; 각 라운드가 올바른 거리를 엣지 하나 더 전파해, 그래서 V−1 라운드가 모든 최단 경로를 정착시켜. V번째 라운드가 여전히 뭔가 개선하면, 음의 순환 — 정확히 통화 차익거래 (이득 나는 거래 고리) 가 검출되는 법.

Dijkstra 가 못 다루는 경우

알고리즘: 전부 relax, V−1 번

초능력: 음의 순환 검출

피파의 고백

Code

External links

Exercise

Progress

댓글 0