다음 행렬은 일곱 개의 정점(vertex)을 갖는 그래프의 간선(edge)들 간의 거리를 나타낸다. Dijkstra 알고리즘을 적용하여 정점 A로부터 나머지 정점들까지 최단경로를 찾을 때, 이에 해당하는 정점의 순서는? (단,는 두 정점 간에 해당 간선이 없다)
A | B | C | D | E | F | G | |
A | 0 | 4 | 9 | ||||
B | 4 | 0 | 4 | 10 | |||
C | 9 | 4 | 0 | 8 | 1 | ||
D | 10 | 0 | 2 | 5 | |||
E | 8 | 2 | 0 | 6 | |||
F | 5 | 0 | 3 | ||||
G | 1 | 6 | 3 | 0 |
- ①A → B → C → G → D → E → F
- ②A → B → C → G → E → D → F
- ③A → B → C → G → E → F → D
- ④A → B → C → G → F → D → E
선지를 골라 바로 채점해 보세요.
정답 ④
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)