Dijkstra·완화·오래된 큐 항목

큐와 너비 우선 탐색 BFS는 간선의 개수가 가장 적은 길을 찾았습니다. 하지만 내비게이션이 찾아야 하는 것은 거치는 도로의 개수가 아니라 걸리는 시간의 합이 가장 적은 길입니다. 짧은 도로 여러 개를 지나는 길이 긴 도로 하나를 지나는 길보다 빠를 수 있기 때문입니다. 간선마다 비용이 붙은 그래프에서 한 출발점으로부터 모든 정점까지 비용의 합이 가장 적은 길을 찾는 대표적인 방법이 Dijkstra 알고리즘입니다. 1956년 Edsger Dijkstra가 고안한 이 방법은 오늘날에도 지도 서비스와, 라우터가 네트워크 지도를 나누어 갖고 각자 최단 경로를 계산하는 OSPF 같은 링크 상태 라우팅의 기초로 쓰입니다. 이 글에서는 힙을 이용해 Dijkstra 알고리즘을 만들고, 왜 맞는지, 어떤 조건에서만 맞는지를 설명합니다.

간선 수가 아니라 비용의 합

아래 그래프는 방향 간선마다 비용이 붙어 있습니다. 간선에 붙은 이 수가 앞 장에서 말한 가중치(weight)이고, 아래 코드에서도 weight라는 이름으로 씁니다. 이 글에서는 걸리는 시간처럼 작을수록 좋은 값이라는 뜻에서 비용이라고 부르겠습니다. A에서 D까지 가는 길 가운데 간선이 가장 적은 것은 A→B→D 또는 A→C→D로 두 개이지만, 비용은 각각 4 + 1 = 5와 1 + 5 = 6입니다. 간선 세 개를 지나는 A→C→B→D는 비용이 1 + 2 + 1 = 4로 가장 적습니다. 시작 정점에서 어떤 정점까지 가는 길 가운데 비용의 합이 가장 적은 길을 최단 경로(shortest path)라 하고, 그 비용의 합을 최단 거리라고 하겠습니다.

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

Dijkstra 알고리즘은 정점마다 지금까지 찾은 가장 싼 비용을 distance에 기록해 둡니다. 처음에는 시작 정점이 0이고 나머지는 아직 길을 모르므로 무한대입니다. 어떤 정점 u까지의 비용을 알고 있을 때 간선 u→v의 비용이 w라면, u를 거쳐 v로 가는 비용은 distance[u] + w입니다. 이 값이 지금 기록된 distance[v]보다 작으면 더 싼 길을 찾은 것이므로 distance[v]를 고치고, v에 어느 정점을 거쳐 왔는지 parent[v] = u로 기록합니다. 이렇게 기록된 비용을 줄여 나가는 일을 완화(relaxation)라고 합니다.

완화는 순서가 중요합니다. 예제에서 A를 처리하면 B까지의 비용이 4로 기록되지만, 나중에 C를 처리할 때 C→B를 완화하면 1 + 2 = 3이 되어 4보다 작으므로 B가 3으로 고쳐집니다. 그런데 B를 4인 채로 먼저 처리해 D를 4 + 1 = 5로 기록해 버리면, B가 3으로 고쳐진 뒤 D도 다시 고쳐야 합니다. 정점마다 비용이 더는 줄지 않는다고 확신할 수 있을 때 처리해야 일을 되풀이하지 않습니다.

가장 가까운 정점부터 확정한다

Dijkstra 알고리즘의 핵심 생각은 아직 처리하지 않은 정점 가운데 기록된 비용이 가장 작은 정점은 그 비용이 최종이라는 것입니다. 그 정점에 더 싸게 가는 길이 있다면, 그 길은 아직 처리하지 않은 다른 정점을 거쳐야 합니다. 그런데 그 다른 정점까지의 비용이 이미 이 정점보다 작지 않고, 간선 비용은 음수가 아니므로 거기서 더 가면 비용이 줄어들 수 없습니다. 그래서 가장 작은 정점을 꺼내 확정하고 그 정점에서 나가는 간선들을 완화하는 일을 되풀이하면, 정점들이 가까운 순서대로 하나씩 확정됩니다.

가장 작은 비용의 정점을 빠르게 꺼내려고 최소 힙을 씁니다. 힙에는 (비용, 정점) 튜플을 넣으므로 비용이 가장 작은 항목이 먼저 나옵니다. 그런데 Python의 heapq에는 이미 들어 있는 항목의 비용을 줄이는 기능이 없습니다. 그래서 완화로 비용이 줄 때마다 새 항목을 하나 더 넣고, 예전 항목은 힙에 그대로 둡니다. 나중에 예전 항목을 꺼내면 그 비용이 distance에 기록된 값과 다르므로, 이미 더 싼 비용으로 처리된 오래된 항목이라고 보고 건너뜁니다.

