Final Check
최단 경로 선택은 조건, 실패 신호, 로그를 함께 닫는다
마지막 검토에서는 어떤 알고리즘을 썼는지보다 왜 그 알고리즘만 안전한지를 기록해야 합니다.
최종 판정 흐름
01
음수 간선이 있는가?
있으면 Dijkstra를 제거합니다.
Bellman
02
모든 쌍 질의인가?
V가 작으면 행렬 DP가 더 단순합니다.
Floyd
03
단일 시작점 + 비음수인가?
heap 기반 거리 확정이 안전합니다.
Dijkstra
04
검증 로그가 남는가?
stale, INF, parent, cycle 신호를 출력합니다.
audit
자주 틀리는 선택
음수 간선인데 Dijkstra
확정된 거리가 나중에 더 줄어들 수 있어 오답입니다.
모든 쌍인데 단일 소스 반복
소스 수가 많으면 Floyd 또는 다른 전략을 먼저 비교합니다.
INF를 일반 거리처럼 계산
오버플로우와 미도달 노드 출력 정책을 분리합니다.
정리: 최단 경로 문제의 첫 구현 단계는 코딩이 아니라 입력 계약을 확정하는 일입니다.