Dijkstra 알고리즘을 이용하여 다음 그래프의 정점 A에서 각 정점… | [7급 국가직 자료구조론] 16년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 16년 1회차
Dijkstra 알고리즘을 이용하여 다음 그래프의 정점 A에서 각 정점으로의 최단경로를 구할 때, 최단경로 발견 순서가 정점 G 바로 다음인 정점은? (단, 간선 옆의 수는 각 정점들 사이의 거리를 나타낸다)
1
정점 C
2
정점 D
3
정점 E
4
정점 F
해설
정점 G 바로 다음으로 최단경로가 확정되는 정점은 C이다.
A에서 시작해 거리가 최소인 정점을 차례로 확정하면 B(4) → F(5, A–B–F) → G(9, F 경유) → C(10, B 경유) → E(11, G 경유) → D(12, C 경유) 순이다.
- 정점 D: B 경유 13이었다가 C 확정 후 12로 갱신되며, 가장 마지막에 확정된다.
- 정점 E: G 확정 후 거리가 11로 갱신되지만 C의 10보다 커서 C 다음에 확정된다.
- 정점 F: A–B–F 경로 5로 G보다 먼저 확정된다.
오류나 개정된 내용이 보이면 알려주세요
