クルマのドライバーにとって、カーナビゲーションシステム（カーナビ）は欠かせない製品だ。とりわけ見知らぬ土地へのドライブでは、重宝している人も多いだろう。最近は、クルマに備え付けるビルトインタイプだけでなく、「Yahoo！カーナビ」や「Googleマップ」などのスマホアプリも普及している。手軽に使えるので、ドライブでこれらのスマホアプリを活用する人もいるはずだ。
ところがカーナビの中には、車幅ギリギリの道を提示したり、渋滞でクルマが全く進まない道を掲示したりすることがある。到着予定時刻がどんどん遅くなり、イライラすることもあるだろう。なぜカーナビは、このような経路を選択してしまうのか。理由は、アルゴリズムを理解すると、おのずと見えてくる。
ベースは半世紀以上前のアルゴリズム
カーナビのように出発地点から目的地点までの経路を調べるソフトウエアの多くは「経路探索アルゴリズム」で実装されている。その理論はとても単純だ。下図を例に説明する。
出発地点（S）から目的地点（G）までの最短経路を求める例だ。道路情報は「グラフ」として表すことができる。交差点をノード（節）と見立てて、ノード間をつなぐ道路を枝と見なす。ノード間を結ぶ枝には、移動するのに必要な時間を割り当てる。枝に割り当てる時間は「コスト」や「重み」といった単語で表現することもある。
このように交差点と道路をノードと枝に見立てて、出発地点から1分後にたどり着くノード、2分後にたどり着くノード、というように探索していく。目的地点にたどり着いたら探索は終了だ。
時間が短い順に、目的地点から出発地点へと経路を逆にたどっていくのが特徴だ。例では、目的地点に一番早く到着した枝がつながっていたのは「ノードF」だ。そこで、目的地点とノードFを結ぶ。ノードFに一番早く到着したのは「ノードE」からの枝なのでノードFとノードEを結ぶ。同様にしてノードEと「ノードA」を結び、ノードAと出発地点を結んで探索を終了する。これで、出発地点から目的地点まで一番早く到着する経路を探索できるわけだ。
このアルゴリズムはスタートノードから他の全てのノードへの最短経路を求める有名な手法で「ダイクストラ（Dijkstra）法」と呼ばれている。このアルゴリズムが考案されたのは1959年だ。実際の探索では、ダイクストラ法の改良版などが使われているが、半世紀以上前のアルゴリズムがカーナビの経路探索のベースになっている。
