経路探索（Google Maps）── Dijkstra から Contraction Hierarchies へ
扱うCS概念：Dijkstra 法、A* アルゴリズム、Contraction Hierarchies（CH）、ヒューリスティック、優先度付きキュー
この章で何ができるようになるか：なぜ Google Maps が「10億ノードの道路グラフ」で数百ミリ秒以内に最短経路を返せるのかを説明できるようになる。Dijkstra の限界と、それを超えるための前処理アルゴリズムの考え方を理解できる。
問題設定
「東京から大阪まで最短・最速ルートを求める」をシステム設計として考える。
規模感（日本の道路網）：
ノード数：約1500万（交差点・地点）
エッジ数：約3500万（道路セグメント）
規模感（Google Maps の世界全体）：
ノード数：数十億
エッジ数：数百億
要件：
- レスポンスタイム：500ms 以内
- 複数の経路候補（最速・最短・経由地あり）
- リアルタイム交通情報を反映
- 徒歩・自転車・公共交通機関にも対応「数十億ノードのグラフで500ms以内」──素朴なアルゴリズムではとても間に合わない。
ステップ1：Dijkstra 法の基本
Dijkstra はグラフの最短経路問題の古典的な解法（1959年）だ。
import heapq
from typing import NamedTuple
class Edge(NamedTuple):
to: int
weight: float # 距離 or 時間
def dijkstra(graph: dict[int, list[Edge]], start: int, goal: int
) -> tuple[float, list[int]]:
"""
graph: {ノードID: [(隣接ノードID, 重み), ...]}
returns: (最短コスト, 経路)
"""
# 優先度付きキュー：(コスト, ノード)
heap = [(0.0, start)]
# 各ノードへの最小コスト
dist = {start: 0.0}
# 経路復元用：{ノード: 前のノード}
prev = {start: None}
while heap:
cost, node = heapq.heappop(heap)
if node == goal:
# 経路を復元
path = []
while node is not None:
path.append(node)
node = prev[node]
return cost, list(reversed(path))
# 既により良いパスが見つかっていれば無視
if cost > dist.get(node, float('inf')):
continue
for edge in graph.get(node, []):
new_cost = cost + edge.weight
if new_cost < dist.get(edge.to, float('inf')):
dist[edge.to] = new_cost
prev[edge.to] = node
heapq.heappush(heap, (new_cost, edge.to))
return float('inf'), [] # ゴールに到達不能計算量：O((V + E) log V)（V=ノード数、E=エッジ数、優先度付きキューを使った場合）
日本の道路網（1500万ノード）に適用すると：
O(1500万 × log(1500万)) ≈ O(1500万 × 23) ≈ 3.5億 操作
→ 現代のCPUで数秒かかる → 要件の500msを満たせないステップ2：A*（エースター）──ヒューリスティックで探索を絞る
Dijkstra は「全方向」に探索する。東京から大阪を探すとき、北海道方向に探索するのは無駄だ。
A* はゴールの方向に向かって優先的に探索する。
def heuristic(node_pos: tuple[float, float], goal_pos: tuple[float, float]) -> float:
"""
ユークリッド距離（or ハーバーサイン距離）で「残り距離の楽観的推定」を返す。
「どんなに速くても、この距離以上かかる」という下限値（Admissible）。
"""
lat1, lng1 = node_pos
lat2, lng2 = goal_pos
return haversine(lat1, lng1, lat2, lng2) # 直線距離（実際の道路距離より必ず短い）
def astar(graph, node_positions, start, goal):
"""
f(n) = g(n) + h(n)
g(n): スタートからnまでの実際のコスト
h(n): nからゴールまでのヒューリスティック（楽観的推定）
"""
heap = [(heuristic(node_positions[start], node_positions[goal]), 0.0, start)]
g_cost = {start: 0.0}
prev = {start: None}
while heap:
f, g, node = heapq.heappop(heap)
if node == goal:
path = []
while node is not None:
path.append(node)
node = prev[node]
return g, list(reversed(path))
if g > g_cost.get(node, float('inf')):
continue
for edge in graph.get(node, []):
new_g = g + edge.weight
if new_g < g_cost.get(edge.to, float('inf')):
g_cost[edge.to] = new_g
prev[edge.to] = node
h = heuristic(node_positions[edge.to], node_positions[goal])
heapq.heappush(heap, (new_g + h, new_g, edge.to))
return float('inf'), []graph LR
subgraph Dijkstra（全方向探索）
Start1[東京] -->|等距離に全方向| Circle[同心円状に広がる]
end
subgraph A*（ゴール方向に絞る）
Start2[東京] -->|大阪方向を優先| Goal[大阪]
endA* は大きな改善だが、それでも大規模なグラフでは不十分だ。道路グラフの場合、ヒューリスティック（直線距離）と実際の経路コストのギャップが大きく、多くの不要なノードを探索してしまう。
ステップ3：Contraction Hierarchies（CH）── Google Maps の核心技術
CH は2008年に発表された、道路グラフに特化した前処理アルゴリズムだ。事前処理を行うことで、クエリ時の探索ノード数を劇的に削減する。
直感的な説明
「東京から大阪まで行く」とき、実際の思考プロセスは：
1. 東京の近所の小道を通り、国道に出る（ローカルな道）
2. 東名高速→名神高速で一気に移動（高速道路 = 重要ノード）
3. 大阪の高速出口から目的地まで小道を通る（ローカルな道）CH はこの「階層構造」を事前に構築する。
CH の前処理：ノードの縮約（Contraction）
「重要でないノード」を順番に取り除き、それを通る最短経路をショートカットエッジで置き換える。
前処理前：
A --2--> B --3--> C --1--> D
（B と C は小さな交差点 = 重要度が低い）
B を縮約：
A --5--> C --1--> D （A→C のショートカット: 2+3=5）
C を縮約：
A --6--> D （A→D のショートカット: 5+1=6）
結果：
階層グラフには重要なノード（A, D）と
「A→D の最短距離=6」というショートカットが残るdef contract_node(graph, node_id):
"""
node_id を縮約する：
node_id を通る全てのパス u→node→v について
u→v のショートカット（もし既存のより短ければ）を追加する
"""
neighbors_in = [u for u, edges in graph.items() if node_id in [e.to for e in edges]]
neighbors_out = [e.to for e in graph.get(node_id, [])]
shortcuts_added = []
for u in neighbors_in:
for v in neighbors_out:
if u == v:
continue
# u → node → v のコスト
via_cost = get_edge_cost(graph, u, node_id) + get_edge_cost(graph, node_id, v)
# u から node を使わない最短距離
direct_cost = witness_search(graph, u, v, exclude=node_id)
if via_cost < direct_cost:
# ショートカットが必要（node を使わないと遠回りになる）
add_shortcut(graph, u, v, via_cost)
shortcuts_added.append((u, v, via_cost))
remove_node(graph, node_id)
return shortcuts_addedCH のクエリ：双方向Dijkstra on 階層グラフ
前処理後のクエリは非常に高速だ。
def ch_query(ch_graph, node_rank, start, goal):
"""
CH クエリ：スタートからは「上位ノードのみ」に向かい、
ゴールからも「上位ノードのみ」に向かって探索する。
交差した最小コストが最短経路。
"""
# 前向き探索：rank が高くなる方向のみ進む
forward = dijkstra_upward(ch_graph, node_rank, start)
# 後ろ向き探索：rank が高くなる方向のみ進む（ゴールから逆向き）
backward = dijkstra_upward(ch_graph, node_rank, goal, reverse=True)
# 両探索が共有するノードでの最小コスト
best = float('inf')
meeting_node = None
for node in set(forward.keys()) & set(backward.keys()):
cost = forward[node] + backward[node]
if cost < best:
best = cost
meeting_node = node
return best, unpack_path(ch_graph, start, goal, meeting_node)なぜ「上位ノードのみ」に進むのか：
ランクが高い = 多くの経路で使われる重要なノード（高速道路の主要IC、幹線道路の交差点）。スタートから上へ上へと登り、ゴールからも上へ上へと登ると、必ず重要なノード（高速道路の中継地点）でぶつかる。
graph BT
subgraph CH 階層
L1[ローカル道路<br/>rank 低]
L2[国道<br/>rank 中]
L3[高速道路<br/>rank 高]
end
Start[東京・出発地] -->|上向き探索| L1
L1 -->|上向き| L2
L2 -->|上向き| L3
Goal[大阪・目的地] -->|上向き探索| L1b[ローカル]
L1b -->|上向き| L2b[国道]
L2b -->|上向き| L3
L3 -->|交差！| Optimal[最短経路確定]CH の性能：
Dijkstra の探索ノード数：数百万
A* の探索ノード数：数十万
CH の探索ノード数：数千（！）
→ クエリ時間：数ms 以内（Dijkstra の1000倍以上高速）リアルタイム交通情報の組み込み
CH は事前処理が必要なため、道路の重みが変わる（渋滞・事故）と前処理のやり直しが発生する。
解決策：CH + オーバーレイ（customizable CH）
前処理（不変部分）：道路ネットワークのトポロジー（どこがどこにつながるか）
リアルタイム更新（可変部分）：各エッジの現在の重み（交通量・速度）
→ トポロジーは変わらないので、縮約順序の前処理は再利用
→ 重みだけ更新する "customization" フェーズ（数秒で完了）多目的経路探索（最速 vs 最短 vs 最エコ）
Google Maps は「最速」「最短」「燃費優先」などの複数条件に対応している。これは多目的最適化問題だ。
class Edge:
to: int
distance_km: float # 距離
time_minutes: float # 時間
fuel_liters: float # 燃料消費
def pareto_shortest_paths(graph, start, goal):
"""
パレート最適な経路集合を返す：
「他のどの経路より全ての指標で良い経路」のみを候補とする
"""
# 各ノードへの (距離, 時間) のパレートフロンティア
pareto_fronts: dict[int, list[tuple]] = {start: [(0, 0)]}
heap = [(0, 0, start)] # (距離, 時間, ノード)
while heap:
d, t, node = heapq.heappop(heap)
for edge in graph.get(node, []):
new_d = d + edge.distance_km
new_t = t + edge.time_minutes
# 既存のパレートフロンティアに支配されなければ追加
if not is_dominated((new_d, new_t), pareto_fronts.get(edge.to, [])):
pareto_fronts.setdefault(edge.to, []).append((new_d, new_t))
heapq.heappush(heap, (new_d, new_t, edge.to))
return pareto_fronts.get(goal, [])
def is_dominated(candidate, frontier):
return any(f[0] <= candidate[0] and f[1] <= candidate[1] for f in frontier)まとめ
| アルゴリズム | 前処理 | クエリ速度 | 向いているケース |
|---|---|---|---|
| Dijkstra | 不要 | 遅い（全探索） | 小規模グラフ・動的グラフ |
| A* | 不要 | 中程度 | 中規模・ヒューリスティックが良い場合 |
| CH | 必要（時間かかる） | 非常に速い | 大規模・静的グラフ（道路網） |
| ALT（A* with Landmarks） | 必要（軽量） | 速い | CH より柔軟性が必要な場合 |
設計の本質的なトレードオフ：
「前処理コスト」と「クエリコスト」の交換
CH は前処理に数時間かけることで、クエリを数ms にする。
道路ネットワークは「変化が少ない（トポロジーが安定）」ため、
この交換が非常に有利に働く。
SNS のグラフ（友人関係が毎秒変わる）には CH は向かない。
「前処理コストに見合うだけ、グラフが安定しているか」を判断することが設計の鍵。