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