Dijkstra·완화·오래된 큐 항목
음수가 아닌 가중치에서 최소 비용 후보를 꺼내고 실제 경로를 복원합니다.
길마다 비용이 다르면 BFS의 이동 횟수만으로 부족합니다. 목표는 현재 거리의 개선인 완화와 최소 힙의 역할을 이해하는 것입니다. 힙·BFS·부모 기록을 복습하세요.
개념과 약속
입력은 문자열 정점별 (이웃, 비용) 목록입니다. 비용은 0 이상의 Python 정수 또는 유한한 float이며 bool은 받지 않습니다. 0 비용 간선도 허용합니다. 초기 거리는 출발 정점이 0, 나머지 정점이 무한대입니다. u까지의 비용에 간선 비용 w를 더한 후보가 v의 현재 거리보다 작으면 갱신하는 일을 완화라고 합니다.
이 교재에서는 정수 비용을 권합니다. Python 정수는 고정 폭의 범위에 제한되지 않아 큰 정수도 정확히 더할 수 있습니다. float는 반올림되는 근삿값이며 각 간선이 유한해도 합이 float 범위를 넘을 수 있습니다. 이 구현은 탐색 중 그런 합을 만나면 ValueError로 호출 전체를 중단합니다. 수치 범위 오류를 '도달 불가'와 같은 inf·빈 경로로 돌려주지 않습니다. 정수와 float를 섞은 합이 변환 한도를 넘는 경우도 같은 오류 정책입니다.
최소 힙에서 현재 비용이 가장 작은 항목을 꺼냅니다. 더 좋은 경로를 발견할 때 새 항목을 넣고 예전 항목은 그대로 남길 수 있습니다. 꺼낸 비용이 현재 거리와 다르면 오래된 항목이라 버립니다. 같은 거리에서는 갱신하지 않아 0 비용 사이클에서도 부모가 불필요하게 바뀌지 않습니다. 정점 이름은 문자열이므로 비용 동률 시 힙의 두 번째 값 비교도 가능합니다.
한 단계가 아니라 합계 비용을 줄인다
거리 0에서 두 이웃을 갱신한다. 남은 6의 항목도 무시한다. 각 단계의 값과 전환 이유를 비교합니다.
자료구조·알고리즘 · 상태와 관계
한 단계가 아니라 합계 비용을 줄인다
숫자는 방향 간선의 비용이며 경로 A→C→B→D의 합은 1+2+1=4입니다.
화살표는 이동 가능한 방향입니다. 강조한 C→B 완화가 B의 비용을 4에서 3으로 줄입니다. 도착 D까지는 4입니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 A 처리부터 오래된 D까지 진행합니다.
관계도의 보충 설명
| 구분 | 전체 도표의 내용 |
|---|---|
| 관계 설명 | A에서 C로 가는 비용은 1, A에서 B로 가는 비용은 4, C에서 B로 가는 비용은 2, C에서 D로 가는 비용은 5, B에서 D로 가는 비용은 1인 방향 그래프다. C를 거치면 B까지의 거리 4를 3으로 개선한다. |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| A 처리 거리 0에서 두 이웃을 갱신한다. |
|
|
| C 처리 더 짧은 B 경로를 찾는다. |
|
|
| B 처리 D까지의 거리를 4로 낮춘다. |
|
|
| 오래된 B 거리 4의 B 항목은 현재 최단거리 3과 다르다. |
|
|
| D 처리 최단거리 4의 D를 처리한다. |
|
|
| 오래된 D 남은 6의 항목도 무시한다. |
|
|
한 단계가 아니라 합계 비용을 줄인다
거리 0에서 두 이웃을 갱신한다. 남은 6의 항목도 무시한다. 각 단계의 값과 전환 이유를 비교합니다.
자료구조·알고리즘 · 상태와 관계
한 단계가 아니라 합계 비용을 줄인다
숫자는 방향 간선의 비용이며 경로 A→C→B→D의 합은 1+2+1=4입니다.
화살표는 이동 가능한 방향입니다. 강조한 C→B 완화가 B의 비용을 4에서 3으로 줄입니다. 도착 D까지는 4입니다.
이 예의 조건
- 본문과 전체 도표의 예를 따라 A 처리부터 오래된 D까지 진행합니다.
관계도의 보충 설명
| 구분 | 전체 도표의 내용 |
|---|---|
| 관계 설명 | A에서 C로 가는 비용은 1, A에서 B로 가는 비용은 4, C에서 B로 가는 비용은 2, C에서 D로 가는 비용은 5, B에서 D로 가는 비용은 1인 방향 그래프다. C를 거치면 B까지의 거리 4를 3으로 개선한다. |
| 관찰·상황 | 값·보충 정보 | 변화·이유 |
|---|---|---|
| A 처리 거리 0에서 두 이웃을 갱신한다. |
|
|
| C 처리 더 짧은 B 경로를 찾는다. |
|
|
| B 처리 D까지의 거리를 4로 낮춘다. |
|
|
| 오래된 B 거리 4의 B 항목은 현재 최단거리 3과 다르다. |
|
|
| D 처리 최단거리 4의 D를 처리한다. |
|
|
| 오래된 D 남은 6의 항목도 무시한다. |
|
|
손으로 상태 추적하기
간선 A→B:4, A→C:1, C→B:2, B→D:1, C→D:5입니다.
| 꺼낸 항목 | 완화 결과 |
|---|---|
| A,0 | B=4, C=1 |
| C,1 | B=3, D=6 |
| B,3 | D=4 |
| B,4 | 현재 B=3과 달라 버림 |
| D,4 | 최단 비용 4 |
| D,6 | 현재 D=4와 달라 버림 |
직접 실행하기
아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.
import heapq
import math
def dijkstra(graph, start):
vertices = set(graph)
for edges in graph.values():
for target, weight in edges:
if type(weight) not in (int, float) or weight < 0 or (type(weight) is float and not math.isfinite(weight)):
raise ValueError("nonnegative int or finite float weights required")
vertices.add(target)
if start not in vertices:
raise ValueError("start must be a vertex")
distances = {vertex: math.inf for vertex in vertices}
distances[start] = 0
parent = {start: None}
queue = [(0, start)]
while queue:
cost, vertex = heapq.heappop(queue)
if cost != distances[vertex]:
continue
for target, weight in graph.get(vertex, []):
try:
candidate = cost + weight
except OverflowError as error:
raise ValueError("path cost exceeds float range") from error
if type(candidate) is float and not math.isfinite(candidate):
raise ValueError("path cost exceeds float range")
if candidate < distances[target]:
distances[target] = candidate
parent[target] = vertex
heapq.heappush(queue, (candidate, target))
return distances, parent
def restore_path(parent, target):
if target not in parent:
return []
path = []
while target is not None:
path.append(target)
target = parent[target]
return path[::-1]
graph = {"A": [("B", 4), ("C", 1)], "B": [("D", 1)], "C": [("B", 2), ("D", 5)], "D": [], "E": []}
distance, parent = dijkstra(graph, "A")
print(sorted(distance.items()))
print(restore_path(parent, "D"))
zero, _ = dijkstra({"A": [("B", 0)], "B": []}, "A")
print(zero["B"])실행 결과:
[('A', 0), ('B', 3), ('C', 1), ('D', 4), ('E', inf)]
['A', 'C', 'B', 'D']
0왜 맞고 언제 끝나는가
현재 최소 비용 후보까지의 더 싼 경로가 나중에 나타나려면, 아직 처리하지 않은 정점을 거친 뒤 비용이 줄어야 합니다. 음수가 아닌 간선에서는 그런 감소가 불가능해 꺼낸 최소 거리가 확정됩니다. 각 유효한 완화는 기존 경로의 비용보다 작을 때만 기록합니다. 오래된 후보는 추가 완화를 하지 않아 불필요한 반복을 막습니다.
비용과 적용 범위
이 중복 항목 힙 버전은 비교·덧셈을 한 단위로 보는 작은 수 모델에서 O((V+E) log(V+E)) 시간과 O(V+E) 추가 공간으로 설명할 수 있습니다. 매우 큰 정수는 자릿수에 따른 연산·저장 비용을 더 봐야 합니다. 단순 그래프에서는 흔히 O((V+E) log V)로 씁니다. 음수 간선은 거부합니다. 음수가 필요하면 Bellman–Ford 같은 별도 알고리즘이나 다음 모든 쌍 알고리즘을 검토해야 합니다.
A→B:1e308, B→C:1e308에서 각각의 float는 유한하지만 합은 무한대로 넘칩니다. 위 함수는 이를 명시적으로 거부합니다. 두 비용을 정수 10**308로 주면 C의 정확한 비용 2 * 10**308과 경로 A,B,C를 얻습니다. float의 반올림 자체를 없애는 구현은 아니며 정확한 비용 비교가 필요하면 정수 단위를 정해 입력하세요.
스스로 풀어 보기
- A→B:2, A→C:5, C→B:-10에서 B를 너무 일찍 확정하는 이유를 설명하세요.
- 도달하지 못하는 정점 E의 거리와 경로 반환은 무엇인가요?
힌트
- C를 거치면 비용이 감소합니다.
- 무한대 거리와 부모 없음은 다릅니다.
해설
- B=2를 확정한 뒤 C를 거친 -5가 나타납니다. 음수는 최소 후보 확정의 논리를 깨므로 이 구현은 시작 전에 거부합니다.
- 거리는
inf, 복원은[]입니다. 아직 도달할 경로를 찾지 못했다는 표현이며 무한대 비용의 실제 간선을 넣는 것이 아닙니다.
흔한 오해
엄격히 양수만 가능한 것은 아닙니다. 필요한 조건은 음수가 없다는 것입니다. 반대로 음수 사이클이 없다고 Dijkstra를 사용할 수 있는 것도 아닙니다.
복습과 다음 연결
음수가 아닌 조건의 공식 수업 설명은 MIT Dijkstra 강의에서 확인할 수 있습니다. 다음 Warshall은 비용 대신 가능 여부를 다룹니다.