문제
다음 그래프 알고리즘 중 가중치가 음수인 간선이 있는 그래프에서 최단 경로를 구할 때 사용할 수 없는 것은?
① 벨만-포드 알고리즘 ② 플로이드-워셜 알고리즘 ③ 다익스트라 알고리즘 ④ SPFA(Shortest Path Faster Algorithm)
정답
3번
해설
다익스트라 알고리즘은 그리디 접근법을 사용하여 한 번 방문한 노드의 최단 거리는 확정된다고 가정하는데, 음수 가중치가 있으면 이후에 더 짧은 경로가 발견될 수 있어 올바른 결과를 보장할 수 없다. 벨만-포드 알고리즘은 음수 간선을 처리할 수 있고, 플로이드-워셜은 음수 사이클만 없으면 가능하며, SPFA도 음수 간선을 처리할 수 있다.