최단 경로와 단계별 갱신

지도에서 길을 찾을 때 거치는 도로의 개수가 적은 길이 꼭 가장 빠른 길은 아닙니다. 짧은 도로 여러 개가 긴 도로 하나보다 빠를 수 있기 때문입니다. 그래프로 말하면, 간선 수가 가장 적은 경로와 간선에 붙은 비용의 합이 가장 작은 경로는 다를 수 있습니다. 이 글에서는 그래프의 모델과 표현의 가중치 그래프에서 비용이 가장 작은 경로를 찾는 방법과, 그 방법이 맞는 이유를 다룹니다.

간선 수와 비용의 합

간선에 가중치가 없거나 모든 가중치가 같으면, 가장 짧은 경로는 간선 수가 가장 적은 경로입니다. 이 경우는 출발점에서 가까운 정점부터 차례로 방문하는 너비 우선 탐색으로 구할 수 있으며, 다음 글에서 다룹니다.

가중치가 서로 다르면 경로의 길이를 간선 가중치의 합으로 정합니다. 출발점 s에서 v까지 가는 보행의 비용 가운데 가장 작은 값을 s에서 v까지의 거리라 하고, 그 값을 내는 경로를 최단 경로(shortest path)라고 합니다. 가중치가 0 이상이면 보행에서 반복되는 구간을 빼도 비용이 늘지 않으므로, 가장 싼 보행 가운데 정점을 반복하지 않는 경로가 언제나 있습니다. 무방향 간선 AB = 2, AC = 5, BC = 1, BD = 6, CD = 2인 그래프에서 A에서 D까지 가는 경로를 비교해 보겠습니다.

간선을 가장 많이 쓰는 A → B → C → D가 비용으로는 가장 작습니다. 간선 수만 줄이는 방법으로는 이 경로를 찾을 수 없습니다.

완화: 더 싼 길을 찾으면 고친다

최단 경로 알고리즘은 정점마다 지금까지 찾은 가장 작은 비용을 적어 두고, 더 싼 길을 찾을 때마다 고칩니다. 출발점은 0, 나머지는 아직 길을 모른다는 뜻으로 ∞에서 시작합니다. 간선 u → v의 가중치가 w일 때 u까지의 값에 w를 더한 것이 v의 값보다 작으면 v의 값을 그 합으로 바꾸는데, 이 갱신을 완화(relaxation)라고 합니다. 완화는 값을 줄이기만 하고, 적어 둔 값은 언제나 실제로 갈 수 있는 어떤 길의 비용입니다.

Dijkstra 알고리즘은 아직 확정하지 않은 정점 가운데 적어 둔 값이 가장 작은 정점을 골라 확정하고, 그 정점에서 나가는 간선을 모두 완화하는 일을 반복합니다. 위 그래프에서 A부터 시작하면 표는 다음과 같이 바뀝니다.

A를 확정하면 B가 2, C가 5가 됩니다. 다음으로 값이 가장 작은 B를 확정하고, B를 거쳐 C를 2 + 1 = 3으로, D를 2 + 6 = 8로 고칩니다. 이어서 C를 확정하면 C를 거쳐 D가 3 + 2 = 5로 줄어듭니다. 값만 적어 두면 어떤 길로 갔는지 잊으므로, 완화할 때 직전 정점도 함께 적어 둡니다.

from heapq import heappop, heappush


def dijkstra(graph, start):
    if any(weight < 0 for edges in graph.values() for _, weight in edges):
        raise ValueError("음수 가중치는 허용하지 않습니다")
    distance = {v: float("inf") for v in graph}
    distance[start] = 0
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        cost, v = heappop(heap)
        if cost != distance[v]:
            continue
        for u, weight in graph[v]:
            candidate = cost + weight
            if candidate < distance[u]:
                distance[u] = candidate
                parent[u] = v
                heappush(heap, (candidate, u))
    return distance, parent


def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]


graph = {"A": [("B", 2), ("C", 5)],
         "B": [("A", 2), ("C", 1), ("D", 6)],
         "C": [("A", 5), ("B", 1), ("D", 2)],
         "D": [("B", 6), ("C", 2)]}
distance, parent = dijkstra(graph, "A")
print(distance)
print(" → ".join(path_to(parent, "D")))
try:
    dijkstra({"A": [("B", 1), ("C", 2)], "B": [], "C": [("B", -3)]}, "A")
except ValueError as error:
    print("오류:", error)

{'A': 0, 'B': 2, 'C': 3, 'D': 5}
A → B → C → D
오류: 음수 가중치는 허용하지 않습니다

heapq의 힙은 넣은 항목 가운데 가장 작은 것을 빠르게 꺼내 주므로, 값이 가장 작은 정점을 고르는 데 씁니다. 한 정점의 값이 여러 번 줄어들면 힙에 그 정점의 항목이 여러 개 남는데, 꺼낸 비용이 지금 적힌 값과 다르면 예전 항목이므로 건너뜁니다. parent는 각 정점의 직전 정점을 적어 두고, path_to는 도착점에서 직전 정점을 거꾸로 따라간 뒤 순서를 뒤집어 경로를 만듭니다. 힙과 예전 항목을 다루는 방법은 자료구조·알고리즘 교재의 Dijkstra·완화·오래된 큐 항목에서 더 자세히 다룹니다.

Dijkstra 알고리즘이 맞는 이유

