복잡도

최단 경로와 MST 알고리즘 사이의 선택은 대부분 그래프의 크기, 밀도, 간선 가중치로 결정됩니다. 이 장에서는 실행 시간을 따져 보고 선택지를 비교합니다.

다익스트라

이진 힙을 쓰면 간선 하나가 최대 한 번 넣기를 일으키므로 힙에는 많아야 E + 1개의 항목이 들어갑니다. 넣기와 꺼내기는 각각 O(log E)이고, E가 V^2 이하이므로 log E는 2 log V 이하입니다. 합치면 시간은 O((V + E) log V), 메모리는 O(V + E)입니다. 최선, 평균, 최악 모두 같은 상한이며, 목적지 하나에서 일찍 멈추는 것은 실제 속도에만 도움이 됩니다.

밀집 그래프(E가 V^2에 가까움)에서는 힙이 오히려 손해입니다. 배열을 훑어 확정되지 않은 가장 가까운 정점을 찾으면 단계마다 O(V), 전체 O(V^2)로 O(V^2 log V)보다 빠릅니다.

from math import inf

def dijkstra_dense(w, source):
    """w[u][v]는 간선 가중치, 간선이 없으면 inf입니다."""
    n = len(w)
    dist = [inf] * n
    done = [False] * n
    dist[source] = 0
    for _ in range(n):
        u = min((i for i in range(n) if not done[i]), key=dist.__getitem__)
        if dist[u] == inf:
            break  # 나머지는 닿을 수 없음
        done[u] = True
        for v in range(n):
            if dist[u] + w[u][v] < dist[v]:
                dist[v] = dist[u] + w[u][v]
    return dist

W = [[0, 4, 1], [inf, 0, inf], [inf, 2, 0]]
print(dijkstra_dense(W, 0))  # [0, 3, 1]

피보나치 힙을 쓰면 상한이 O(E + V log V)로 내려가지만 상수 부담이 커서 이론 밖에서는 잘 쓰이지 않습니다.

벨만-포드, 플로이드-워셜, 0-1 BFS

• 벨만-포드는 모든 E개 간선을 V - 1회차 돌립니다. 시간 O(V E), 메모리 O(V)입니다. 일찍 끝내기를 넣으면 첫 회차에 모든 거리가 정해지는 최선의 경우 O(E)입니다.
• 플로이드-워셜은 항상 V^3번 반복하고 V × V 행렬을 저장합니다. 시간 O(V^3), 메모리 O(V^2)입니다. 정점 수백 개까지는 간단하고 빠르지만 V = 10^4이면 행렬만 10^8칸입니다.
• 0-1 BFS는 간선마다 상수 번만 처리하므로 O(V + E)입니다.

방향 비순환 그래프

사이클이 없는 그래프라면 힙이 전혀 필요 없고 음수 가중치도 괜찮습니다. 위상 순서대로 간선을 완화하면 간선마다 정확히 한 번씩 완화되어 전체 O(V + E)입니다. Python 표준 라이브러리에 위상 정렬 도구가 있습니다.

from graphlib import TopologicalSorter
from math import inf

def dag_shortest(n, edges, source):
    adj = [[] for _ in range(n)]
    preds = {v: set() for v in range(n)}
    for u, v, w in edges:
        adj[u].append((v, w))
        preds[v].add(u)
    dist = [inf] * n
    dist[source] = 0
    for u in TopologicalSorter(preds).static_order():
        if dist[u] != inf:
            for v, w in adj[u]:
                dist[v] = min(dist[v], dist[u] + w)
    return dist

print(dag_shortest(4, [(0, 1, 5), (0, 2, 3), (2, 1, -4), (1, 3, 1)], 0))  # [0, -1, 3, 0]

크루스칼과 프림

• 크루스칼은 간선 정렬에 O(E log E)가 들고, 경로 압축(또는 절반 줄이기)과 크기 기준 합치기를 쓴 유니온 파인드 연산은 O(E α(V))입니다. 역아커만 함수 α는 현실적인 입력에서 5보다 작습니다. 정렬이 지배하므로 전체는 O(E log E), 곧 O(E log V)입니다.
• 이진 힙 프림은 다익스트라처럼 O(E log V)입니다. 인접 행렬과 배열을 쓰면 O(V^2)로, "모든 점 쌍을 이을 수 있는" 완전 그래프에서 가장 좋은 선택입니다.

비교표

음수가 아닌 가중치의 희소 그래프에서 모든 쌍을 구할 때, 모든 정점에서 다익스트라를 돌리면 O(V (V + E) log V)로, E가 V^2보다 훨씬 작으면 플로이드-워셜보다 빠릅니다. 존슨(Johnson) 알고리즘은 벨만-포드 한 번으로 가중치를 다시 매겨 이 방법을 음수 간선까지 넓힙니다.

규모 감각

V = 10,000개 정점, E = 100,000개 간선, log2 V는 약 14

다익스트라(이진 힙)   (V + E) log V   약 150만 단계
벨만-포드             V × E           10억 단계
플로이드-워셜         V^3             1조 단계
크루스칼              E log E         약 170만 단계

대략적인 단계 수는 초 단위 시간이 아니지만, 알고리즘 선택이 몇 자릿수 차이를 만든다는 점은 분명히 보여 줍니다.

정리

• 다익스트라는 힙으로 O((V + E) log V), 밀집 그래프에서는 배열로 O(V^2)입니다.
• 벨만-포드의 O(V E)는 음수 간선을 허용하는 대가이고, 플로이드-워셜의 O(V^3)은 작은 그래프에만 맞습니다.
• DAG와 0/1 가중치에는 선형 시간 알고리즘이 있습니다.
• 크루스칼은 정렬이 시간을 지배하고, 프림은 다익스트라의 힙 구조를 그대로 닮았습니다.