자료 구조와 알고리즘
간선에 방향이 없는 그래프에서 간선의 가중치(거리)가 S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3, A−T: 6이다. 다익스트라 알고리즘으로 S에서 T까지의 최단 경로를 구했을 때, 그 경로와 길이는?
- AS→A→C→T, 길이 8
- BS→B→A→C→T, 길이 7
- CS→B→C→T, 길이 9
정답과 해설 보기
정답: B. S→B→A→C→T, 길이 7
다익스트라 알고리즘은 거리가 확정되지 않은 정점 중 가장 가까운 것을 확정하고, 그 이웃 정점의 거리를 갱신하는 것을 반복합니다. S(0)에서 B가 1로 확정되고, B를 거치면 A는 1 + 2 = 3으로 직접 가는 4보다 짧아집니다. A(3)를 확정하면 C는 3 + 1 = 4, T는 3 + 6 = 9가 되고, C(4)를 확정하면 T는 4 + 3 = 7로 갱신됩니다. 따라서 최단 경로는 S→B→A→C→T이고 길이는 7입니다. S→A→C→T(8)는 S−A를 직접 지나는 만큼 길고, S→B→C→T(9)는 B−C의 5가 크기 때문에 길어집니다.