다음 그래프의 정점 A에서 시작하여 다른 모든 정점까지의 최단 경로를 … | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지

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

다음 그래프의 정점 A에서 시작하여 다른 모든 정점까지의 최단 경로를 찾고자 한다. 다익스트라(Dijkstra) 알고리즘을 사용하여 찾은 정점 G까지의 최단 경로를 바르게 나열한 것은?

A → B → F → G

A → C → F → G

A → D → F → G

A → D → F → H → G

해설

A에서 G까지의 최단 경로는 A → D → F → H → G(거리 5)이다.
다익스트라를 진행하면 먼저 거리 2인 D가 확정되고, D를 거쳐 F가 2+1=3, G가 2+5=7로 갱신된다. 이어 B(3), F(3)가 확정되며 F를 거쳐 C와 H가 각각 4, G는 3+5=8(갱신 없음)이 된다.
H(4)가 확정되면 H를 거친 G까지의 거리가 4+1=5로 갱신되어 최종 최단 거리가 된다.
B와 F를 거쳐 G로 가는 경로: 3+2+5=10으로 더 길다.
C와 F를 거쳐 G로 가는 경로: 6+1+5=12로 더 길다.
D와 F에서 곧바로 G로 가는 경로: 2+1+5=8로, H를 경유하는 5보다 길다.

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

이어서 풀어보기

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

비슷한 기출

7급 국가직 자료구조론 기출문제 암기장 전체 보기

💬 자격증 스터디 커뮤니티헷갈리는 문제, 같이 준비하는 사람들에게 물어보세요

→