Dijkstra
음수 간선이 없을 때 가장 가까운 정점부터 확정한다
우선순위 큐에서 가장 작은 거리 후보를 꺼내고, 이미 더 짧은 기록이 있으면 stale 후보로 버립니다.
예시 그래프와 거리 후보
2
5
1
2
3
1
2
3
4
우선순위 큐 판정
pop
정점 1, 거리 0
확정
relax
1→2 = 2, 1→3 = 5
push
pop
정점 2, 거리 2
확정
relax
2→3 = 3, 2→4 = 4
갱신
pop
정점 3, 거리 5 후보
stale skip
조건
모든 간선 가중치가 0 이상이어야 거리 확정이 안전합니다.
자료구조
min-heap에는 “아직 검토할 거리 후보”만 넣습니다.
검증 로그
pop 거리 > dist[v]이면 오래된 후보라 건너뜁니다.
핵심: Dijkstra의 정확성은 “한 번 확정한 거리가 다시 짧아지지 않는다”는 비음수 조건에 기대고 있습니다.