最短経路（道順）を求める際のポイント（特定の点を通る場合）：場合の数

• 特定の点を通る場合の、目的地までの最短経路の総数を求める問題です。
• 特定の点までの最短経路と、特定の点から目的地までの最短経路に分けて考えます。
• 特定の点を通らない場合は、(すべての進み方)－(通る場合)で求められます。

最短経路（道順）の問題

図のような格子状の道路がある。点Aから点Bまでの、点Pを通る最短経路の総数を求めなさい。

経路の図

特定の点を通る場合の解法の手順

1. AからPまでの最短経路の総数を求めます。
2. PからBまでの最短経路の総数を求めます。
3. 積の法則より、(AからPまでの総数)× (BからPまでの総数)が求める最短経路の総数となります。

最短経路（道順）の問題の解説

まず、点Aから点Pまでの進み方を考えます。
点Aから点Pに最短で進むには、右に4回と上に1回だけ進むことになります。
このような進み方は、同じものを含む順列の考え方から

   

となります。点Bから点Pへの進み方も同様に考えて、

   

となります。点Aから点Pへの進み方5通りすべてに関して点Pから点Bへの進み方は
同じように4通りずつ存在するので、積の法則より最短経路の総数は

   

と求められます。

参考

チャート式　数研出版