ダイクストラ法 — いちばん安い道から確定する

カーナビは「いちばん近い道」をどう見つけているのでしょう。やみくもに全部の道を試すのではなく、今わかっている中でいちばん安く着けそうな地点から順に調べていきます。これがダイクストラ法の考え方です。各地点まで「最小いくらで来られるか」を更新しながら、コストの小さい所から扇状に探索を広げます。

ポイントは距離(コスト)に差があっても正しく最短を出せること。下の図1には、通れない壁と、通れるけど時間のかかる砂地(コスト3)があります。1ステップや自動再生で探索の広がりを観察し、ゴールに着いたら引かれる最短経路を見てください。マス目をクリックすると壁を足したり消したりできます。

なぜ「いちばん安い候補から」なのか

ダイクストラ法は、確定したマスのコストは二度とくつがえらないという保証のうえに成り立っています。今ある候補の中で最小コストのマスを選んで確定すれば、それより安く後から到達する経路は存在しません(コストがマイナスにならない限り)。だから確定したマスから隣へコストを伝え、また最小の候補を選ぶ —— これを繰り返すだけで、ゴールに着いたときにはそこまでの最短コストが確定しているのです。

図1で砂地(コスト3)を無理に突っ切るより回り道した方が安いとき、探索はちゃんと回り道側を選びます。ちなみに「ゴールの方向へ優先的に探す」ヒントを足して無駄な探索を減らしたものが A*(エースター)です。考え方の土台はダイクストラと同じで、当てずっぽうの一歩を足すだけ。壁を描き替えて、探索の広がり方と最短経路がどう変わるか試してみてください。

まとめ

ダイクストラ法は「今わかっている中でいちばん安い所から確定していく」だけの、素直で強いアルゴリズムです。コストに差があっても最短を取りこぼさず、カーナビ・ネットワーク経路・ゲームのAIまで広く使われています。図1で、探索がコストの低い方へ優先して広がり、砂地を避けて最短経路が引かれる様子を、ステップを進めながら味わってみてください。