図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。 A1地点から、C2地点を経由して、D4地点へ行く最短経路は何通りあるか。
答え イ
【解説】 図2のB2に至る最短経路の数は、B1に至る最短経路の数とA2に至る最短経路の数の和であり、C2に至る最短経路の数は、C1に至る最短経路の数とB2に至る最短経路の数の和である。 同じように、C2地点からD4地点へ行く最短経路を図2と同様の方法で求める。 ここで、C2地点への最短経路数が3なので、最短経路を求める図は となり、A1地点から、C2地点を経由して、D4地点へ行く最短経路は9(イ)通りである。
【キーワード】 ・最短経路探索
戻る 一覧へ 次へ