음수 간선, 질의 범위, 실패 신호를 한 줄로 맞추면 구현 전 알고리즘 선택이 흔들리지 않습니다.
| 조건 | 선택 | 보장 | 실패 신호 |
|---|---|---|---|
| 음수 없음단일 시작점 | Dijkstra | 가장 짧은 후보부터 거리 확정 | 음수 간선이 섞이면 확정 순서가 깨짐 |
| 음수 간선cycle 검출 | Bellman-Ford | V-1번 완화 후 추가 갱신으로 cycle 확인 | V번째에도 dist가 줄면 음수 사이클 |
| 모든 쌍작은 V | Floyd-Warshall | 중간 정점 k를 허용하며 거리 행렬 갱신 | V가 크면 O(V^3)이 병목 |
| 무가중동일 비용 | BFS | 레벨이 곧 최단 거리 | 가중치가 달라지면 레벨 거리 불가 |
조건: 음수 없음, 단일 시작점
실패: 음수 간선이 섞이면 확정 순서가 깨집니다.
조건: 음수 간선 또는 cycle 검출
실패: V번째 완화에서도 줄면 음수 사이클입니다.
조건: 모든 쌍 거리, 작은 V
실패: V가 크면 O(V^3)이 바로 병목입니다.
조건: 무가중 또는 동일 비용
실패: 가중치가 달라지면 레벨이 거리가 아닙니다.