最短経路は何通りあるか

上野竜生です。図が与えられていて最短経路が何通りあるかを求める方法を紹介します。

最短経路の数

スポンサーリンク

基本 ↑に何回・→に何回いくか考える

図のような道がある。今左下の点から右上の点まで最短経路で進む。

最短経路問1

(1) 進み方は何通りあるか?
(2) ×がついた道は通行止めであるとする。進み方は何通りあるか?

裏技:効率よく全部数える こともできますがこの程度なら計算でできます。

最短経路は「↑4つと→6つ」を並べ替えてできる数と等しいことがわかりますね。順番はどうであれ↑4回と→6回進まなくてはいけませんからその順番の決め方だけでいいのです。

(2)は全体から通行止めを通るやり方をひけばいいですね。

答え(1) ↑4つと→6つを並べ替えるやり方に等しい。よって10C4=210通り。

(2) 通行止めの道の左の点をP,右の点をQとする。通行止めを通るやり方を数える。

スタートから点Pまでの行き方は「↑3つ→3つ」の並べ替えなので6C3=20通り。

点Qからゴールまでの行き方は「↑1つ→2つ」の並べ替えなので3C1=3通り。

よって通行止めを通るのは20×3=60通り。

通行止めを通らないのは210-60=150通り。

裏技 効率よく全部数える

下の図のように各頂点への行き方が何通りあるかをすべて書き出すこともできます。

スタート地点からまっすぐ上には1通りしかいけません。まっすぐ右も1通りしかいけません。残りの点については「1つ左の点から→」・「1つ下の点から↑」といけるので1つ左の点と1つ下の点に書かれた数字の和になります。

これを繰り返しゴール地点に書かれる数字が求める場合の数となります。

最短経路の裏技

応用

図のような道路がある。後戻りせずに左下の点から右上の点まで行く方法は何通りあるか?なお斜め方向(/)にも道がある。
最短経路問2

答え斜めを何回通るかで場合分けする。
斜めを1回も通らないとき
↑3個と→5個の並べ替えなので8C3=56通り。
斜めを1回通るとき
↑2個・斜め1個・→4個の並べ替えなので\(\displaystyle \frac{7!}{2!1!4!}=105\)通り。
斜めを2回通るとき
↑1個・斜め2個・→3個の並べ替えなので\(\displaystyle \frac{6!}{1!2!3!}=60\)通り。
斜めを3回通るとき
斜め3個・→2個の並べ替えなので5C2=10通り。
以上より56+105+60+10=231通り。

こちらも図で書くと下のようになります。

最短経路問2答え

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする