다음과 같은 방향 그래프에 대하여 Dijkstra의 알고리즘을 적용하여… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 19년 1회차
다음과 같은 방향 그래프에 대하여 Dijkstra의 알고리즘을 적용하여 최단경로를 구하고자 한다. 노드 a에서 시작하여 노드 f로 가는 최단 경로를 찾아 가는 과정에서 노드 a에서부터 다른 노드까지 최단 경로를 차례로 알게 된다. 이 과정에서 알게 되는 최단 경로의 노드 순서로 옳은 것은?
1
a - b - c - d - e - f
2
a - b - d - f
3
a - c - d - f
4
a - c - d - e - f
해설
Dijkstra 알고리즘이 최단 거리를 확정하는 노드 순서는 a-b-c-d-e-f이다.
매 단계 거리가 가장 작은 미확정 노드를 확정한다. a(0) 다음 b(2)를 확정하면 c가 2+1=3으로 갱신되어 c(3)가 확정된다.
c에서 d가 3+2=5로 갱신되어 d(5), d에서 e가 5+1=6으로 갱신되어 e(6), 마지막으로 e에서 f가 6+1=7로 f(7)가 확정된다.
- a-b-d-f는 비용 2+4+3=9인 경로로, 최단 경로도 확정 순서도 아니다.
- a-c-d-f는 a에서 c로 직접(4) 가는 경로로, c는 b를 거친 3이 더 짧으며 확정 순서와도 다르다.
- a-c-d-e-f는 a→f 최단 경로(a-b-c-d-e-f, 비용 7)와도 다르고, b의 확정을 빠뜨린 순서이다.
오류나 개정된 내용이 보이면 알려주세요
