中学生でも解ける東大大学院入試問題（１９９）

こんにちは。東久留米市の学習塾塾長です。

天気予報では、しばらく３０℃前半の気温が続くようで、先週までの猛暑に比べて少し過ごしやすくなりそうです。夏休みも半分終わりました。宿題など早めに片付けるとよいでしょう。

さて、今回は平成２７年度東大大学院工学系研究科システム創成学の入試問題です。

問題は、
「下図に示す有向グラフにおいて、頂点Ａから各頂点までの最短経路の距離と、最短経路における直前の頂点を求め、下表に埋めよ。ただし、辺の傍の数字は距離を示す。」

▲問題図

▲解答の表

です。

アルファベット順に調べていきましょう。

まず頂点Ｃです。頂点Ｃに到達する直前の頂点は、ＡまたはＥです。

頂点Ａの場合、最短経路は、Ａ→Ｃ（１３）です。（経路の後の（ ）の数はその経路の距離を表します）

頂点Ｅの場合、頂点Ｅに到達する直前の頂点はＢで、頂点Ｂを経由する最短経路と頂点Ｅまでの最短経路はＡ→Ｂ→Ｅとなります。つまり、頂点ＡからＥを経由するＣまでの最短経路は、Ａ→Ｂ→Ｅ→Ｃ（１２）です。

以上から、頂点ＡからＣまでの最短経路は、Ａ→Ｂ→Ｅ→Ｃで、そのとき頂点Ａからの距離は１２、直前の頂点はＥになります。

これで、図１のように、頂点（Ａ）、（Ｂ）、Ｃ、Ｅの最短経路が判りました。

▲図１．頂点（Ａ）、（Ｂ）、Ｃ、Ｅの最短経路

次に頂点Ｄです。頂点Ｄに到達する直前の頂点は、Ａ、ＣまたはＦです。

頂点Ａの場合、最短経路はＡ→Ｄ（１５）です。

頂点Ｃの場合、最短経路は、Ａ→Ｂ→Ｅ→Ｃ→Ｄ（１４）です。

頂点Ｆに到達する直前の頂点は、Ｃ、ＥまたはＧで、それらの頂点を経由する最短経路と頂点Ａからの距離は、それぞれＡ→Ｂ→Ｅ→Ｃ→Ｆ（１８）、Ａ→Ｂ→Ｅ→Ｆ（１０）、Ａ→Ｂ→Ｅ→Ｇ→Ｆ（３４）となり、頂点Ｅを経由する経路が最短経路になります。つまり、頂点ＡからＦを経由するＤまでの最短経路はＡ→Ｂ→Ｅ→Ｆ→Ｄ（１８）です。

以上から、頂点ＡからＤまでの最短経路は、Ａ→Ｂ→Ｅ→Ｃ→Ｄで、そのとき頂点Ａからの距離は１４、直前の頂点はＣになります。

これで、図２に示すように、頂点（Ａ）、（Ｂ）、Ｃ、Ｄ、Ｅ、Ｆの最短経路が判りました。

▲図２．頂点（Ａ）、（Ｂ）、Ｃ、Ｄ、Ｅ、Ｆ

続いて頂点Ｇです。頂点Ｇに到達する直前の頂点はＥだけなので、最短経路は、Ａ→Ｂ→Ｅ→Ｇで、そのとき頂点Ａからの距離は１８、直前の頂点はＥになります。

これで、図３に示すように、頂点（Ａ）、（Ｂ）、Ｃ、Ｄ、Ｅ、Ｆ、Ｇの最短経路が判りました。

▲図３．頂点（Ａ）、（Ｂ）、Ｃ、Ｄ、Ｅ、Ｆ、Ｇの最短経路

続いて頂点Ｈです。頂点Ｈに到達する直前の頂点は、Ｄ、Ｆ、ＧまたはＩです。

頂点Ｄの場合、最短経路は、Ａ→Ｂ→Ｅ→Ｃ→Ｄ→Ｈ（２６）です。

頂点Ｆの場合、最短経路は、Ａ→Ｂ→Ｅ→Ｆ→Ｈ（２７）です。

頂点Ｇの場合、最短経路は、Ａ→Ｂ→Ｅ→Ｇ→Ｈ（２５）です。

頂点Ｉに到達する直前の頂点は、Ｂ、ＥまたはＧで、それらの頂点を経由する最短経路と頂点Ａからの距離は、それぞれＡ→Ｂ→Ｉ（１０４）、Ａ→Ｂ→Ｅ→Ｉ（２３）、Ａ→Ｂ→Ｅ→Ｇ→Ｉ（２８）となり、頂点Ｅを経由する経路が最短経路になります。つまり、頂点ＡからＩを経由するＨまでの最短経路はＡ→Ｂ→Ｅ→Ｉ→Ｈ（３２）です。

以上から、頂点ＡからＨまでの最短経路は、Ａ→Ｂ→Ｅ→Ｇ→Ｈで、そのとき頂点Ａからの距離は２５、直前の頂点はＧになります。

これで、図４に示すように、頂点Ａから各頂点までの最短経路と距離が判りました。

▲図４．頂点Ａから各頂点までの最短経路

これをまとめると、
頂点Ｂ：Ａ→Ｂ（５）
頂点Ｃ：Ａ→Ｂ→Ｅ→Ｃ（１２）
頂点Ｄ：Ａ→Ｂ→Ｅ→Ｃ→Ｄ（１４）
頂点Ｅ：Ａ→Ｂ→Ｅ（９）
頂点Ｆ：Ａ→Ｂ→Ｅ→Ｆ（１０）
頂点Ｇ：Ａ→Ｂ→Ｅ→Ｇ（１８）
頂点Ｈ：Ａ→Ｂ→Ｅ→Ｇ→Ｈ（２５）
頂点Ｉ：Ａ→Ｂ→Ｅ→Ｉ（２３）
となり、解答の表を埋めたものを表１に示します。

▲表１．解答の表を埋めました

頂点Ａからの最短経路が決まった頂点を利用して、逐次、最短経路を決めていく方法が簡単です。