우선순위 큐로 확정
가중치가 모두 0 이상이면 우선순위 큐 기반 Dijkstra를 우선 검토합니다.
최단 경로는 음수 간선과 질의 범위로 선택한다
Dijkstra, Bellman-Ford, Floyd-Warshall은 모두 거리 배열을 갱신하지만 허용 입력과 질의 범위가 다릅니다.
반복 완화로 음수 대응
음수 간선이나 음수 사이클 검출이 필요하면 Bellman-Ford를 선택합니다.
행렬 DP로 전체 계산
정점 수가 작고 전체 쌍 거리가 필요하면 Floyd-Warshall이 단순합니다.
초기값
시작점 0, 나머지 INF, 부모 배열 초기화를 한 번에 확인합니다.
완화 조건
더 짧은 거리일 때만 갱신하고 INF 더하기를 피합니다.
미도달
도달 불가 노드의 출력 규칙을 문제 요구와 맞춥니다.