【場合の数】最短経路の数｜組合せの利用とパスカルの方法

今回は、最短経路の数の問題について解説します。

最短経路の数

今回は、最短経路の数の問題について解説したいと思います。

組合せで考える

最短経路の問題は、組合せで考えることができます。例えば、次の経路でAから出発してBまで最短で行くことを考えます。このとき、AからBまでの最短経路は何通りあるでしょうか。

AからBまで行く最短経路は、例えば、次のような経路が考えられます。

このことから、上向きの矢印↑2本と、右向きの矢印→3本の並べ替えで経路が決まっていることに気がつきます。すなわち、次図の左のように並べた場合、右のように経路が決まるのです。

よって、矢印の並び替えで経路が決まっているのです。

以上より、同じものを含む順列となるので、AからBまでの最短経路は\( {}_5 \mathrm{C}_2 = 10 \)（通り）と求めることができます。

以上が、教科書に載っている一般的な解法です。

経路の数を書き込む方法

最短経路の問題では、組合せの利用による解法の他に経路の数を書き込む解法というものがあります。大学受験向け参考書には載っていることが少ない（もしくは別解として掲載されている）解法ですが、複雑な経路なほど、こちらのやり方の方が簡単なので、本記事ではこちらの解法をメインに解説していきます。この方法をパスカルの方法と呼びます。

経路の数を書き込む解法にはルールがあるので、まずはそちらを紹介します。

左側の交差点と真下の交差点の行き方の数を足すイメージです。

これを用いて、最短経路を求めることになります。

先ほどの例をもう一度考えてみましょう。次の経路でAから出発してBまで最短で行くことを考えます。このとき、AからBまでの最短経路は何通りあるでしょうか。

最短経路の問題では、交差点の部分に行き方の数を書き込んでいきます。今回は、Aから出発します。以下のように、赤印をつけた箇所のAからの最短経路の行き方は何通りあるでしょうか。

Aから赤印まで最短経路で行く方法は、下図に示すように、Aから左にいく1通りしかないことがわかります。それ以外の経路で行くと、全て遠回りになってしまいます。交差点までの経路を考える際には、遠回りの経路は考えず、最短経路のみを考えます。

では、次に示す青印までの経路はどうでしょうか。

こちらも同じく、Aから青印まで直接右に進んでいく1通りしかありません。

同様の考え方により、以下の5個の交差点までの最短経路が埋まります。全て1通りです。

さて、残りの交差点部分も全て埋めていきますが、残りの部分は先ほど紹介した経路の数を書き込むルールに従って埋めていけば良いです。例えば、次のような感じです。

あとは、これを繰り返して行きます。最終的には、次のようになります。

よって、Bまでの最短経路は10通りと求めることができます。

ある地点を通る場合

問題文によっては、条件があることがあります。よくある条件の一つが、ある地点を通る場合において、最短経路の数を求める問題です。このように指定がある場合は、道を工夫して変える必要があります。

例えば、次の経路で、必ずCを通り、Aから出発してBまで最短で行くことを考えます。このとき、AからBまでの最短経路は何通りあるでしょうか。

この場合、Cを通らない道は全て削り、道を次のように変えます。

あとは書き込んでいきます。

よって、この場合は6通りであるとわかります。

ある地点を通らない場合

よくある条件のもう一つの例として、ある地点を通らない場合において、最短経路の数を求める問題が挙げられます。こちらも同様に、道を工夫して変える必要があります。

例えば、次の経路で、Pは通らずに、Aから出発してBまで最短で行くことを考えます。このとき、AからBまでの最短経路は何通りあるでしょうか。

Pは通らないので、次のように道を削ることができます。

あとは書き込んでいます。

よって、この場合は6通りであるとわかります。

このように、直接書き込んでいく方法はある地点を通らない場合に特に有効です。

例題と演習

では、具体例を見ていきましょう。

例題：最短経路の数

演習：最短経路の数

おわりに

今回は、パスカルの方法で最短経路の数を求める方法を解説しました。

最後までお読みいただき、ありがとうございました。