最短経路の問題の解き方｜交差点に数を足す方法と公式

最短経路の問題は何を聞いている？

最短経路の問題は、碁盤の目のような道で、スタートからゴールまで遠回りをせずに行く道順が何通りあるかを数える問題です。ゴールが右上にあれば、進む向きは右と上の2つだけで、左や下へ戻る道順は数えません。

たとえば「右に4区画・上に3区画」のゴールなら、どの道順も「右4回・上3回」の計7回の移動でできています。違うのは、7回のうちどこで右に進むかという順番だけです。これが、組合せの公式で数えられる理由です。

組合せ（nCr）の計算に自信がない場合は、先に順列と組合せの使い分けを確認しておくと、この記事の公式の意味がよく分かります。

最短経路を解く2つの方法

足し算法が成り立つのは、ある交差点に最短で着く道順は「左の交差点から右へ来る」か「下の交差点から上へ来る」のどちらかしかないからです（和の法則）。通れない道があれば、その道を通って来る数を足さないだけで済みます。

公式が成り立つ理由を小さな例で確かめる

右2・上2のゴールで、道順をすべて書き出してみます。右を「→」、上を「↑」と書くと、次の6通りです。

• →→↑↑　→↑→↑　→↑↑→
• ↑→→↑　↑→↑→　↑↑→→

どれも「→2つ・↑2つ」の並べ方になっています。4回の移動のうち→にする2回を選ぶので 4C2＝6通り。公式 (a+b)Ca の a＝2、b＝2 の場合とぴったり一致します。「同じものを含む順列」として 4!÷(2!×2!)＝6 と考えても同じです。

このように、道順＝矢印の並べ方と言い換えられることが、公式の正体です。公式を忘れたときは、小さな例で書き出して確かめられるようにしておくと安心です。

足し算法の手順

1. スタートに1を書く。スタートと同じ行・同じ列の交差点（一番下の行と一番左の列）は、まっすぐ進む1通りしかないので、すべて1。
2. 左下から右上へ、1つずつ埋める：各交差点に「左の交差点の数＋下の交差点の数」を書く。
3. 通れない道があれば、その道からは足さない：たとえば左からの道が通れないなら、下の数だけを書く。
4. ゴールの数が答え。公式が使える形なら、公式の答えと一致するかを確かめる。

例題1：障害物のない道順を数える

例題1 碁盤の目の道で、地点Aから右へ4区画、上へ3区画進んだところに地点Bがある。AからBまで最短で行く道順は何通りか。

1. 12通り　2. 35通り　3. 7通り　4. 5040通り

解き方 右4回・上3回の計7回の移動のうち、どの4回を右にするかを選ぶので、7C4＝7C3＝(7×6×5)÷(3×2×1)＝35通りです。

足し算法でもBは35になり、公式と一致します。正解は2です。1の12通りは 4×3 とかけただけの値、3の7通りは移動の回数そのもの、4の5040通りは 7! で、右どうし・上どうしの入れ替えまで別に数えてしまった値です。

例題2：通れない道がある場合

例題2 地点Aから右へ3区画、上へ3区画進んだところに地点Bがある。ただし、Aから右に1・上に1進んだ交差点Pと、Pの右隣の交差点Qを結ぶ道は工事中で通れない。AからBまで最短で行く道順は何通りか。

1. 20通り　2. 6通り　3. 26通り　4. 14通り

解き方 足し算法で数えます。Q（右2・上1）には、左のPから来る道が通れないので、下からの1だけを書きます。あとは通常どおり足していきます。

Bは14なので、正解は4です。1の20通りは工事を無視した 6C3、2の6通りは工事中の道を通る道順の数、3の26通りはその2つを足した値です。

検算：工事中の道を通る道順は「A→P」が 2C1＝2通り、「Q→B」が右1・上2で 3C1＝3通りなので 2×3＝6通り。全体20通りから引いて 20−6＝14通りと、足し算法の答えに一致します。

必ず通る点がある場合はどうする？

「途中で必ず地点Pを通る」場合は、道順を2つに分けてかけます。

• スタート→P と P→ゴール を、それぞれ公式か足し算法で数える。
• 2つの区間は続けて進むので、積の法則でかける。
• 「Pを通らない」道順は、全体からPを通る道順を引く。

練習 例題1の道（右4・上3）で、Aから右に2・上に1進んだ交差点Pを必ず通る道順は何通りか。

答え 18通り。A→Pは右2・上1で 3C1＝3通り、P→Bは右2・上2で 4C2＝6通り。3×6＝18通りです。Pを通らない道順は 35−18＝17通りになります。

「PもRも通る」のように通る点が2つあれば、区間を3つに分けてかけます。ただし、PからRへ最短で進めない位置関係（RがPの左や下にある）なら、両方を通る最短経路は0通りです。点の位置関係を先に確かめてから計算します。

つまずいた操作から確認する

1分で解くための時短のコツ

• 障害物がなければ公式一択：7C3 のような計算は10秒で終わります。表を書くのは障害物があるときだけにします。
• 通れない道は「全体−通る道順」でも解ける：通れない道が1本だけなら、例題2の検算のように引き算の方が速いこともあります。
• 表は必要な範囲だけ書く：ゴールに関係しない交差点（スタートより左や下など）は書かなくて構いません。

足し算法の表は、慣れると1マス2〜3秒で埋まります。4×3程度の道なら20マスで1分弱かかるので、障害物のない部分は公式、障害物の周りだけ足し算法、と使い分けるのが現実的です。

次に練習すること

組合せの公式そのものは順列と組合せの使い分け、足すかかけるかの判断は場合の数の基本で確認できます。道順を確率に使う問題（分かれ道で進む向きを等しい確率で選ぶなど）は、確率の基本と「少なくとも1回」の確率の考え方と組み合わせて練習してください。

2つの方法を覚えたら、登録不要の無料お試し10問で、本番と同じ1問1分のペースで解けるかを試してみてください。