최단 경로 - 다익스트라와 그 한계

이 장에서 배우는 것

앞 장에서 다룬 그래프 탐색은 정점 사이에 길이 있는지, 몇 개의 간선을 거치는지 확인하는 데 쓰였다. 그러나 실제 이동 비용은 간선마다 다르다. 골목 하나를 지나는 데 2분이 걸리고 다른 골목은 9분이 걸린다면, 적은 수의 골목을 지나는 길이 가장 빠른 길이라고 할 수 없다. 이번에는 간선에 붙은 비용을 더해 비교하고, 출발점에서 각 지점까지의 최소 비용을 구한다.

다익스트라 알고리즘(Dijkstra’s algorithm)의 핵심은 현재까지 알려진 거리 중 가장 작은 것을 먼저 살피는 데 있다. 이 선택을 믿을 수 있는 조건이 무엇인지 이해해야 코드를 다른 상황에도 안전하게 적용할 수 있다. 특히 음수 비용은 단순한 예외 입력이 아니라 정확성 근거를 바꾸는 조건이다.

• 가중치 그래프를 인접 리스트로 표현하고, 거리와 간선 수의 차이를 설명한다.
• 우선순위 큐(priority queue)와 heapq로 다익스트라를 구현한다.
• 음수 간선이 있을 때 최소 거리 확정 논리가 무너지는 이유를 반례로 확인한다.
• 직전 정점을 기록해 실제 최단 경로를 복원한다.
• 작은 그래프의 모든 단순 경로를 조사해 빠른 풀이의 결과와 대조한다.

문제 상황

작은 배달 거점에서 네 지점으로 물품을 보낸다. 지점 번호는 0부터 3까지이며 출발점은 0이다. 도로마다 이동 시간이 다르고, 통행 방향도 정해져 있다. 0에서 1로 가는 도로가 있다고 해서 1에서 0으로 돌아올 수 있는 것은 아니다. 여기서는 교통 상황이 변하지 않고, 도로를 지날 때마다 정해진 시간이 든다고 가정한다.

도로 정보는 0→1이 7분, 0→2가 2분, 2→1이 1분, 2→3이 8분, 1→3이 3분이다. 0에서 1까지 곧장 가면 7분이지만 2를 거치면 3분이다. 3까지는 0→2→1→3으로 가는 6분짜리 경로가 가장 빠르다. 프로그램은 각 지점까지의 최소 시간과 3까지의 실제 이동 순서를 출력해야 한다.

두 번째 상황은 창고의 이동 통로다. 창고 구역은 네 곳이며 0→1의 비용은 0, 1→2의 비용은 4다. 구역 3으로 가는 통로는 없다. 비용 0은 통행 불가를 뜻하지 않는다. 추가 비용 없이 이동할 수 있다는 뜻이다. 반면 구역 3은 도달할 수 없으므로 거리와 경로를 별도로 처리해야 한다.

마지막으로 정산 경로를 생각해 본다. 어떤 연결을 통과할 때 할인액이 차감되어 비용이 음수가 될 수 있다. 이 상황은 배달 시간과 같은 규칙으로 풀 수 있을까. 음수 간선의 작은 반례를 통해 적용 조건을 확인한다. 세 상황 모두 정점은 장소나 처리 지점, 간선은 허용된 이동, 가중치는 그 이동의 비용을 나타낸다.

가중치와 최소 거리의 확정

가중치 그래프(weighted graph)는 간선마다 수치가 붙은 그래프다. 이 수치를 가중치라고 부른다. 경로의 비용은 그 경로에 포함된 간선 가중치의 합이다. 여기서 구할 값은 하나의 출발점에서 각 정점까지 가는 경로 중 비용의 최솟값이다. 도달할 수 없는 정점에는 유한한 최솟값이 없다.

앞 장의 너비 우선 탐색은 먼저 발견한 정점이 출발점에서 간선 수로 가장 가까운 정점이라는 성질을 이용했다. 모든 간선 비용이 같다면 이 순서로 충분하다. 비용이 다르면 발견 순서만으로 거리를 확정할 수 없다. 배달 예시에서 정점 1은 출발점과 직접 연결되어 있지만 정점 2를 거쳐야 더 싸게 도달한다.

