모든 간선 가중치가 0 이상인 희소 방향 그래프에서 한 출발점으로부터 다른 정점까지의 최단 거리를 구하려 한다. 적절한 알고리즘은?

1. 1

   Dijkstra

   정답 근거Dijkstra는 음수 간선이 없는 단일 출발점 최단 경로를 우선순위 큐로 효율적으로 구하므로 정답이다.
2. 2

   Bellman-Ford

   오답 이유Bellman-Ford도 단일 출발점 문제를 풀지만 음수 간선 허용이 필요할 때의 더 일반적이고 느린 선택이다.
3. 3

   Floyd-Warshall

   오답 이유Floyd-Warshall은 모든 정점 쌍 최단 경로를 O(V³)에 구하므로 희소 단일 출발점 조건에 과하다.
4. 4

   Kruskal

   오답 이유Kruskal은 무방향 가중 그래프의 최소 신장 트리를 구하며 최단 경로 알고리즘이 아니다.