【カーナビの仕組みが分かる！】経路探索生物「ダイクストラ」
《誕生》
また１匹、交差点に経路探索生物が産み落とされた。
生物の名は「ダイクストラ」。
英語の綴りは「Ｄｉｊｋｓｔｒａ」と書いたりする。勘で綴るのは、ほぼ無理だ。
さてこのダイクストラ、此度は「近くのコンビニを２つ見つけて」と頼まれた。「道順もよ」と、創造主は生物使いが荒い。
でもダイクストラは文句を言わない。少し品種改良をしてもらっているからだ。「ノーマルのままだと、物語を書くのが一手間増えるのよ」と創造主は言っているのだが、ダイクストラはそのことを知らない。
《１巡目》
早速、ダイクストラは、４つの子を産み出した。
始まりの交差点は十字路。４つの道がつながっているからだ。
そして最初のダイクストラは消滅した。
生まれたダイクストラたちは、各道を進む。
それぞれ進む。
そのお腹から、青い糸を吐き出しながら。
そして。
１匹目のダイクストラは１５進むと、新たな交差点に差し掛かり、その歩みを止めた。
２匹目は１０進んで、別の交差点に着いた。
３匹目の道は、とても曲がりくねっていた。進んでも進んでも、交差点に着かない。
６０進んで、ようやく着いた。
でも着いたら疲れは吹き飛んだ。
そこにはコンビニＡが、あったから。
４匹目は２０進んで、交差点に着いた。
こうして皆、互いに異なる交差点に着いた。
《２巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
離れていても、不思議な力で、比べることができる。
そして今回は２匹目の糸が、１０と、もっとも短かった。
故に。
確定した。
始まりの交差点から、２匹目のいる交差点にたどり着くには、２匹目の通ってきた道が最も近道であると、確定したのだ。
なぜって、ほかの３匹は始まりの交差点から１０より遠くに離れてる。どんな近道を通ったって、２匹目より短い糸で、この交差点にはたどり着けない。
こうして確定したので２匹めの出した青い糸が、赤色に変わる。
それは確定意味する、赤い色。
そして２匹目は、５匹目と６匹目を産み出して、消滅した。
２匹目のいた交差点は三叉路。つながる道は３つ。
でも、そのうち１つは、赤い糸がある。
だから３匹では無く、２匹を産んだ。
ノーマルだと、ここで３匹産む。
新たに生まれたダイクストラは、道を進む。ひたすら進む。
それぞれ、その腹部から青い糸を出しながら、
やがて。
５匹目のダイクストラは、２５進んで交差点に着いた。始まりの地からは３５になる。
６匹目も交差点に着いた。こちらは２０、始まりの地からは３０になる。
そして５匹目と６匹目は同じ交差点に着いた。
ダイクストラは１つの交差点に１匹しか生きられない。
始まりの地に近いダイクストラが生き残る。
だから生まれたばかりの５匹目は消滅した。５匹目の出した青い糸も消滅した。
《３巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
今度は１匹目の糸が、１５と、もっとも短かった。
また、確定した。
始まりの交差点から１匹めのいる交差点にたどり着くには、１匹目の通ってきた道が最も近道であると、確定したのだ。
１匹めの出した青い糸が、赤色に変わる。
そして１匹目は、７匹目と８匹目を産み出し、消滅した。
１匹目のいた交差点につながる道は３つ。そのうち１つは、赤い糸がある。
生まれたダイクストラは道を進む。青い糸を出しながら。
７匹目は、５５進んで交差点に着いた。始まりの地からは７０。そしてそこには、コンビニＢがあった。
８匹目も着いた。こちらは２５進んだ。始まりの地からは４０。
でもそこには４匹目がいた。４匹目は始まりの地から２０だった。
ダイクストラは１つの交差点に１匹しか生きられない。
始まりの地に近いダイクストラが生き残る。
だから８匹目は消滅した。出した青い糸も消滅した。
《４巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
コンビニ２つ見つかってるが、それでも長さを比べ始める。
もっと近い、道があるかも。
もっと近い、コンビニあるかも。
そして今度は４匹目の糸が、２０と、もっとも短かった。
確定。
４匹目の糸が、青から赤へ。４匹目は、９匹目と１０匹目を産んで、消滅した。
４匹目のいた交差点につながる道は３つ。そのうち１つは、赤い糸がある。
生まれたダイクストラは、青い糸を出しながら、道を進む。
９匹目の到着した交差点には誰もいないが、赤い糸が届いていた。なので９匹目は消滅した。その青い糸も消滅した。
１０匹目は３５進んで交差点についた。そこにはコンビニＡがあった。３匹目もいた。
１０匹目は始まりの地から５５。３匹目は始まりの地から６０。
だから３匹目は消滅した。その青い糸も消滅した。
こうしてコンビニＡには、更に近道があったことが分かった。
《５巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
そして今度は６匹目の糸が、始まりの交差点から３０と、もっとも短かった。
確定した。
始まりの交差点から６匹めのいる交差点にたどり着くには、「６匹目と、その親の２匹目の通ってきた道」が最も近道であると、確定したのだ。
だってほかの２匹の生き残りは、始まりの交差点から５５と７０。どんな隠れた近道があっても、６匹目より短い糸で、この交差点に来ることはない。
６匹目の出してきた青い糸が、赤色に変わる。
６匹目は、１１匹目と１２匹目と１３匹目を産み、消滅した。
６匹目は変形の交差点にいた。つながる道は４つ。だから赤い糸の道を除いて、３匹産んだ。
１１匹目は３０進んで、コンビニＢのある交差点に着いた。始まりの地からは６０。
７匹目がいたが、その糸は７０。７匹目は青い糸とともに消滅した。
コンビニＢの始まりの地からの長さも、７０から６０へと、短くなった。
だからコンビニ２つ見つかってても、ダイクストラは活動を続ける。
１２匹目は１０進んだだけで、コンビニＣのある交差点についた。始まりの地からは４０。
だからコンビニ２つ見つかってても、活動を続けてきたのである。それは３つ目を見つけても、同じこと。
１３匹目の到着した交差点には誰もおらず。でも赤い糸が、届いていた。
１３匹目は、青い糸と一緒に、消滅した。
《６巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
そして生まれたばかりの１２匹目の糸が、始まりの交差点から４０と、もっとも短かった。
確定した。
始まりの交差点から１２匹めのいる交差点にたどり着くには、「１２匹目と、その親の６匹目と、更にその親の２匹目の通ってきた道」が最も近道であると、確定した。
１２匹目の出してきた青い糸が、赤色に変わる。
そして故に。
コンビニＣの経路も確定した。この交差点にはコンビニＣがあった。これ以上の近道は存在しない。始まりの交差点から、４０であることが確定した。
最初に確定したので、もっとも近いコンビニであることも確定。ただ同じ距離の別のコンビニがあるかどうかまでは、まだ分からない。
１２匹目は、１４匹目と１５匹目を産み、消滅した。
１２匹目のいた交差点は三叉路。赤い糸のある道を除いて、２匹を産んだ。
１４匹目は１０進んで交差点に着いた。そこには誰もいなかった。赤い糸も届いていない。
１５匹目は５０進み、コンビニＡのある交差点についた。全部で９０。
そこには１０匹目もいた。その長さは５５。
だから１５匹目は消滅した。その青い糸も消滅した。
コンビニＡの距離は、今度は更新されず。でも今が最短かどうかは、まだ分からない。
《７巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
そして今度は１４匹目の糸が、始まりの交差点から５０と、もっとも短かった。
確定。
始まりの交差点から１４匹めのいる交差点にたどり着くには、「１４匹目と、その親の１２匹目と、更にその親の６匹目と、更に更にその親の２匹目の通ってきた道」が最も近道であると、確定した。
１４匹目の出してきた青い糸が、赤色に変わる。
１４匹目のいた交差点は三叉路。１６匹目と１７匹目を産んで、１４匹目は消滅した。
１６匹目は２５進んで交差点に着いた。誰もおらず、赤い糸もなかった。
１７匹目は１０進んで交差点に着いた。そこにはコンビニＤだけがあった。
コンビニＢとコンビニＤは、どちらも始まりの交差点から６０。もしこれらが６０のままで、創造主が「３つ見つけて」と言っていたら、３位が２つあることになる。創造主はこうした場合、「早いもの勝ちで良いわよ」とダイクストラに告げていた。
《８巡目》
ダイクストラは、皆が止まると、互いに糸の長さを比べ始める。
今回は１０匹目の糸が、始まりの交差点から５５と、もっとも短かった。
確定した。
始まりの交差点から１０匹目のいる交差点にたどり着くには、「１０匹目と、その親の４匹目の通ってきた道」が最も近道であると、確定したのだ。
そしてこの交差点にはコンビニＡがある。２つ目のコンビニの経路と距離が確定したのだ。同じ距離のコンビニが別にあるかもしれない。でも２番であることは確定した。創造主は早いもの勝ちで良いと言っていた。
《成就》
ダイクストラたちは創造主に、「コンビニ２つ見つけた」と報告した。
創造主は、コンビニＣとそれに繋がる赤い糸、コンビニＡとそれに繋がる赤い糸を取り出し、黙って去っていった。
ダイクストラたちは怒らない。創造主が利用者のために、これから別の作業をすると知っているから。
「道に迷わないと良いね」
「早く着けると良いね」
そうして全てのダイクストラは、消滅した。
おしまい
おまけ：各道路のコスト
ここまでお読みいただき、ありがとうございました。そしてお疲れさまでした。
なお単純に「Ａ地点からＢ地点の近道を探し出す」場合は、「Ａ地点を始まりの地にして、Ｂ地点に赤い糸が引かれれば、それが近道」になります。
「Ａ＊（エースター）アルゴリズム」は、このようにＢ地点の位置が明確な場合は、「ダイクストラ法」よりも効率良く近道を探し出せるように改良されています。しかし、本作のように位置が不明な目標への近道を探したい場合には、使用することができません。