거리 배열 dist에는 지금까지 발견한 최소 비용을 기록한다. 처음에는 출발점만 0이고 나머지는 무한대다. 정점 u까지의 비용이 알려져 있고 u에서 v로 가는 간선 비용이 w라면, v까지 가는 후보 비용은 dist[u] + w다. 이 값이 dist[v]보다 작으면 기록을 바꾼다. 이처럼 간선을 통해 거리의 상한을 낮추는 작업을 완화(relaxation)라고 한다.

다익스트라는 아직 처리가 끝나지 않은 정점 중 현재 거리가 가장 작은 정점을 선택한다. 배달 예시에서는 0, 2, 1, 3 순서로 유효한 처리가 이루어진다. 정점 번호 순서나 도로가 입력된 순서가 기준이 아니다.

가장 작은 거리부터 처리하면 배달 거리가 갱신되는 과정

꺼낸 항목	거리 배열	일어난 일
시작 전	[0, ∞, ∞, ∞]	출발점만 거리 0이다.
(0, 0)	[0, 7, 2, ∞]	1과 2의 후보를 등록한다.
(2, 2)	[0, 3, 2, 10]	1을 개선하고 3을 발견한다.
(3, 1)	[0, 3, 2, 6]	3을 10에서 6으로 줄인다.
(6, 3)	[0, 3, 2, 6]	나가는 도로가 없다.
(7, 1), (10, 3)	[0, 3, 2, 6]	이미 바뀐 옛 기록이므로 버린다.

거리 배열의 유한한 값은 실제로 발견한 어떤 경로의 비용이다. 따라서 실제 최단 거리보다 작게 기록되지는 않는다. 이것이 첫 번째 불변식이다. 두 번째 불변식은 가장 작은 유효 거리로 선택되어 처리를 마친 정점의 거리가 실제 최단 거리라는 것이다. 두 번째 성질에는 모든 간선 가중치가 0 이상이라는 조건이 필요하다.

왜 그런지 짧게 따져 보자. 지금 선택한 정점 u까지 더 짧은 경로가 남아 있다고 가정한다. 그 경로에서 처리가 끝난 영역을 처음 벗어나는 정점을 x라고 하자. 출발점은 처음 처리되므로, 아직 처리하지 않은 u로 가는 경로에는 이런 경계가 있다. x 직전 정점을 처리할 때 x까지의 후보가 이미 등록되었다.

남은 간선 비용이 모두 0 이상이면 x까지의 비용은 그 경로 전체 비용보다 클 수 없다. 따라서 u보다 작은 거리의 후보 x가 먼저 선택되어야 한다. 이는 u가 가장 작은 유효 후보였다는 선택과 맞지 않는다. 출발점부터 이 논리를 반복하면 처리된 정점의 거리가 차례로 확정된다는 결론을 얻는다. 비용이 0인 간선도 이 근거를 해치지 않는다.

힙으로 구현하고 경로를 되짚기

매번 거리 배열 전체를 훑어 가장 작은 값을 찾을 수도 있다. 하지만 정점이 많으면 같은 탐색을 반복하는 비용이 커진다. 힙(heap)은 가장 작은 항목을 빠르게 꺼내는 자료구조다. Python 표준 라이브러리 heapq는 리스트를 최소 힙으로 다루며, 여기서는 (거리, 정점 번호) 쌍을 넣는다. 두 거리 값이 같으면 정점 번호로 순서를 정하므로 실행 순서도 일정하다.

이미 들어간 항목의 값을 직접 고치지는 않는다. 정점 1의 거리가 7에서 3으로 줄면 (3, 1)을 새로 넣고 (7, 1)은 그대로 둔다. 나중에 (7, 1)을 꺼냈을 때 거리 배열의 현재 값 3과 다르므로 버린다. 힙의 항목은 최종 답이 아니라 특정 시점에 등록한 후보라는 점을 구분해야 한다.

코드의 핵심 조건은 d != dist[u]다. 꺼낸 거리 d가 현재 기록과 같을 때만 간선을 조사한다. 이미 더 좋은 값으로 바뀐 항목을 걸러 내므로 불필요한 재처리를 줄인다. 간선 비용이 0 이상이면 유효한 항목으로 처리된 정점의 거리가 이후 더 줄어들지 않는다.

실제 경로를 출력하려면 parent[v]에 v의 거리를 개선한 직전 정점 u를 저장한다. 배달 예시에서는 parent[3]이 1, parent[1]이 2, parent[2]가 0이 된다. 목적지에서 시작해 부모를 따라가면 [3, 1, 2, 0]을 얻는다. 이를 뒤집으면 출발점부터의 경로가 된다.

