그림은 정점 A～H 간의 거리를 나타낸 그래프이다. 다익스트라(Dijk… | [7급 국가직 자료구조론] 22년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 22년 1회차

그림은 정점 A～H 간의 거리를 나타낸 그래프이다. 다익스트라(Dijkstra) 알고리즘을 이용하여 정점 A로부터 다른 모든 정점까지의 최단 경로를 구하고, 각 최단 경로의 거리를 짧은 것부터 순서대로 나열한 것은?

3, 11, 13, 15, 16, 20, 21

3, 11, 13, 15, 16, 21, 22

3, 11, 13, 16, 18, 20, 21

3, 11, 13, 16, 18, 21, 22

해설

A로부터의 최단 거리를 오름차순으로 나열하면 3, 11, 13, 15, 16, 20, 21이다.

다익스트라 알고리즘으로 확정 순서를 따라가면 B(3), E(11), C(13)가 먼저 확정된다. 이어 F는 C를 거쳐 13+2=15, H는 E를 거쳐 11+5=16으로 확정된다.

D는 C를 거치면 22이지만 H를 거치면 16+4=20으로 더 짧고, G는 D를 거쳐 20+1=21로 확정된다.

3, 11, 13, 15, 16, 21, 22는 마지막 두 거리가 실제 최단 거리인 D의 20(H 경유), G의 21(D 경유)보다 커서 최단 경로 갱신을 놓친 나열이다.
3, 11, 13, 16, 18, 20, 21은 F를 B 경유 거리(18)로 잡아 C를 거치는 15를 반영하지 못했다.
3, 11, 13, 16, 18, 21, 22는 F와 D·G 모두에서 최단 경로 갱신을 놓친 결과다.

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

이어서 풀어보기