58.다음 네트워크에서 출발지 S로부터 도착지 F까지 최단경로의 거리는 얼마인가? (단, 경로별 숫자는 km임)

① 23 km

정답: X

S에서 F까지 가장 짧은 길도 25km라 23km로 닿는 경로는 없다.

② 24 km

정답: X

24km가 되는 경로는 없다 — b를 거쳐 c까지 13km, d까지 15km를 지나야 25km다.

③ 25 km

정답: O

a 8·b 10, c = b 10 + 3 = 13(직접 15보다 짧다), d = c 13 + 2 = 15, e = c 13 + 4 = 17, F = d 15 + 10 = 25(e 경유 26, c 경유 27, a 경유 27) → S→b→c→d→F 25km.

④ 26 km

정답: X

S→b→c→e→F(10 + 3 + 4 + 9)로 가면 26km다 — d를 거치면 1km 짧다.

⑤ 27 km

정답: X

S→a→F(8 + 19)나 S→b→c→F(10 + 3 + 14)로 가면 27km가 나온다.