거리가 같은 후보에서는 부모를 바꾸지 않는다. 이 규칙은 같은 비용의 경로 중 하나를 일관되게 남기며, 비용 0인 연결을 따라 불필요하게 부모를 바꾸는 일도 막는다. 이 구현이 사전순으로 가장 작은 최단 경로를 보장하는 것은 아니다. 그런 요구가 있다면 동률 처리 규칙을 별도로 설계해야 한다.

도달하지 못한 정점은 parent가 -1이지만, 출발점의 parent도 -1이다. 따라서 parent만 보고 도달 여부를 판단하면 출발점까지의 경로를 놓칠 수 있다. 먼저 dist[target]이 무한대인지 확인하고, 도달 가능할 때만 부모를 따라간다. 출발점 자체를 목적지로 주면 [start]가 나온다.

정점 수를 V, 간선 수를 E라고 하자. 인접 리스트를 만드는 데 시간과 공간이 O(V + E) 든다. 이 구현은 개선된 후보를 새로 넣으므로 힙에 O(E + 1)개의 항목이 들어갈 수 있다. 전체 시간은 고립된 정점의 초기화까지 포함해 O(V + E log(E + 2)), 보조 공간은 거리·부모·힙을 합쳐 O(V + E)다. 입력 그래프를 포함한 공간도 같은 차수다.

같은 두 정점 사이에 중복 간선이 없는 일반적인 그래프에서는 E가 V² 이하이므로 시간 복잡도를 흔히 O((V + E) log V)로 표현한다. 경로 복원은 출력 경로에 포함된 정점 수를 L이라 할 때 시간과 반환 리스트 공간이 O(L)이다. 코드에서는 음수 간선 검사를 위해 모든 간선을 한 번 더 보지만 전체 차수는 달라지지 않는다.

음수 간선의 반례와 작은 정답 검사

정산 경로에 0→1 비용 2, 0→2 비용 5, 2→1 비용 -4가 있다고 하자. 출발점 0을 처리하면 정점 1의 거리는 2, 정점 2의 거리는 5다. 다익스트라의 선택대로라면 1을 먼저 확정한다. 그러나 2를 거친 0→2→1의 비용은 1이다. 뒤에서 음수 비용을 만나면 큰 중간 비용을 가진 경로가 더 작은 최종 비용으로 바뀔 수 있다.

정확히 말하면, 정점을 방문 처리한 뒤 다시 갱신하지 않는 구현이나 목적지를 처음 꺼내자마자 반환하는 구현은 이 반례에서 잘못된 답을 낸다. 반면 이번 코드처럼 개선된 항목을 계속 넣고 끝까지 처리하는 형태는 이 작은 반례의 값을 다시 고칠 수도 있다. 그렇다고 음수 간선에 쓸 수 있는 다익스트라 구현이 되는 것은 아니다. 앞서 제시한 확정 논리와 시간 복잡도 근거를 적용할 수 없기 때문이다.

특히 출발점에서 갈 수 있는 곳에, 한 바퀴 돌 때 비용이 줄어드는 음수 사이클이 있으면 갱신이 계속될 수 있다. 그 사이클을 거쳐 도달하는 목적지에는 비용을 더 낮추는 이동을 반복할 수 있어 유한한 최솟값이 없다. 완성 코드는 음수 간선을 발견하면 계산을 시작하기 전에 예외를 발생시킨다. 출발점에서 닿지 않는 음수 간선도 거부하는 단순하고 명확한 입력 계약을 사용한다.

빠른 풀이를 검증할 느린 정답은 모든 단순 경로를 조사한다. 단순 경로는 같은 정점을 두 번 방문하지 않는 경로다. 음수가 없는 그래프에서는 정점을 반복하는 부분을 제거해도 비용이 커지지 않는다. 따라서 도달 가능한 두 정점 사이에는 최단 비용을 갖는 단순 경로가 하나 이상 있다. 비용 0인 사이클이 있어도 이 설명은 성립한다.

느린 정답은 현재 경로에 포함된 정점을 used 집합으로 기억한다. 정점을 내려갈 때 추가하고 돌아올 때 제거한다. 어떤 정점까지 이미 더 싼 경로를 찾았더라도 탐색을 중단하지 않는다. 그 경로에서 이미 쓴 정점이 서로 다를 수 있으므로, 모든 단순 경로를 직접 조사한다는 검증 방식에 맞춰 가지치기 없이 진행한다.

