다음은 정점 간의 거리를 표시한 방향 그래프(directed graph… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

다익스트라 방식으로 구하면 시작 정점 0에서 정점 3까지 5, 정점 4까지 7이다.
0→1은 2, 0→1→2는 2+1=3으로 직행 간선(4)보다 짧다.
정점 3: 0→1→2→3 = 3+2 = 5 (직행 8, 0→1→3의 6보다 짧음)
정점 4: 0→1→2→3→4 = 5+2 = 7
정점 3이 5, 정점 4가 8인 조합은 0→1→3→4(2+4+2) 경로의 거리로 최단이 아니다.
정점 3이 8, 정점 4가 11인 조합은 직행 간선 0→3과 0→1→4(2+9)만 본 값이다.
정점 3이 8, 정점 4가 12인 조합은 시작 정점에서 나가는 직행 간선만 본 값이다.