최단 경로와 최소 신장 트리 안내서 · 6/6

실무 활용

최단 경로와 신장 트리는 가장 널리 쓰이는 그래프 알고리즘에 속합니다. 이 장에서는 실제로 어디에서 돌아가는지, 어떤 라이브러리를 쓰면 되는지, 틀린 답을 내는 흔한 실수가 무엇인지 살펴봅니다.

쓰이는 곳

네트워크 라우팅: OSPF, IS-IS 같은 링크 상태 프로토콜은 모든 라우터에 네트워크 지도를 나눠 주고, 각 라우터가 다익스트라로 전달 테이블을 만듭니다. RIP 같은 거리 벡터 프로토콜은 벨만-포드를 분산해서 돌리는 형태입니다.
지도와 길찾기: 도로망은 정점이 수백만 개라서 실제 서비스는 다익스트라 위에 전처리를 더합니다. A*는 남은 거리 추정치로 목적지 쪽을 먼저 탐색하고, 축약 계층(contraction hierarchies)은 지름길을 미리 계산해 두어 질의가 그래프의 아주 작은 부분만 보게 합니다.
게임과 로봇: 격자나 내비게이션 메시 위의 경로 찾기는 대개 A*나 다익스트라이며, 비용 없는 이동이 섞이면 0-1 BFS가 쓰입니다.
네트워크 설계: MST는 케이블, 배관, 도로로 지점들을 잇는 가장 싼 방법이고, 메트릭 외판원 문제 같은 어려운 문제를 근사하는 출발점이기도 합니다(MST 기반 순회는 최적의 2배 이하).
군집화: 크루스칼을 돌리다가 컴포넌트가 k개 남았을 때 멈추면 단일 연결(single-linkage) 군집화가 됩니다. 흔히 쓰는 계층적 군집화 방법입니다.
금융: 가중치를 -log(환율)로 두면 벨만-포드가 찾은 음수 사이클이 곧 환율 차익 거래 고리입니다.

라이브러리

Python에서는 NetworkX가 프로토타입이나 간선 수십만 개 정도까지의 그래프에 편리합니다.

import networkx as nx

G = nx.Graph()
G.add_weighted_edges_from([("A", "B", 1), ("B", "C", 2), ("A", "C", 3), ("C", "D", 4), ("B", "D", 5)])

print(nx.dijkstra_path(G, "A", "D"))  # ['A', 'B', 'D']
print(nx.dijkstra_path_length(G, "A", "D"))  # 6
mst = nx.minimum_spanning_tree(G, algorithm="kruskal")
print(sorted(mst.edges(data="weight")))  # [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 4)]

큰 수치 그래프라면 SciPy의 scipy.sparse.csgraph가 희소 행렬 위에서 컴파일된 코드로 동작합니다.

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra, minimum_spanning_tree

m = csr_matrix(np.array([
    [0, 1, 3, 0],
    [1, 0, 2, 5],
    [3, 2, 0, 4],
    [0, 5, 4, 0],
]))
dist = dijkstra(m, directed=False, indices=0)
print(dist)  # [0. 1. 3. 6.]
print(minimum_spanning_tree(m).sum())  # 7.0

C++에서는 Boost Graph Library가 dijkstra_shortest_paths, bellman_ford_shortest_paths, kruskal_minimum_spanning_tree, prim_minimum_spanning_tree를 제공합니다. 데이터베이스 쪽에서는 Neo4j의 Graph Data Science 라이브러리와 PostgreSQL의 pgRouting 확장이 데이터 가까이에서 이 알고리즘들을 돌립니다.

흔한 실수

음수 간선에 다익스트라 쓰기. 오류가 나지 않고 조용히 틀린 거리를 돌려줍니다. 입력을 검사하거나 벨만-포드를 씁니다.
낡은 항목 검사 if d > dist[u] 빠뜨리기. 결과는 맞지만 밀집 그래프에서 크게 느려질 수 있습니다.
무방향 간선을 한쪽 방향으로만 넣기.
오버플로: C++나 Java에서는 INF + w가 값이 넘쳐 음수가 됩니다. 거리가 아직 무한대인 정점에서는 완화하지 말고 64비트 정수를 씁니다.
실수 가중치: 소수의 합은 정확하지 않으므로 비교에 주의하거나 정수 단위(원, 밀리초)로 바꿉니다.
힙의 동점: Python은 튜플을 앞에서부터 비교합니다. 거리가 같은 두 항목의 두 번째 값이 비교할 수 없는 객체라면 heappush가 TypeError를 냅니다. 카운터를 동점 처리용으로 끼워 넣습니다.

import heapq
from itertools import count

tie = count()
heap = []
heapq.heappush(heap, (5, next(tie), {"name": "warehouse"}))
heapq.heappush(heap, (5, next(tie), {"name": "store"}))  # TypeError 없음: 카운터가 순서를 정함
print(heapq.heappop(heap)[2])  # {'name': 'warehouse'}

연결되지 않은 그래프의 MST: 크루스칼은 간선이 V - 1개보다 적은 포레스트를 돌려줍니다. 트리로 다루기 전에 간선 수를 확인합니다.

정리

다익스트라는 링크 상태 라우팅과 (전처리를 더한) 지도 길찾기를 움직이고, 벨만-포드는 거리 벡터 라우팅의 바탕입니다.
MST는 네트워크 설계, 군집화, 근사 알고리즘에 쓰입니다.
편의성은 NetworkX, 규모는 SciPy나 Boost로 챙깁니다.
버그는 대부분 음수 가중치, 빠진 역방향 간선, 오버플로, 힙 동점 처리에서 나옵니다.

더 읽을거리

이 장에 대해 질문이 있나요?