与えられた街路図において、点Pから点Qへ行く最短経路について、次の3つの場合について経路の数を求める問題です。 (1) 全ての経路の数 (2) 点Rを通る経路の数 (3) ×印の箇所を通らない経路の数
2025/6/2
1. 問題の内容
与えられた街路図において、点Pから点Qへ行く最短経路について、次の3つの場合について経路の数を求める問題です。
(1) 全ての経路の数
(2) 点Rを通る経路の数
(3) ×印の箇所を通らない経路の数
2. 解き方の手順
この問題は図に各交差点までの最短経路数を書き込むことで解くことができます。
(1) 総数
PからQまでの最短経路数は、図の通り792通りです。
(2) Rを通る経路
PからRまでの経路数とRからQまでの経路数をそれぞれ求め、それらを掛け合わせることで計算できます。図より、Rを通る経路数は350通りです。
(3) ×印の箇所を通らない経路
PからQまでの全ての経路数から、×印の箇所を通る経路数を引くことで計算できます。図より、×印の箇所を通らない経路数は542通りです。
3. 最終的な答え
(1) 総数: 792通り
(2) Rを通る経路: 350通り
(3) ×印の箇所を通らない経路: 542通り