다음 그래프는 각 정점들 사이의 거리를 간선에 나타낸 것이다. 정점 0… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음 그래프는 각 정점들 사이의 거리를 간선에 나타낸 것이다. 정점 0에서 각 정점 1, 2, 3, 4, 5까지의 최단경로를 Dijkstra 최단경로 알고리즘으로 구할 때, 최단경로가 발견된 정점들의 순서로 옳은 것은?
1
0, 2, 3, 1, 5, 4
2
0, 2, 1, 3, 4, 5
3
0, 2, 4, 1, 3, 5
4
0, 1, 5, 2, 3, 4
해설
Dijkstra 알고리즘으로 최단경로가 확정되는 순서는 0, 2, 1, 3, 4, 5이다.
매번 거리가 가장 짧은 미확정 정점을 확정하고 인접 정점의 거리를 갱신한다.
정점 2 확정(3) → 1은 3+6=9, 3은 3+15=18로 갱신
정점 1 확정(9) → 5는 9+30=39
정점 3 확정(18) → 4는 기존 20 유지
정점 4 확정(20) → 5는 20+3=23으로 갱신
정점 5 확정(23)
- 0, 2, 3, 1, 5, 4: 2를 거친 경로로 1의 거리가 9가 되어 3(18)보다 먼저 확정된다.
- 0, 2, 4, 1, 3, 5: 4의 거리 20은 1(9)·3(18)보다 크므로 먼저 확정될 수 없다.
- 0, 1, 5, 2, 3, 4: 처음에는 거리 3인 2가 가장 가까워 먼저 확정되어야 한다.
오류나 개정된 내용이 보이면 알려주세요
