Shortest Path Gate
최단 경로는 입력 조건 3개로 먼저 고른다
가중치 부호, 질의 범위, 그래프 특성을 먼저 확인하면 Dijkstra를 잘못 쓰는 실수를 줄일 수 있습니다.
선택 질문 순서
01
간선 가중치가 모두 0 이상인가?
음수가 있으면 거리 확정 방식이 깨질 수 있습니다.
Dijkstra
02
음수 간선 또는 음수 사이클 검출이 필요한가?
모든 간선을 반복 완화하며 안전하게 확인합니다.
Bellman-Ford
03
모든 정점 쌍의 거리가 필요한가?
정점 수가 작을 때 행렬 DP가 가장 단순합니다.
Floyd
04
모든 간선 비용이 같은가?
가중치가 없거나 모두 같으면 레벨 탐색이 충분합니다.
BFS
알고리즘별 안전 조건
Dijkstra
단일 시작점, 음수 간선 없음, sparse 그래프에서 빠름.
Bellman-Ford
음수 간선 허용, 추가 완화로 음수 사이클 검출.
Floyd-Warshall
모든 쌍 질의, V가 작고 행렬 결과가 필요한 경우.
BFS
무가중 또는 동일 가중치, 레벨이 곧 거리인 경우.
핵심: “빠른 알고리즘”보다 “입력 조건을 만족하는 알고리즘”을 먼저 선택합니다.