음수 간선과 음수 사이클이 모두 존재할 수 있는 그래프에서 모든 정점 쌍의 최단 경로를 구하기 전에 탐지해야 할 사항은?

1. 1

   음수 사이클 존재 여부

   정답 근거도달 가능한 음수 사이클은 반복할수록 비용을 낮춰 유한 최단 경로를 없애므로 먼저 탐지해야 해 정답이다.
2. 2

   최소 신장 트리의 개수

   오답 이유최소 신장 트리 개수는 무방향 연결 그래프의 전체 연결 비용 문제이며 모든 쌍 최단 경로 정의와 무관하다.
3. 3

   그래프의 위상 정렬 순서

   오답 이유위상 정렬은 DAG에서만 가능하며 일반 가중 그래프 최단 경로의 선행 검사가 아니다.
4. 4

   모든 정점의 진입 차수 동일 여부

   오답 이유진입 차수의 동일 여부는 최단 거리 존재 조건이 아니다.