朝の通勤、休日のお出かけ、初めて行く場所。
何かしらどこかに向かうとき、皆さまは行き慣れたところ以外は無意識に地図を開いて、地図の最短経路通りに目的に向かっているかと思います。

しかしここで私平山は思いました。

「なぜ地図アプリは一瞬で「最短ルート」を出せるのか？」

そこで今回は、地図アプリが最短ルートをだす仕組みについてご説明いたします！

📍 地図 = グラフ

地図アプリは道路網を「グラフ」という構造で表現してます。
グラフは以下の3つの要素があります。

• ノード（点）: 交差点
• エッジ（線）: 道路
• 重み: 距離や所要時間

こんなイメージです👇

一方通行とかもあるので、方向も考慮した「有向グラフ」として扱います。

🔍 使用される2つの代表的なアルゴリズム

ダイクストラ法

考え方: 全方向を均等に探索

メリット✅：確実に最短ルートを見つける
デメリット❌： ちょっと遅い（無駄な探索も多い）

1956年にエドガー・ダイクストラさんが考えた古典的なアルゴリズムです。

どう動くの？
実際に例として、⑦のノードからスタートし、⑫のノードをゴールとして最短経路を出してみます。

1.「今行ける中で一番近い場所」に移動
今回だと、⑦を起点として移動できるノードは③、⑥、⑧、⑪に移動できますが、その中で一番重みが小さいのは⑥になるので、⑥に移動します

2.そこからまた「行ける中で一番近い場所」へ
次に移動できる⑤、⑨、⑩ともに重みは同じなので、今回は⑩のノードに移動します。

3.ゴールに着くまで繰り返し
1と2の手順を繰り返し、すべての道を調べ確実に最短経路を割り出します。

前述にもあった通り、このアルゴリズムは確実に最短経路を割り出すことはできますが、すべての道を調べ上げるので、処理が遅いのがネックです。

A*アルゴリズム（エースターアルゴリズム）

考え方: ゴール方向を優先的に探索

✅ めっちゃ速い
✅ 実際の地図アプリで使われてる
✅ ちゃんと最短ルートを見つける

💡 A*の賢いポイント

「目的地が東にあるのに、なんで西を探索してるの？」と無駄を省いたアルゴリズムで、目的地までの直線距離を考慮して、「こっちの方が近そう」と方向を優先的に探索します。

こんなイメージです👇

1.進む方向を決める
ゴールである⑫は東の方向になるので、北、北西、西、南東、南方向の道は進まないと判断し、そこから一番重み（距離）が小さいノードに向かいます。

2.ゴールに着くまで繰り返し
ゴールは北東の方にあるので、南向きの⑩は選択肢から外しそのままゴールの⑫に向かいます。

このようにダイクストラ法と比べ、無駄な道を検索せずに最短でゴールまでの経路を割り出せるのがA*アルゴリズムの特徴になります。

実際にはアルゴリズムに加え、事前計算やキャッシュなどの工夫もあります。

📊 結局どっちを使えばいいの？

ダイクストラ法

• いいところ: シンプルで理解しやすい、確実に最短を見つける
• イマイチなところ: 全方向を探索するから遅い
• 使う場面: アルゴリズムの勉強、小規模なグラフ、座標情報がない場合

A*アルゴリズム

• いいところ: ダイクストラより圧倒的に速い、ちゃんと最短を見つける
• イマイチなところ: 実装がちょっと複雑、座標が必要
• 使う場面: 地図アプリ、ゲームのキャラクター移動、実用的なナビゲーション

結論: 地図みたいに「東西南北の位置」が分かる場合は、A*アルゴリズムを使えばOK！実際のGoogle MapsとかもA*をベースにしたアルゴリズムが多く使われています。

⚡ 実際のアプリはもっと賢い

基本アルゴリズムだけだと遅いので、実際の地図アプリはいろんな工夫をしてます。

🪜 階層化 - 遠くに行くなら高速を使う

東京から大阪に行くとき、最初から全部の路地を探索してたら日が暮れます。

遠くに行くときは高速道路メインで探索して、出発地と目的地の近くだけ細かく探索します。

🚦 リアルタイム渋滞情報

道路の渋滞情報をリアルタイムで取得し「重み」を動的に変更します。

通常時：　渋谷ー[10分]→新宿
渋滞中：　渋谷ー[20分]→新宿 ←重みが2倍に！

「この道、今めっちゃ混んでるから避けよう」って判断してくれるわけです。

⚙️ その他の工夫

• 有料道路回避: 「高速使わない」設定 → 高速道路のエッジを除外
• 最短時間 vs 最短距離: 重みを時間にするか距離にするか
• 車両制限: トラックの高さ・重量制限も考慮
• 時間帯規制: 「この時間は通行止め」も反映

📝 まとめ

1. 道路網をグラフで表現（交差点=ノード、道路=エッジ）
2. A*アルゴリズムで探索（目的地方向を優先）
3. いろんな工夫で高速化（階層化、リアルタイム情報、キャッシング）

普段何気なく使っている地図アプリの最短ルート検索の仕組みは、意外とシンプルな原理で動いています。