いちばん早い道順を探す方法 | 子ども向けオンラインプログラミングスクールのみらいごとラボ

こんにちは！もりたか先生です。

皆さんはお出かけをするとき、お店への行き方をどうやって調べていますか？最近はカーナビや便利な地図アプリがあるので、初めて行くお店でも簡単に道順を調べることができますね。

ところで、カーナビや地図アプリはどうやって目的地への道順を考えているのでしょうか？目的地へ行く道順は1通りではなく、色々な行き方があります。たくさんの道の中から、一番早く到着できる道順を探すのはとても大変そうですね。

実はある方法を使えば、一番早い道順を簡単に見つけることができるんです！今回はその方法を紹介します。

その前に、まずは皆さんに一番早い道順を見つけるクイズを解いてもらおうと思います。

【クイズ】

家から学校に行く道順のうち、一番早く学校に着く道順を見つけましょう！

黒い線の近くに書いてある数字は、その道を通るのにかかる時間を表しています。
例えば、家からバス停を通って学校に行く道順は５＋３＝８分 の時間がかかります。
8分よりも短い時間で学校に行ける道順はあるでしょうか？

皆さんはどんな方法で解いてみましたか？
ここからは簡単に最短経路(一番早い道順)を見つける方法でクイズの問題を解いていきます。皆さんの答えが最短経路になっているか、確かめてみましょう！

【解き方】

ステップ1

まずはスタート地点の家からまっすぐ一本道で行ける場所を探してみましょう。家から一本道で行けるのはポスト・公園・バス停の３箇所ですね。

家からこの３箇所に行くのにかかる時間をそれぞれ書きこんでみましょう。すると、下の絵のようになります。

これで家から一本道で行ける場所は探し終わったので、スタート地点に色を塗るなどして、印をつけておきましょう。今回は青く塗っていきます。

ステップ2

今度はステップ１で見つけた黒点の中で、一番小さい数字が書かれている場所に注目してみましょう。今回は１と書かれたポストが一番小さいですね。

ではポストからまっすぐ一本道で行ける場所のうち、まだ青く塗られていない場所を探しましょう。この場合は公園ですね。ステップ１で、家から公園までは４分かかると計算しました。しかし、ポストから公園までは２分で行けるので、家→ポスト→公園の道順だと１＋２＝３分で公園に行けますね。４分より短い時間で公園に行ける道順が見つかったので、公園の数字を３に書き変えましょう。

ポストから一本道で行ける場所も探し終わったので、ポストの点も青く塗ります。

ステップ3

残った黒点の中で、一番小さい数字が書かれた点に注目しましょう。公園が３、バス停が５なので、一番小さいのは公園の点ですね。

ステップ１・２と同じようにして、公園からまっすぐ一本道で行けて、まだ青く塗られていない場所を探しましょう。この場合はコンビニと学校です。

この２箇所にはまだ数字が書かれていませんね。ではこの２箇所の点に、(公園の点の数字)＋(公園とコンビニまたは学校をつなぐ道の数字)を計算して書きこんでみましょう。つまり、

コンビニの場合：３＋３＝６分

学校の場合：３＋６＝９分となります。これは、(家から公園に行くのにかかる時間)＋(公園からコンビニまたは学校に行くのにかかる時間)になっていますね。

計算が終わったら、公園の点も青く塗ります。

ステップ4

次に注目する黒点はどれでしょうか？一番小さい数字が書かれているのはバス停の点ですね。

バス停から一本道で行けて、まだ青く塗られていないのはコンビニと学校です。コンビニと学校に書かれている数字はこのままでいいでしょうか？

コンビニの場合：バス停からコンビニへ行くには２分かかるので、家→バス停→コンビニの道順の場合、５＋２＝７分になります。今コンビニの数字は６分なので、数字を変える必要はないですね。

学校の場合：バス停から学校へ行くには３分かかるので、家→バス停→学校の道順の場合、５＋３＝８分になります。今学校の数字は９分なので、バス停を通る道順の方が早く学校に着きますね。なので、学校の点を９分から８分に書き変えましょう。

書き変えたらバス停の点を青く塗りましょう。

ステップ5

いよいよ最後のステップです。残った黒点は２個。数字が小さいのはコンビニの点ですね。

では今までのステップを参考に、学校の点の数字を考えてみましょう。

下の絵のようになったでしょうか？

【完成！】

最終的に学校の点に書かれている数字が、一番早い道順を通るのに必要な時間を表しています。つまり、クイズの答えは７分です！皆さんの答えはあっていたでしょうか？

【まとめ】

いかがだったでしょうか？簡単といっていたのに、意外と面倒くさいことをしている…と思った人もいるかもしれません。そんな人はぜひチャレンジ問題にも挑戦してみてください！地図が複雑になるほど、この方法がとても便利だということに気付くと思います！
今回紹介した方法はダイクストラ法と呼ばれています。1959年にエドガー・ダイクストラさんによって考案された方法です。こんなにも昔に考えられた方法が、カーナビなどのハイテクな技術のもとになっているのはすごいことですね！