77.다음 그림과 같이 각 구간별 운송거리가 주어졌을 때, 물류센터 S에서 최종 목적지 G까지의 최단 경로 산출거리는? (단, 구간별 운송거리는 km임)

① 12 km

정답: X

G까지 가장 짧은 길도 14km라 12km로 닿는 경로는 그림에 없다.

② 13 km

정답: X

S→A→B→E까지 이미 9km이고 E→G가 5km라 13km로는 G에 닿지 못한다.

③ 14 km

정답: O

S에서 A 4·C 5, B는 A를 거쳐 4 + 1 = 5, D = A 4 + 5 = 9, E = B 5 + 4 = 9, H = C 5 + 5 = 10, G = E 9 + 5 = 14 → S→A→B→E→G 14km.

④ 15 km

정답: X

S→A→D→G(4 + 5 + 6)나 S→A→E→G(4 + 6 + 5)로 가면 15km가 나온다 — B를 거쳐 E로 가야 짧다.

⑤ 16 km

정답: X

최단거리는 S→A→B→E→G 14km라 16km는 더 먼 길을 고른 값이다.