Dijkstra
음수 간선 없음
단일 시작점에서 각 정점까지의 거리를 빠르게 확정한다.
최단 경로는 입력 조건을 먼저 읽고 고른다
음수 간선, 시작점 수, 모든 쌍 질의 여부가 알고리즘 선택을 결정한다. Dijkstra는 만능이 아니다.
Bellman-Ford
음수 간선 허용
느리지만 음수 간선과 음수 사이클 검출에 안전하다.
Floyd-Warshall
모든 쌍 거리
정점 수가 작고 모든 도시 쌍 질의가 필요할 때 쓴다.
BFS
가중치 없음
간선 비용이 모두 같다면 큐 기반 BFS가 최단 거리다.