- 特定の通路を通る場合の、目的地までの最短経路を求める問題です。
- 特定の通路の入り口までの進み方と、出口からの進み方で分けて考えます。
- 特定の通路を通らない場合は、(すべての進み方)－(通る場合)で求められます。
スポンサーリンク
最短経路（道順）の問題
図のような格子状の道路がある。点Aから点Bまでの、通路Xを通らない最短経路を求めなさい。
最短経路の図
特定の通を通る場合の解法の手順
- 点Aから点Bまでの最短経路の総数を求めます。
- 点Aから通路Xの左側の点までの最短経路の総数を求めます。
- 通路Xの右側の点から点Bまでの最短経路の総数を求めます。
- (AからXの左側まで)×(Xの右側からBまで)で通路Xを通る場合の最短経路の総数を求めます。
- (すべての進み方)－(通る場合)で通らない場合の総数を求めます。
最短経路（道順）の問題の解説
特定の通路を通らない場合は、余事象の考え方を用いて全体から通る場合を引くことで求めます。
まず、最短経路の総数を求めます。
点Aから点Bまでの最短経路は、上に4回と右に5回進むことになるので、その総数は
となります。
次に、点Xを通る最短経路の総数を求めます。
通路Xを通る最短経路なので、点A→通路Xの左側の点→通路X→通路Xの右側の点→点B
の順に進むことになります。
点Aから通路Xの左側の点までの最短経路は、上に2回と右に1回進むことになるので、
総数は
であり、 通路Xの左側の点から通路Xを通って通路Xの右側の点に進む進み方は1通り、 通路Xの右側の点から点Bまでの最短経路は、上に2回と右に3回進むことになるので、
となります。
よって、通路Xを通る最短経路は
存在することになります。
以上より、通路Xを通らない最短経路は
存在することが求められます。
通らない場合を求めるときは、特に最後の引き算を忘れないように注意が必要です。
参考
チャート式 数研出版