다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
다음 표는 A, B, C, D, E 등 다섯 개의 정점을 갖는 어느 그래프의 간선들 간의 거리를 나타낸다. 표에서 무한대 기호 ∞는 해당 간선이 없음을 나타낸다. 정점 A에서 나머지 네 개의 정점들에 도달하기 위한 최단경로들의 합은 얼마인가?
| to from | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 2 | 5 | ∞ | 3 |
| B | ∞ | 0 | ∞ | 4 | 10 |
| C | ∞ | ∞ | 0 | 6 | 2 |
| D | ∞ | ∞ | ∞ | 0 | ∞ |
| E | ∞ | ∞ | 1 | 2 | 0 |
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를 경유하는 더 짧은 경로를 놓친다.
오류나 개정된 내용이 보이면 알려주세요