가중치가 모두 0 이상이면, 확정하는 순간의 값이 실제 거리라는 것을 보일 수 있습니다. 앞서 확정한 정점들의 값은 실제 거리라고 가정하고, 확정되지 않은 정점 가운데 값이 가장 작은 u를 확정하려 한다고 합시다. 출발점에서 u로 가는 아무 경로나 하나 잡고 따라가면, 확정된 정점들 안에서 출발해 어딘가에서 처음으로 확정되지 않은 정점 y로 넘어갑니다. 넘어가기 직전의 정점 x는 확정되면서 x → y를 완화했으므로, 이 경로에서 y까지의 비용은 y에 적힌 값 이상이고, 그 값은 u의 값 이상입니다. y에서 u까지 남은 부분은 가중치가 0 이상이라 비용을 줄이지 못하므로, 어떤 경로도 u에 적힌 값보다 싸지 않습니다.

이 증명에서 "남은 부분이 비용을 줄이지 못한다"는 데 가중치가 0 이상이라는 조건을 썼습니다. 방향 간선 A → B = 1, A → C = 2, C → B = −3인 그래프에서는 이 조건이 깨집니다. A를 확정하면 B가 1, C가 2가 되고, 값이 작은 B를 먼저 확정합니다. 그런데 나중에 C를 거치면 A → C → B의 비용이 2 + (−3) = −1이라 확정한 값보다 작습니다. 확정한 정점을 다시 고치지 않는 Dijkstra 알고리즘은 B의 거리를 1로 잘못 내놓습니다.

위 코드처럼 값이 줄어든 정점을 힙에 다시 넣는 구현은 이 작은 예에서 우연히 −1을 찾기도 합니다. 하지만 한 번 꺼낸 정점의 값이 다시 바뀐다는 것은 확정이라는 생각이 무너졌다는 뜻이고, 맞는다는 증명도 실행 시간의 한계도 더는 성립하지 않습니다. 그래서 코드는 음수 가중치를 처음부터 거절합니다.

모든 쌍의 최단 거리

모든 정점 쌍의 거리가 필요하면 Floyd–Warshall 알고리즘을 쓸 수 있습니다. n × n 거리 행렬 D를 대각선은 0, 간선이 있는 자리는 그 가중치, 간선이 없는 자리는 ∞로 채운 뒤, 정점 k를 중간에 거쳐도 되도록 하나씩 허용하며 $D_{ij}\leftarrow\min(D_{ij},D_{ik}+D_{kj})$로 고칩니다. 관계와 그래프를 계산하는 행렬의 Warshall 알고리즘에서 OR를 최솟값으로, AND를 덧셈으로 바꾼 것입니다. k번째 단계의 갱신이 맞으려면 모든 i, j에 대해 $D_{ik}$와 $D_{kj}$에 중간에 정점 1부터 k − 1까지만 거치는 가장 싼 비용이 이미 적혀 있어야 하므로, k가 가장 바깥 반복이어야 합니다. 앞의 그래프로 계산하면 다음 표가 나옵니다.

A의 행은 Dijkstra 알고리즘으로 구한 값과 같습니다. 무방향 그래프라서 표가 대칭이고, B에서 D까지는 직접 가는 간선 6보다 C를 거치는 1 + 2 = 3이 작습니다. 세 겹의 반복이 각각 n번씩 돌므로 계산량은 $n^3$에 비례합니다.

Floyd–Warshall 알고리즘은 음수 간선이 있어도 쓸 수 있지만, 비용의 합이 음수인 사이클이 있으면 문제가 달라집니다. 그 사이클을 한 바퀴 돌 때마다 비용이 줄어들므로, 사이클을 거쳐 갈 수 있는 두 정점 사이에는 가장 작은 비용이 정해지지 않습니다. 계산을 마친 뒤 대각선에 음수가 있으면 그 정점을 지나는 음수 사이클이 있다는 뜻이므로 결과를 거리로 읽으면 안 됩니다. 코드와 음수 사이클의 판정은 자료구조·알고리즘 교재의 Floyd–Warshall과 음수 사이클에서 다룹니다.

정리

• 가중치 그래프에서 경로의 길이는 간선 가중치의 합이고, 간선 수가 가장 적은 경로와 비용이 가장 작은 경로는 다를 수 있습니다.
• 완화는 u까지의 값에 간선 u → v의 가중치를 더한 것이 v의 값보다 작을 때 v의 값을 고치는 일이며, 직전 정점을 함께 적어 두면 경로를 되찾을 수 있습니다.
• Dijkstra 알고리즘은 값이 가장 작은 정점을 확정하고 그 정점의 간선을 완화하는 일을 반복합니다. 가중치가 모두 0 이상이면 확정한 값이 실제 거리입니다.
• 음수 간선이 있으면 나중에 찾은 길이 확정한 값보다 작을 수 있으므로 Dijkstra 알고리즘의 증명이 성립하지 않습니다.
• Floyd–Warshall 알고리즘은 중간 정점을 하나씩 허용하며 $D_{ij}\leftarrow\min(D_{ij},D_{ik}+D_{kj})$로 모든 쌍의 거리를 구하고, 대각선의 음수로 음수 사이클을 알아냅니다.

연습 문제

1. 거리가 줄어든 단계

Dijkstra 표에서 D의 값이 8에서 5로 바뀐 것은 어느 정점을 확정한 단계이고, 그때 D의 직전 정점은 어떻게 바뀌나요?

2. 최단 경로가 둘일 때

간선 BD의 가중치를 6에서 3으로 바꾸면 A에서 D까지의 거리와 코드가 돌려주는 경로는 무엇인가요?

3. 음수 사이클

방향 간선 A → B = 1, B → C = −2, C → A = 0인 그래프에서 A에서 C까지의 최단 거리는 얼마인가요?

결과가 이상하면 가중치에 음수가 있는지, 간선이 없는 자리를 0이 아니라 ∞로 적었는지부터 확인해 보세요. 다음 글 깊이 우선 탐색과 너비 우선 탐색에서는 비용 없이 간선만 따라 그래프 전체를 훑는 두 가지 순서를 비교합니다.