가중 방향 그래프에 음수 간선이 있지만 음수 사이클은 없다. 한 출발점 최단 경로를 구할 수 있는 알고리즘은?

1. 1

   Prim

   오답 이유Prim도 최소 신장 트리를 확장하는 알고리즘이며 단일 출발점 최단 경로 알고리즘이 아닙니다.
2. 2

   Dijkstra

   오답 이유Dijkstra는 확정된 최단 거리가 다시 줄지 않는 비음수 가중치 조건이 필요합니다.
3. 3

   Bellman-Ford

   정답 근거Bellman-Ford는 모든 간선을 반복 완화하여 음수 가중치를 처리하고 마지막 완화로 음수 사이클도 탐지할 수 있습니다.
4. 4

   Kruskal

   오답 이유Kruskal은 무방향 그래프의 최소 신장 트리를 구하는 알고리즘입니다.