동작 원리

이 장에서는 작은 그래프에서 각 알고리즘을 직접 따라가며 완화가 어떤 순서로 일어나는지 봅니다. 다익스트라 예제는 방향 간선 A→B 4, A→C 1, C→B 2, B→D 1, C→D 5, D→E 3 이고 출발점은 A입니다.

다익스트라 한 단계씩

다익스트라는 (거리, 정점) 쌍을 담은 최소 힙을 씁니다. 가장 가까운 정점을 꺼내면, 모든 가중치가 음수가 아니므로 나중에 어떤 경로가 와도 그 정점을 더 싸게 만들 수 없습니다. 그래서 꺼낸 정점의 거리는 확정이고, 이어서 그 정점의 나가는 간선을 완화합니다. 거리가 줄어들면 힙의 기존 항목을 고치지 않고 새 쌍을 넣기만 하며, 낡은 쌍은 꺼낼 때 건너뜁니다(지연 삭제).

최종 거리는 A 0, B 3, C 1, D 4, E 7입니다. E까지의 최단 경로는 A→C→B→D→E입니다.

음수 간선에서 다익스트라가 틀리는 이유

A→B 2, A→C 3, C→B -2 를 생각해 봅니다. 다익스트라는 C를 보기 전에 B를 거리 2로 확정하지만, 실제 거리는 3 + (-2) = 1입니다. "가장 가까운 정점은 확정"이라는 탐욕적 논리는 경로를 늘리면 길이가 줄지 않는다는 가정에 기대는데, 음수 가중치가 있으면 이 가정이 틀립니다. 이럴 때는 벨만-포드를 씁니다.

벨만-포드

벨만-포드는 모든 간선을 V - 1번 완화합니다. 사이클이 없는 최단 경로는 간선이 많아야 V - 1개이고, k번째 회차가 끝나면 간선 k개짜리 경로가 모두 반영되기 때문입니다. 그다음 한 번 더 돌리는 회차가 검사 역할을 합니다. 그때도 완화되는 간선이 있으면 출발점에서 닿는 음수 사이클이 있다는 뜻입니다.

from math import inf

def bellman_ford(n, edges, source):
    dist = [inf] * n
    dist[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != inf and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:          # 이번 회차에 바뀐 것이 없으면 일찍 끝냅니다
            break
    for u, v, w in edges:
        if dist[u] != inf and dist[u] + w < dist[v]:
            raise ValueError("출발점에서 닿는 음수 사이클이 있습니다")
    return dist

# S=0, A=1, B=2, C=3
print(bellman_ford(4, [(0, 1, 4), (0, 2, 5), (2, 1, -3), (1, 3, 2)], 0))  # [0, 2, 5, 4]

1회차에서 간선을 적힌 순서대로 훑으면 A가 4, B가 5가 되고, B→A가 A를 2로 낮추며, A→C가 C를 4로 만듭니다. 2회차에서는 아무것도 바뀌지 않으므로 반복이 일찍 끝납니다.

플로이드-워셜

플로이드-워셜은 세 겹 반복문으로 모든 쌍을 한꺼번에 구합니다. 중간 정점 k까지 처리하고 나면 d[i][j]는 중간에 0..k 정점만 거치는 i에서 j까지의 최단 거리입니다. 반복 순서가 중요해서 k가 가장 바깥에 있어야 합니다.

from math import inf

def floyd_warshall(d):
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

d = [[0, 3, inf], [inf, 0, 1], [2, inf, 0]]
print(floyd_warshall(d))  # [[0, 3, 4], [3, 0, 1], [2, 5, 0]]

실행이 끝난 뒤 대각선에 음수가 있으면(d[i][i] < 0) 정점 i가 음수 사이클 위에 있다는 뜻입니다.

0-1 BFS

모든 가중치가 0 또는 1이면 힙 대신 덱(deque)을 씁니다. 0 간선으로 닿은 정점은 앞에, 1 간선으로 닿은 정점은 뒤에 넣으면 덱이 늘 거리순으로 유지되고 각 단계는 O(1)입니다.

from collections import deque
from math import inf

def zero_one_bfs(adj, source):
    dist = [inf] * len(adj)
    dist[source] = 0
    dq = deque([source])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

print(zero_one_bfs([[(1, 1), (2, 0)], [(3, 1)], [(1, 0), (3, 1)], []], 0))  # [0, 0, 0, 1]

한 그래프에서 크루스칼과 프림

무방향 간선: A-B 1, B-C 2, A-C 3, C-D 4, B-D 5.

A에서 시작한 프림은 트리 밖으로 나가는 가장 싼 간선을 꺼냅니다. A-B 1, 그다음 B-C 2(A-C 3보다 쌈), 그다음 C-D 4(B-D 5보다 쌈)입니다. 두 알고리즘 모두 가중치 7인 같은 트리에 도착합니다. 같은 가중치가 있어 MST가 여러 개일 때만 서로 다른 트리를 고를 수 있고, 그때도 합은 같습니다.

정리

• 다익스트라는 매번 가장 가까운 정점을 확정하고 힙의 낡은 항목은 건너뜁니다.
• 벨만-포드는 V - 1회차가 필요하며, 한 번 더 돌린 회차에서 값이 바뀌면 음수 사이클입니다.
• 플로이드-워셜은 중간 정점 k를 가장 바깥 반복으로 둡니다.
• 0-1 BFS는 0 간선을 덱 앞에 넣어 순서를 유지합니다.
• 크루스칼은 간선 단위로, 프림은 트리 하나를 키우는 방식으로 동작하며 둘 다 옳은 탐욕 알고리즘입니다.