다익스트라와 벨만-포드 알고리즘은 언제 구분하여 쓰는가?

간선의 음수 가중치 존재 여부와 음수 사이클의 유무에 따라 구분하여 쓴다. 음수 가중치가 없다면 다익스트라를 쓰고, 있다면 벨만-포드를 써야 한다.

다익스트라는 매번 최단 거리가 가장 짧은 노드를 선택하며 탐색한다. 이미 방문한 노드의 거리는 변하지 않는다고 가정하므로 음수 가중치가 있으면 오동작한다. 대신 우선순위 큐를 써서 모든 간선을 거듭 도는 비용을 피한다.

벨만-포드는 매 단계 모든 간선을 전부 확인하며 거리를 갱신한다. 이 과정을 노드 수만큼 반복하므로 느리지만 음수 가중치를 처리할 수 있다.

V번째 완화에서도 값이 바뀌면 시작점에서 닿을 수 있는 음수 사이클이 있다고 본다. 닿지 않는 곳의 사이클은 이 방법으로 못 찾는다.