최단 경로 점검표

최단 경로 입력 조건

음수 간선, 시작점 범위, 모든 쌍 요구를 먼저 판정하면 알고리즘 선택과 반례 설계가 단순해집니다.

단일 시작Dijkstra 음수 간선Bellman-Ford 모든 쌍Floyd-Warshall
no negative

Dijkstra

음수 간선이 없고 시작점이 하나라면 가장 먼저 검토합니다. stale 큐 항목을 건너뛰는 조건을 로그로 확인합니다.

negative edge

Bellman-Ford

음수 간선이나 음수 사이클 판정이 필요하면 선택합니다. 마지막 완화에서 갱신되는지 따로 기록합니다.

all pairs

Floyd-Warshall

정점 수가 작고 모든 쌍 질의가 많을 때 적합합니다. INF 덧셈과 대각선 초기값을 먼저 검증합니다.

1. 조건 읽기가중치 부호, 정점 수, 질의 범위를 분리합니다.
2. 알고리즘 고정정확성 조건을 만족한 뒤 성능을 비교합니다.
3. 반례 넣기음수 간선, 미도달 노드, 다중 최단 경로를 포함합니다.
4. 로그 확인relax 횟수와 오버플로우 위험을 따로 봅니다.