다음 그래프에 다익스트라 알고리즘을 적용하여 구한 정점 a에서 정점 f… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

정점 a에서 f까지의 최단 거리는 10이며, 경로는 a→b→c→e→d→f이다.
a에서 b까지 1, b→c 간선 2로 c까지 3이 되어 직행 간선 a→c 5보다 짧다. c→e 1로 e까지 4가 되고, e→d 2로 d까지 6이 되어 a→d 8보다 짧다.
f로 가는 간선은 d→f 4와 e→f 7이므로 6+4=10이 4+7=11보다 작다.
11: e에서 f로 바로 가는 경로의 거리로, d를 거치는 경로보다 1 길다.
12: a→d 직행 간선 8에 d→f 4를 더한 거리로 최단이 아니다.
13: 어떤 최단 경로 갱신 과정에서도 f의 최종 거리로 남지 않는다.