예제 그래프에서 A부터 시작하면 힙에서 항목이 다음 순서로 나옵니다.

B는 A를 처리할 때 4로 한 번, C를 처리할 때 3으로 한 번 힙에 들어갔습니다. 힙은 비용이 작은 (3, B)를 먼저 내놓으므로 B는 3으로 처리되고, 나중에 나온 (4, B)는 건너뜁니다. D도 같은 방식으로 6이 아니라 4로 처리됩니다.

코드로 옮기기

그래프는 정점마다 (이웃, 비용) 튜플의 리스트를 둔 인접 목록으로 나타냅니다. 비용이 음수인 간선이 있으면 이 알고리즘이 맞지 않으므로 시작하기 전에 거절합니다. 그 이유는 뒤에서 설명합니다. math.inf는 어떤 수보다도 큰 무한대 값이라서, 아직 길을 모르는 정점의 비용으로 씁니다.

import heapq
import math


def dijkstra(graph, start):
    for edges in graph.values():
        for _, weight in edges:
            if weight < 0:
                raise ValueError("음수 비용의 간선은 다룰 수 없습니다")
    distance = {vertex: math.inf for vertex in graph}
    distance[start] = 0
    parent = {start: None}
    queue = [(0, start)]
    while queue:
        cost, vertex = heapq.heappop(queue)
        if cost != distance[vertex]:
            continue
        for target, weight in graph[vertex]:
            candidate = cost + weight
            if candidate < distance[target]:
                distance[target] = candidate
                parent[target] = vertex
                heapq.heappush(queue, (candidate, target))
    return distance, parent


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


graph = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": [], "E": []}
distance, parent = dijkstra(graph, "A")
print(distance)
print(restore_path(parent, "D"), restore_path(parent, "E"))

{'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': inf}
['A', 'C', 'B', 'D'] []

D까지의 최단 거리는 4이고 경로는 A, C, B, D입니다. E는 A에서 가는 간선이 없어 거리가 inf로 남고, parent에도 없으므로 경로는 빈 리스트입니다. 경로 복원은 BFS와 같은 방식으로, 마지막으로 완화한 정점이 parent에 남아 있으므로 그것을 따라 거슬러 올라가면 최단 경로가 됩니다.

candidate < distance[target]에서 같은 비용일 때는 고치지 않습니다. 그래서 비용이 같은 다른 길을 찾아도 처음 기록한 부모가 그대로 남고, 비용이 0인 간선으로 이루어진 사이클이 있어도 같은 정점을 끝없이 다시 넣지 않습니다. 비용이 0인 간선 자체는 음수가 아니므로 문제없이 다룰 수 있습니다.

왜 맞는가

오래된 항목이 아닌 항목 (d, u)를 꺼냈을 때 d가 u까지의 최단 거리라는 것을 보이면 됩니다. 이미 처리를 마친 정점들의 집합을 S라고 하고, S의 정점들은 모두 최단 거리로 처리되었다고 합시다. 시작 정점에서 u까지 가는 아무 길을 하나 생각하면, 그 길은 S 안에서 출발해 어디선가 처음으로 S 밖의 정점 x에 들어섭니다. x 바로 앞의 정점은 S에 있으므로 이미 처리되면서 x로 가는 간선을 완화했고, 그래서 x의 기록된 비용은 그 길에서 x까지의 비용 이하입니다.

그런데 힙은 기록된 비용이 가장 작은 항목을 먼저 내놓으므로, 지금 꺼낸 d는 x의 기록된 비용 이하입니다. 또 간선 비용이 음수가 아니므로, 그 길에서 x 다음으로 u까지 더 가는 동안 비용은 줄지 않습니다. 정리하면 d는 x의 기록된 비용 이하, 그것은 그 길에서 x까지의 비용 이하, 그것은 그 길 전체의 비용 이하입니다. 어떤 길을 골라도 d보다 싸지 않으므로 d가 최단 거리입니다. 각 정점은 최단 거리로 한 번만 처리되고 힙에 넣는 항목은 완화할 때마다 하나씩이므로, 넣은 항목을 모두 꺼내면 알고리즘이 끝납니다.

음수 비용이 있으면

증명에서 "간선 비용이 음수가 아니므로 비용이 줄지 않는다"는 부분이 핵심이었습니다. 음수 비용이 있으면 이 부분이 깨집니다. 간선 A→B가 2, A→C가 5, C→B가 -10인 그래프를 생각해 봅시다. A를 처리하면 B가 2, C가 5로 기록되고, 힙에서 B가 먼저 나와 2로 확정됩니다. 하지만 실제 B까지의 최단 거리는 A→C→B의 5 + (-10) = -5입니다. 가장 가까워 보였던 B에, 더 멀어 보이는 C를 거쳐 더 싸게 갈 수 있었던 것입니다.

