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보다 먼저 확정된다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 16년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기