정점 수가 늘면 단순 경로 수가 빠르게 증가하므로 이 검사는 작은 입력에서만 쓴다. 여기서는 정점 3개의 서로 다른 두 정점 사이에 가능한 방향 간선 6개를 만든다. 각 간선은 없음, 비용 0, 비용 2 중 하나를 고른다. 그래프는 3⁶ = 729개이며 각 그래프에서 출발점 3개를 모두 검사해 총 2,187번 비교한다. 난수를 쓰지 않으므로 seed 설정 없이도 검사 순서와 출력이 일정하다.

거리만 맞고 경로가 잘못될 수도 있다. 그래서 모든 목적지에 대해 복원한 경로의 시작과 끝, 정점 중복 여부, 실제 간선의 존재, 비용의 합까지 확인한다. 이 전수 대조는 정점 3개와 지정한 비용 집합 안에서의 검사다. 일반 입력에 대한 보장은 앞서 설명한 불변식과 입력 조건이 맡고, 작은 검사는 구현의 실수를 찾는 역할을 한다.

완성 코드

다음 프로그램 전체를 main.py에 저장한다. 외부 입력을 기다리지 않으며 표준 라이브러리만 사용한다. 예시 문자열은 io.StringIO로 감싸 코딩 테스트의 입력 파일처럼 읽는다. 첫 줄은 정점 수, 간선 수, 출발점이며 이후 각 줄은 출발 정점, 도착 정점, 비용이다. 정점 번호는 0부터 시작한다고 가정한다.

import heapq
import io
from itertools import product
from math import inf


