75.다음 그림과 같이 각 구간별 운송거리가 주어졌을 때, 출발지 A에서 목적지 H까지의 최단경로 산출거리는? (단, 구간별 숫자는 km임)

① 6

정답: X

G까지 가장 짧아도 6이고 H로 가려면 1이 더해지므로 6이 되는 경로는 없다.

② 7

정답: O

A에서 B 1·D 2·E 3, C 4·F 4(D 경유), G = F 4 + 2 = 6, H = G 6 + 1 = 7 → 최단경로 A→D→F→G→H = 2 + 2 + 2 + 1 = 7.

③ 8

정답: X

A→D→F→H(2 + 2 + 4)나 A→D→G→H(2 + 5 + 1)로 가면 8이 나온다 — F→G→H로 돌면 1이 준다.

④ 9

정답: X

A→B→C→G→H(1 + 3 + 4 + 1)나 A→D→C→G→H(2 + 2 + 4 + 1)를 고르면 9가 나온다.

⑤ 10

정답: X

아래쪽 A→E→F→G→H(3 + 4 + 2 + 1)로 돌면 10이 나온다 — F까지는 D를 거쳐야 짧다.