図中の矢印に記した数値は，各区間の運賃を表す。出発地から目的地までの経路のうち，最も安い総運賃は幾らか。

図中の矢印に記した数値は，各区間の運賃を表す。出発地から目的地までの経路のうち，最も安い総運賃は幾らか。

解答：イ

＜解説＞

1. 中継地4,5,6に行くまでの一番安い経路を求める。
   • 出発地-(2)→中継地3-(6)→中継地4 運賃( 8)
   • 出発地-(2)→中継地3-(8)→中継地5 運賃(10)
   • 出発地-(5)→中継地2-(5)→中継地6 運賃(10)
2. 次に,中継地4,5,6から目的地までの一番安い経路を求める。
   • 中継地4-(10)→中継地7-(4)→目的地 運賃(14)
   • 中継地5-( 7)→中継地7-(4)→目的地 運賃(11)
   • 中継地6-( 3)→中継地8-(7)→目的地 運賃(10)
3. 1と2より一番運賃の安い経路を求めると中継地6を通過する経路が一番安いことが分かる。
   出発地-(5)→中継地2-(5)→中継地6-( 3)→中継地8-(7)→目的地 運賃(20)