def read_graph(text):
    stream = io.StringIO(text)
    n, m, start = map(int, stream.readline().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v, weight = map(int, stream.readline().split())
        graph[u].append((v, weight))
    return graph, start


def dijkstra(graph, start):
    for edges in graph:
        for _, weight in edges:
            if weight < 0:
                raise ValueError("음수 간선은 지원하지 않는다.")

    dist = [inf] * len(graph)
    parent = [-1] * len(graph)
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, u = heapq.heappop(heap)
        if d != dist[u]:
            continue
        for v, weight in graph[u]:
            candidate = d + weight
            if candidate < dist[v]:
                dist[v] = candidate
                parent[v] = u
                heapq.heappush(heap, (candidate, v))

    return dist, parent


def restore_path(parent, dist, target):
    if dist[target] == inf:
        return []
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path


def all_simple_distances(graph, start):
    best = [inf] * len(graph)
    used = {start}

    def search(u, cost):
        best[u] = min(best[u], cost)
        for v, weight in graph[u]:
            if v not in used:
                used.add(v)
                search(v, cost + weight)
                used.remove(v)

    search(start, 0)
    return best


def check_paths(graph, start, dist, parent):
    for target in range(len(graph)):
        path = restore_path(parent, dist, target)
        if dist[target] == inf:
            assert path == []
            continue
        assert path[0] == start
        assert path[-1] == target
        assert len(path) == len(set(path))
        total = 0
        for u, v in zip(path, path[1:]):
            weights = [
                weight for to, weight in graph[u] if to == v
            ]
            assert weights
            total += min(weights)
        assert total == dist[target]


def exhaustive_check():
    n = 3
    pairs = [
        (u, v)
        for u in range(n)
        for v in range(n)
        if u != v
    ]
    checked = 0
    for choices in product((None, 0, 2), repeat=len(pairs)):
        graph = [[] for _ in range(n)]
        for (u, v), weight in zip(pairs, choices):
            if weight is not None:
                graph[u].append((v, weight))
        for start in range(n):
            dist, parent = dijkstra(graph, start)
            expected = all_simple_distances(graph, start)
            assert dist == expected
            check_paths(graph, start, dist, parent)
            checked += 1
    return checked


def main():
    delivery_text = """4 5 0
0 1 7
0 2 2
2 1 1
2 3 8
1 3 3
"""
    graph, start = read_graph(delivery_text)
    dist, parent = dijkstra(graph, start)
    assert dist == all_simple_distances(graph, start)
    check_paths(graph, start, dist, parent)
    print("배달 거리:", dist)
    print("배달 경로:", restore_path(parent, dist, 3))

    warehouse_text = """4 2 0
0 1 0
1 2 4
"""
    graph, start = read_graph(warehouse_text)
    dist, parent = dijkstra(graph, start)
    assert dist == all_simple_distances(graph, start)
    check_paths(graph, start, dist, parent)
    print("창고 거리:", dist)
    print("창고 경로:", restore_path(parent, dist, 2))
    print("고립 구역 경로:", restore_path(parent, dist, 3))

    negative_graph = [[(1, 2), (2, 5)], [], [(1, -4)]]
    try:
        dijkstra(negative_graph, 0)
    except ValueError as error:
        print("음수 간선 검사:", error)
    else:
        raise AssertionError("음수 간선을 거부해야 한다.")

    print("전수 대조:", exhaustive_check(), "건 통과")


if __name__ == "__main__":
    main()

줄별 해설

가져오기와 입력 구성. heapq는 후보의 추가와 최솟값 추출에 사용한다. io는 문자열을 입력 스트림으로 읽는 데 쓴다. product는 간선 상태의 모든 조합을 만들고, inf는 도달할 수 없는 거리를 표현한다. 큰 정수를 임의로 골라 무한대처럼 쓰면 실제 경로 비용이 그보다 커질 수 있으므로 여기서는 inf로 구분한다.

read_graph. stream.readline()은 문자열의 한 줄을 읽는다. graph[u]에는 u에서 나가는 (도착 정점, 비용) 쌍을 넣는다. 역방향 간선을 자동으로 추가하지 않으므로 방향 그래프가 된다. 입력 형식이 올바르고 정점 번호가 범위 안이라는 조건을 둔다. 실제 서비스 입력이라면 이 조건에 대한 검증을 별도로 붙인다.

dijkstra의 앞부분. 거리 배열을 만들기 전에 음수 가중치를 검사한다. 이 위치에 검사를 두면 도달 여부와 관계없이 함수의 입력 계약을 일관되게 적용한다. dist[start]만 0으로 두는 이유는 아무 간선도 지나지 않는 출발점까지의 비용이 0이기 때문이다. parent의 -1은 이전 정점이 없다는 표시다.

while heap. heappop은 가장 작은 거리 쌍을 꺼낸다. d와 dist[u]가 다르면 이미 갱신된 옛 항목이다. continue 아래의 간선 반복문은 현재 기록과 일치하는 후보에 대해서만 실행된다. 목적지 하나를 정해 중간에 반환하지 않고 모든 도달 가능한 정점의 거리를 구한다.

candidate와 부모 저장. candidate는 현재 경로 뒤에 간선 하나를 붙인 비용이다. 더 작을 때만 거리와 부모를 함께 고치고 새 후보를 넣는다. 부모만 바꾸거나 거리만 바꾸면 경로의 비용과 거리 배열이 서로 어긋날 수 있다. 비교가 <라는 점도 중요하다. 같은 값으로는 새 항목을 넣지 않는다.

restore_path. 무한대인 목적지는 빈 리스트로 반환한다. 나머지는 목적지부터 parent를 따라가며 수집한 뒤 뒤집는다. 유효한 다익스트라 결과에서는 부모가 경로를 출발점까지 연결한다. 이 함수는 그 계약을 전제로 하므로 임의의 부모 배열에 대한 검증 함수로 사용하지 않는다.

all_simple_distances. best는 느린 정답의 거리 배열이다. search에 전달하는 cost는 현재 경로의 비용이며, used는 그 경로 안에 있는 정점만 담는다. 재귀 호출이 끝난 다음 used.remove(v)를 실행하므로 다른 경로에서는 v를 다시 선택할 수 있다. 전체 탐색에서 한 번 방문한 정점을 계속 막는 방식과 다르다.

check_paths. 도달 가능한 정점에 대해 복원 경로의 양 끝과 중복 여부를 검사한다. zip(path, path[1:])은 연속한 두 정점을 차례로 꺼낸다. 그 사이의 간선이 있는지 확인하고 비용을 더한다. 같은 방향의 간선이 여러 개라면 최소 비용을 쓴다. 현재 코드는 정점 순서만 복원하므로 개별 도로의 식별자가 필요한 업무에서는 부모 간선도 따로 기록해야 한다.

exhaustive_check. pairs에는 자기 자신을 제외한 방향 간선 후보가 들어간다. None은 간선 없음이고 정수 0은 실제 비용이다. 각 조합마다 그래프를 새로 만든 뒤 모든 출발점에서 빠른 거리와 느린 거리를 비교한다. 검사 중 하나라도 실패하면 assert가 실행을 멈춘다. 검증을 위해 실행할 때는 assert를 생략하는 최적화 옵션을 붙이지 않는다.

main. 배달과 창고 예시는 거리 대조와 경로 검사를 거친 뒤 출력된다. 음수 예시는 예외가 발생하는 동작을 확인하며, 예외가 없으면 검사 실패로 처리한다. 마지막으로 전수 대조 횟수를 출력한다. 함수 정의와 실행 부분을 나누었으므로 다른 파일에서 함수를 가져와도 예시가 자동 실행되지는 않는다.

실행 결과

macOS나 Linux에서 다음 명령으로 문법 컴파일과 실행을 확인할 수 있다. 첫 명령이 성공하면 출력 없이 끝나며, 두 번째 명령은 아래 결과를 출력한다. Python 3.12 이상의 표준 라이브러리만 필요하다.

python3 -m py_compile main.py
python3 main.py

배달 거리: [0, 3, 2, 6]
배달 경로: [0, 2, 1, 3]
창고 거리: [0, 0, 4, inf]
창고 경로: [0, 1, 2]
고립 구역 경로: []
음수 간선 검사: 음수 간선은 지원하지 않는다.
전수 대조: 2187 건 통과

창고 거리의 두 번째 0은 구역 1까지 비용 없이 갈 수 있다는 뜻이다. inf는 구역 3으로 가는 경로를 찾지 못했다는 뜻이다. 전수 대조의 2,187건은 그래프와 출발점의 조합 수다. 각 조합에서 모든 목적지의 거리와 복원 경로를 검사한다.

실무에서 자주 틀리는 것

처음 발견한 거리를 최종 거리로 취급한다

다음 코드는 아직 발견하지 못한 정점만 갱신한다. 배달 예시에서 정점 1에 7을 기록한 뒤 더 짧은 3을 받아들이지 못한다. 발견 여부 대신 새로운 비용이 현재 비용보다 작은지 비교해야 한다.

# 틀린 코드
if dist[v] == inf:
    dist[v] = d + weight
    heapq.heappush(heap, (dist[v], v))

# 고친 코드
candidate = d + weight
if candidate < dist[v]:
    dist[v] = candidate
    parent[v] = u
    heapq.heappush(heap, (candidate, v))

거리와 정점의 튜플 순서를 바꾼다

heapq는 튜플의 첫 값을 먼저 비교한다. 정점 번호를 앞에 놓으면 거리 순서로 꺼내지 못한다. 잘못된 순서에 재처리를 허용하면 일부 입력의 답을 나중에 고칠 수 있어 오류를 알아채기 어렵지만, 다익스트라의 처리 순서와 성능 근거는 사라진다.

# 틀린 코드
heapq.heappush(heap, (v, candidate))

# 고친 코드
heapq.heappush(heap, (candidate, v))

꺼낼 때도 d, u 순서를 유지하고, d != dist[u] 검사를 함께 둔다. 튜플을 넣는 부분만 고치고 꺼내는 변수 순서를 그대로 두면 또 다른 오류가 된다.

같은 거리에서도 후보를 계속 등록한다

비교에 <=를 쓰면 비용 0인 사이클을 따라 같은 후보가 반복해서 들어갈 수 있다. 예를 들어 0→1과 1→0의 비용이 모두 0이면 서로 같은 거리를 계속 등록한다. 부모 기록도 불필요하게 바뀔 수 있다.

# 틀린 코드
if candidate <= dist[v]:
    dist[v] = candidate
    parent[v] = u
    heapq.heappush(heap, (candidate, v))

# 고친 코드
if candidate < dist[v]:
    dist[v] = candidate
    parent[v] = u
    heapq.heappush(heap, (candidate, v))

음수 비용을 0으로 바꿔 계산한다

음수를 제거하면 알고리즘의 조건은 맞출 수 있지만 원래 문제의 비용이 달라진다. 정산 반례에서 -4를 0으로 바꾸면 우회 경로의 비용이 1에서 5가 된다. 잘못된 입력을 조용히 수정하지 말고 함수가 지원하는 범위를 명시해야 한다.

# 틀린 코드
weight = max(0, weight)

# 고친 코드
if weight < 0:
    raise ValueError("음수 간선은 지원하지 않는다.")

실제로 음수 비용이 필요한 문제라면 음수 간선을 허용하는 별도의 최단 경로 알고리즘과 음수 사이클 처리가 필요하다. 이번 구현의 조건 검사만 지우는 것으로 해결되지 않는다.

한눈에 보기

다익스트라 구현을 읽을 때 확인할 조건과 역할

항목	규칙	이유
가중치	모든 간선이 0 이상이다.	작은 거리부터 확정하는 근거다.
힙 항목	(거리, 정점)을 저장한다.	거리 기준으로 후보를 꺼낸다.
옛 후보	d != dist[u]이면 버린다.	갱신 이전 기록의 처리를 막는다.
거리 갱신	더 작을 때만 바꾼다.	동일 비용의 반복 등록을 막는다.
경로 복원	개선 시 부모를 함께 저장한다.	최종 비용에 해당하는 경로를 남긴다.
도달 불가	거리는 inf, 경로는 []다.	비용 0인 경로와 구별한다.
전체 시간	O(V + E log(E + 2))	배열 초기화와 힙 처리를 포함한다.
전체 공간	O(V + E)	인접 리스트와 후보를 저장한다.
작은 정답	모든 단순 경로를 조사한다.	음수가 없으면 최단 비용을 보존한다.

연습 문제

1. 배달 예시에서 2→3의 비용만 8에서 1로 바꾼다. 정점 3까지의 최단 거리와 경로를 구하고, 정점 1을 처리할 때 정점 3의 값이 바뀌는지 설명하라.
2. 창고 예시에 2→1 비용 0인 통로를 추가한다. 출발점 0에서 모든 정점까지의 거리를 구하라. 단순 경로만 조사해도 되는 이유와 used에서 정점을 제거해야 하는 이유를 설명하라.
3. 정산 그래프의 간선이 0→1 비용 3, 0→2 비용 8, 2→1 비용 -7이다. 목적지 1을 처음 꺼낼 때 반환하는 구현의 답과 실제 최단 거리를 각각 구하라. 음수 사이클이 없어도 다익스트라의 확정 근거가 무너지는지 설명하라.
4. 전수 대조에 포함되지 않은 자기 자신으로 향하는 간선을 검사하려 한다. 정점 0에 비용 0인 자기 간선을 추가했을 때 빠른 풀이와 느린 풀이가 어떻게 처리하는지 설명하라. 또한 시작점과 목적지가 같을 때 복원 결과를 쓰라.

정답과 해설

1. 정점 3까지의 최단 거리는 3이고 경로는 [0, 2, 3]이다. 정점 2를 처리할 때 정점 1과 정점 3의 거리가 모두 3이 된다. 힙에서는 정점 번호가 작은 1이 먼저 나오지만, 1을 거쳐 3으로 가는 후보는 3 + 3 = 6이므로 현재 값 3을 바꾸지 않는다. 최소 거리의 동률은 최단 거리 계산에 문제를 일으키지 않는다.

2. 거리는 [0, 0, 4, inf]다. 1→2→1을 반복하면 한 바퀴에 비용 4가 추가되므로 더 싼 경로를 만들지 못한다. 일반적으로 음수가 없는 사이클은 제거해도 비용이 늘지 않아 단순 경로만으로 최단 비용을 찾을 수 있다. used는 현재 경로의 중복을 막기 위한 집합이므로, 재귀 호출이 끝나면 정점을 제거해 다른 경로에서 다시 선택할 수 있게 해야 한다.

3. 처음 꺼낼 때 반환하면 3을 답으로 낸다. 실제로는 0→2→1의 비용이 8 - 7 = 1이다. 이 그래프에는 사이클 자체가 없지만 먼저 꺼낸 정점의 거리가 나중에 줄어든다. 따라서 음수 사이클이 없다는 조건만으로 다익스트라의 확정 근거가 복구되지는 않는다. 완성 코드는 -7을 발견한 순간 예외를 발생시킨다.

4. 빠른 풀이에서 정점 0의 자기 간선 후보는 0 + 0 = 0이다. 현재 거리보다 작지 않으므로 등록하지 않는다. 느린 풀이에서는 정점 0이 이미 used에 있으므로 해당 간선을 따라가지 않는다. 두 풀이 모두 최단 거리를 바꾸지 않으며, 출발점 0까지의 복원 경로는 [0]이다. 자기 간선 검사는 기존의 2,187건과 별도로 추가해야 하며, 기존 전수 대조가 모든 형태의 그래프를 다룬다고 해석해서는 안 된다.