答え イ
【解説】
この問題のときかたは、出発地からの各中継地の最も安い運賃を計算しながら進めていく方法(1)と、目的地からの各中継地の最も安い運賃を計算しながら進めていく方法(2)があります。
(1)出発地から計算
まず、出発地から中継地4〜7までの経路の最も安い運賃を求めます。
出発地→中継地4は、中継地1と通る経路、中継地2を通る経路、中継地3を通る経路があり、それぞれの運賃は、
“出発地(6)→中継地1(8)→中継地4”の運賃は、14
“出発地(5)→中継地2(6)→中継地4”の運賃は、11
“出発地(2)→中継地3(6)→中継地4”の運賃は、8
になり、出発地→中継地4の最も安い運賃は、“出発地→中継地3→中継地4”の経路の8になります。(C)
同様に中継地5と中継地6の運賃も求めると
出発地→中継地5の運賃は、“出発地→中継地3→中継地5”の10(D)
出発地→中継地6の運賃は、“出発地→中継地2→中継地6”の10(E)
になります。
次に、出発地から中継地7と中継地8の運賃を計算します。上で求めたCDEを利用して
出発地→中継地7の運賃は、“出発地…→中継地5→中継地7”の17(F)
出発地→中継地8の運賃は、“出発地…→中継地5→中継地8”の13(G)
になります。
最後に出発地から目的地の運賃を計算します。上で求めたFGを利用して
出発地→目的地の運賃は、“出発地…→中継地8→目的地”の20
(イ)になります。
(2)目的地から計算
まず、中継地4〜7から目的地まで経路の最も安い運賃を求めます。
中継地4→目的地は、中継地7を通る経路と、中継地8を通る経路があり、それぞれの運賃は、
“中継地4(10)→中継地7(4)→目的地”の運賃は14
“中継地4(11)→中継地8(7)→目的地”の運賃は17
になり、中継地4→目的地の最も安い運賃は“中継地4→中継地7→目的地”の経路の14になります。(C)
同様に中継地5と中継地6の運賃も求めると、
中継地5→目的地の運賃は、“中継地5→中継地7→目的地”の11(D)
中継地6→目的地の運賃は、“中継地6→中継地8→目的地”の10(E)
になります。
次に、中継地1、中継地2、中継地3から目的地の運賃を計算します。上で求めたCDEを利用して
中継地1→目的地の運賃は、“中継地1→中継地6…→目的地”の17(@)
中継地2→目的地の運賃は、“中継地2→中継地6…→目的地”の15(A)
中継地3→目的地の運賃は、“中継地3→中継地6…→目的地”の20(B)
になります。
最後に出発地から目的地の運賃を計算します。上で求めた@ABを利用して
出発地→目的地の運賃は、“出発地→中継地2…→目的地の20
(イ)になります。