알고리즘 8장
최단 경로: Dijkstra (음수 간선 없음)
Dijkstra는 우선순위 큐에서 가장 짧은 후보 거리를 꺼내며 음수 간선이 없는 그래프의 최단 거리를 확정합니다.
다익스트라 거리 상태 변화
거리 확정
S
0
A
3
B
5
C
INF
pop S
→
relax A/B
→
skip stale
다익스트라 확정 거리 불변식
점검
dist 초기화
시작점은 0, 나머지는 INF로 둡니다.
pq pop
현재 가장 작은 후보 거리를 꺼냅니다.
relax
더 짧은 경로를 찾으면 dist와 pq를 갱신합니다.
stale skip
꺼낸 거리와 dist가 다르면 오래된 항목이라 건너뜁니다.