이 글의 코드처럼 오래된 항목을 건너뛰는 방식은 B를 나중에 -5로 다시 넣고 다시 처리해서 이 예에서는 답을 고칠 수 있습니다. 그러나 그러면 "한 정점을 한 번만 처리한다"는 성질이 사라져 같은 정점을 몇 번 처리할지 한계가 없어지고, 입력에 따라 매우 느려질 수 있습니다. 비용의 합이 음수인 사이클이 있으면 그 사이클을 돌수록 비용이 끝없이 줄어 아예 끝나지 않습니다. 그래서 이 코드는 음수 비용을 처음부터 거절합니다. 음수 비용이 있는 그래프에는 Bellman–Ford 알고리즘이나, 이 장 마지막 글의 Floyd–Warshall처럼 음수를 다룰 수 있는 방법을 씁니다.

비용

각 정점은 한 번만 처리되고, 처리할 때 나가는 간선을 한 번씩 완화합니다. 완화가 성공할 때마다 힙에 항목을 하나 넣으므로 힙에는 많아야 E + 1개의 항목이 들어가고, 넣고 꺼낼 때마다 O(log E)가 듭니다. 단순 그래프에서는 E가 V²보다 작아 log E가 O(log V)이므로, 전체 시간은 흔히 O((V + E) log V)로 씁니다. 공간은 거리와 부모와 힙을 합해 O(V + E)입니다.

더 깊이: 힙 없이 만들면

힙을 쓰지 않고, 매번 처리하지 않은 정점 전체를 훑어 기록된 비용이 가장 작은 정점을 찾을 수도 있습니다. 이때는 정점 하나를 고르는 데 O(V)가 들고 이 일을 V번 하므로 전체가 O(V²)입니다. 간선이 적은 그래프에서는 O((V + E) log V)보다 느리지만, 거의 모든 정점 쌍 사이에 간선이 있어 E가 V²에 가까운 그래프에서는 O(V² log V)보다 오히려 빠릅니다. Dijkstra가 처음 발표한 방법도 이렇게 힙 없이 고르는 방식이었습니다. 어떤 자료구조로 가장 가까운 정점을 고르느냐에 따라 같은 알고리즘의 비용이 달라지는 것입니다.

정리

• Dijkstra 알고리즘은 간선 비용이 음수가 아닌 그래프에서 한 시작 정점으로부터 모든 정점까지의 최단 거리와 최단 경로를 구합니다.
• 완화는 u를 거쳐 v로 가는 비용이 기록된 비용보다 작을 때 distance[v]와 parent[v]를 고치는 일입니다.
• 처리하지 않은 정점 가운데 기록된 비용이 가장 작은 정점은 비용이 최종이므로, 최소 힙에서 꺼내 확정하고 나가는 간선을 완화합니다.
• 비용이 줄 때마다 힙에 새 항목을 넣고, 기록된 비용과 다른 오래된 항목은 꺼낼 때 건너뜁니다.
• 음수 비용이 있으면 가장 가까운 정점을 확정하는 논리가 깨지므로 다른 알고리즘을 씁니다. 힙을 쓴 구현은 O((V + E) log V)입니다.

연습 문제

1. 음수 비용에서 틀리는 곳

간선 A→B가 2, A→C가 5, C→B가 -10일 때, 정점을 꺼내는 순간 확정하는 Dijkstra 알고리즘은 B를 몇으로 확정하고, 실제 최단 거리는 얼마인가요? 본문의 dijkstra에 이 그래프를 넣으면 어떻게 되나요?

2. 닿을 수 없는 정점

본문 예제에서 E의 거리와 restore_path(parent, "E")의 결과는 무엇이고, 각각 무엇을 뜻하나요?

3. BFS와 Dijkstra가 고르는 길

간선 A→C의 비용이 100, A→B와 B→C의 비용이 각각 1일 때, A에서 C까지 BFS가 찾는 길과 Dijkstra 알고리즘이 찾는 길은 각각 무엇인가요?

간선 비용이 음수가 아니라는 조건과 증명은 MIT 강의 Introduction to Algorithms의 Dijkstra 강의에서도 확인할 수 있습니다. 다음 글 Warshall과 도달 가능성의 논리에서는 비용 대신 갈 수 있는지만을, 한 출발점이 아니라 모든 정점 쌍에 대해 한꺼번에 구합니다.