최단 경로 알고리즘의 선택 기준은 무엇인가?

가중치가 있는지, 음수가 섞였는지로 갈린다. 가중치가 없으면 BFS를 쓴다. 음수가 없으면 다익스트라를 쓴다. 0인 간선은 있어도 된다. 음수가 있으면 벨만-포드를 쓴다.

BFS는 모든 노드를 동일한 거리로 계산하므로 가중치가 없을 때 가장 빠르다. 다익스트라는 우선순위 큐를 이용해 최단 거리를 확정하며 탐색 범위를 좁힌다.

벨만-포드는 모든 간선을 반복적으로 확인하여 음수 사이클이 있는지 판단한다. 다익스트라와 달리 음수 가중치를 다룬다. 다만 시작점에서 닿는 음수 사이클이 있으면 최단 거리 자체가 없고, 벨만-포드는 그것을 알려 줄 뿐이다.

간선 수와 가중치 조건을 먼저 확인하면 정확성을 지키면서 불필요한 계산을 피할 수 있다.