最短経路 わかりやすく

線ごとに距離が違う

点と点を線でつなぐ方法は、もう学びました。でも実際の道には、もう一つあります。線ごとに距離が違うということです。
短い道もあれば遠い道もあるので、線の上に数字を書きます。その数字が距離です。
下の道を押して、距離を確かめましょう。

道を押すと距離が見えます。（線 = 道 · 数字 = その道の距離）

距離が違うことが、なぜ大切なのでしょうか。分かれ道を少ししか通らない道でも、一区間ずつが遠ければ、全体ではもっと遅くなることがあります。
逆に、分かれ道を多く通っても、各区間が近ければ、全体ではもっと速くなることもあります。
だから距離を抜きにして道を選ぶことはできません。

近い順に数えるだけでは足りない

前に、近い順に広がる方法を見ました。一マス、二マス、三マスと、出発点から何マス離れているかで数える方法でした。
でもそれは、すべての道がちょうど一マスのときの話です。
道ごとに距離が違えば、マスの数が少ない道がもっと近いとは限りません。

二つの道を押して比べます。（マスが少ない道 vs 距離が短い道 · 同じではない）

分かれ道を少ししか通らない道のほうが、距離ではもっと遠かったのです。マスの数だけ数えると、このわなにはまります。
だからマスの数ではなく、距離を足しながら、本当に近い道を探さなければなりません。

近いものから確定する

では、どうすればよいでしょうか。目の前の最善を選ぶ貪欲を思い出しましょう。
出発点から始めて、まだ距離が確定していない点のうち、今いちばん近い点を一つ選び、その距離を確定します。
道の距離がマイナスでなければ、いちばん近い点までもっと短い道はありえないので、確定しても安心です。

いちばん近い点を押して確定します。（毎回、未確定の点のうち距離がいちばん短いものを選ぶ）

これが目の前の最善を選ぶということです。地図全体を解くのではなく、今いちばん近い点から一つずつ確定していきます。
一つの点を確定すると、その点を通っていく隣の点の距離も、新しく近くなることがあります。
この方法をダイクストラ法と呼びます。

境界を広げていく

確定した点が増えるほど、「距離が決まった範囲」ができ、その範囲のふちが境界です。
毎回、境界のすぐ外からいちばん近い点を一つ取り込めば、範囲が一点ずつ大きくなります。
静かな水に石を投げると、波紋が広がるのに似ています。

境界のすぐ外の点を押すと、範囲が大きくなります。（確定した範囲が一点ずつ外へ育つ）

境界がだんだん外へ広がっていくと、やがてすべての点が確定した範囲に入ります。
そのときには、出発点からどの点までも、いちばん速い距離がすべてわかります。近いところから一歩ずつ、それがこつです。

まとめ

いちばん速い道探しを一行にまとめるとこうです。線ごとに距離が違えば、マスの数が少ない道が速い道とは限らないので、近い順に数えるだけでは足りません。
近い点から距離を確定し、境界を一点ずつ広げていけば、その時その時で目の前の最善を選びながら、すべての点までの最短距離が見つかります。

要点を順に押してまとめます。（距離が違う → マスの数ではだめ → 近いものから確定 → 境界を広げる）

地図アプリがいちばん速い道を探してくれるとき、中ではこんなことが起きています。近いところから距離を確定し、境界を少しずつ広げていくのです。
目の前の最善という単純な決まりが、距離がばらばらな複雑な道でも、いちばん速い答えを連れてきます。