다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그래프의 간선들 간의 거리를 나타낸다. 표에서 무한대 기호 ∞는 해당 간선이 없음을 나타낸다. 정점 A에서 나머지 네 개의 정점들에 도달하기 위한 최단경로들의 합은 얼마인가?
to
from
ABCDE
A025∞3
B∞0∞410
C∞∞062
D∞∞∞0∞
E∞∞120
1
12
2
14
3
15
4
16
해설

A에서 나머지 정점까지의 최단경로 합은 14이다.

다익스트라 알고리즘으로 B = 2, E = 3이 먼저 확정된다. E를 거치면 C는 3 + 1 = 4로 직접 가는 5보다 짧고, D는 3 + 2 = 5로 B를 거치는 2 + 4 = 6보다 짧다.

합계: 2 + 4 + 5 + 3 = 14

  • A→C를 직접 간선 5로 두면 합이 15가 되어 E를 경유하는 더 짧은 경로를 놓친다.

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

이어서 풀어보기

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