개념

이 안내서는 가중치 그래프의 대표적인 두 문제를 다룹니다. 최단 경로는 한 정점에서 다른 정점으로 가는 가장 싼 길을 찾는 문제이고, 최소 신장 트리(MST)는 모든 정점을 연결 상태로 유지하는 가장 싼 간선 집합을 찾는 문제입니다. 둘 다 코딩 테스트에 자주 나오고, 지도 길찾기, 네트워크 라우팅, 배선 설계 같은 실제 시스템에서도 쓰입니다.

가중치 그래프

그래프는 정점 V와 간선 E로 이루어집니다. 가중치 그래프에서는 간선마다 거리, 시간, 비용, 지연 시간 같은 숫자가 붙습니다. 간선은 방향이 있을 수도(일방통행) 없을 수도(양방향 도로) 있습니다. 경로의 가중치는 경로에 있는 간선 가중치의 합이며, 최단 경로는 이 합이 가장 작은 경로입니다.

이 장의 알고리즘은 대부분 인접 리스트를 씁니다. 정점마다 (이웃, 가중치) 쌍의 목록을 두는 방식으로, 메모리는 O(V + E)이고 한 정점의 이웃을 빠르게 훑을 수 있습니다. 크루스칼 알고리즘은 대신 단순한 간선 리스트를 씁니다.

n = 4
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1)]  # (u, v, 가중치)

adj = [[] for _ in range(n)]
for u, v, w in edges:
    adj[u].append((v, w))
    # 무방향 그래프라면 adj[v].append((u, w))도 추가합니다

print(adj)  # [[(1, 4), (2, 1)], [(3, 1)], [(1, 2)], []]

문제의 종류

• 단일 출발점 최단 경로(SSSP): 한 출발점에서 모든 정점까지의 거리입니다. 다익스트라와 벨만-포드가 이 문제를 풉니다.
• 단일 쌍: s에서 t까지만 구합니다. 실제로는 SSSP 알고리즘을 돌리다가 t가 확정되면 멈춥니다.
• 모든 쌍 최단 경로(APSP): 모든 정점 쌍의 거리입니다. 플로이드-워셜을 쓰거나 모든 정점에서 다익스트라를 돌립니다.
• 최소 신장 트리: 연결된 무방향 그래프에서 모든 정점을 잇는 V - 1개의 간선을 가중치 합이 가장 작게 고릅니다. 크루스칼과 프림이 이 문제를 풉니다.

완화(relaxation)

이 안내서의 최단 경로 알고리즘은 모두 완화라는 하나의 연산 위에 세워져 있습니다. 정점마다 임시 거리 dist[v]를 두고 무한대로 시작합니다(출발점만 0). 간선 (u, v, w)를 완화한다는 것은 "u를 거쳐 가는 쪽이 지금 아는 값보다 나은가?"를 확인하는 일입니다.

from math import inf

dist = [0, inf, inf, inf]
parent = [-1, -1, -1, -1]

def relax(u, v, w):
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u          # v에 어떻게 왔는지 기록합니다
        return True
    return False

relax(0, 1, 4)
relax(0, 2, 1)
relax(2, 1, 2)                 # 1 + 2 = 3 이 4보다 작습니다
print(dist, parent)            # [0, 3, 1, inf] [-1, 2, 0, -1]

알고리즘마다 다른 것은 간선을 완화하는 순서뿐입니다. 다익스트라는 아직 확정되지 않은 정점 중 가장 가까운 정점의 간선부터 완화하고, 벨만-포드는 모든 간선을 여러 번 반복해서 완화하며, 플로이드-워셜은 거쳐 가는 정점을 하나씩 늘려 가며 완화합니다. parent 배열은 최단 경로 트리를 이루므로, 목적지에서 거꾸로 따라가면 실제 경로를 복원할 수 있습니다.

음수 간선과 음수 사이클

음수 가중치는 벨만-포드와 플로이드-워셜에서는 허용되지만 다익스트라의 탐욕적 가정을 깨뜨립니다. 음수 사이클은 가중치 합이 0보다 작은 사이클입니다. 출발점에서 이런 사이클에 닿을 수 있으면 그 사이클을 끝없이 돌 수 있으므로 최단 거리가 정의되지 않습니다. 음수 사이클을 찾아내는 것 자체가 쓸모 있는 결과이기도 해서, 환율 차익 거래를 찾는 데 쓰입니다.

알고리즘 고르기

최소 신장 트리

연결된 무방향 그래프의 신장 트리는 정확히 V - 1개의 간선으로 모든 정점을 잇고 사이클이 없습니다. MST는 그중 가중치 합이 가장 작은 신장 트리입니다. 탐욕 알고리즘이 여기서 옳은 답을 내는 이유는 두 가지 성질 덕분입니다. 컷 성질은 정점을 두 무리로 나눌 때 그 경계를 건너는 가장 가벼운 간선이 어떤 MST에 반드시 들어간다는 것이고, 사이클 성질은 사이클 위의 가장 무거운 간선은 빼도 된다는 것입니다. 크루스칼은 간선을 가벼운 순서로 더하면서 사이클을 만드는 간선은 유니온 파인드로 걸러 냅니다. 프림은 시작 정점 하나에서 트리를 키우면서 트리 밖으로 나가는 가장 싼 간선을 계속 더합니다.

MST와 최단 경로 트리는 다릅니다. MST는 케이블 전체 길이를 최소로 하고, 최단 경로 트리는 각 정점에서 출발점까지의 거리를 최소로 합니다.

    A ---1--- B
     \       /
      3     1
       \   /
         C

MST(합 2):               A-B, B-C   -> A에서 C까지는 B를 거쳐 2
A에서 시작한 최단 경로 트리: A-B, B-C  (이 경우는 같습니다)
A-C를 1.5로 바꾸면 MST는 그대로 A-B, B-C 이지만,
A에서 C로 가는 최단 경로는 직접 잇는 간선이 됩니다.

정리

• 최단 경로는 출발점에서의 가중치를 최소로 하고, MST는 무방향 그래프를 연결 상태로 두는 전체 가중치를 최소로 합니다.
• 완화가 공통 기본 연산이며, 알고리즘은 간선을 완화하는 순서로 구별됩니다.
• 가중치의 종류(없음, 0/1, 음수 아님, 음수)와 출발점이 하나인지 모든 쌍인지로 알고리즘을 고릅니다.
• 크루스칼과 프림이 옳은 이유는 컷 성질과 사이클 성질입니다.