最短経路探索（ダイクストラ法とA*アルゴリズム）

Q: 最短経路探索（ダイクストラ法とA*アルゴリズム）とは何ですか？

重み付きグラフ G = (V, E) において、始点 s から終点 t までの経路のうち、辺の重みの総和 \sum e_{ij} が最小となるパスを求める問題。エドガー・ダイクストラが考案した「ダイクストラ法」は、確定した最短距離のノードから貪欲法（Greedy）で探索を広げるアルゴリズムである。A*（エイスター）探索は、ゴールまでの推定残り距離（ヒューリスティック関数 h(n)）を加味することで探索を劇的に高速化する。

Q: 最短経路探索（ダイクストラ法とA*アルゴリズム）は社会やプログラミングでどのように使われていますか？

ゲームキャラクターの自動追従・ナビゲーションAI: 2Dグリッド上で障害物を避けながらターゲットへ向かう幅優先探索（BFS）/ ダイクストラ法のTypeScript実装。

グラフ上の無数のルートから「最もコストが小さい道」を一瞬で見つけ出す数学

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 最短経路探索（ダイクストラ法とA*アルゴリズム）の本質的な定義と直感的ビジュアルをシミュレーターで体験できる。
2: 公式や証明の背景にある数学的意味と、厳密な導出ステップを解説。
3: 実社会における工学応用（ゲームキャラクターの自動追従・ナビゲーションAI）のTypeScript実装コードを収録。

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

最短経路探索（ダイクストラ法とA*アルゴリズム）の基礎原理を体系化し、抽象的な計算を直感的に扱うために誕生した。

身につく武器・思考力

グラフ上の無数のルートから「最もコストが小さい道」を一瞬で見つけ出す数学。この考え方を身につけることで、複雑な課題を単純化して数理モデルとして解く力が養われる。

実社会・ITでの活躍現場

•ゲームキャラクターの自動追従・ナビゲーションAI
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

マス目をクリックして壁（障害物）を設置し、「最短経路を探索」ボタンを押してみよう。スタート（緑）からゴール（赤）に向かって探索波が広がり、障害物を迂回した最短ルート（黄色のライン）が瞬時に求まる。「リセット」で何度でも違う迷路を試せる。

※マスをクリックして壁を追加・削除

探索したノード数

0 マス

最短ステップ数

未探索 / 経路なし

探索状態

待機中

↑ 緑（Start）から赤（Goal）に向かって、水色のマス（探索済みの波）が広がり、壁を巧みに迂回して黄色の最短ルートを特定します。カーナビやGoogleマップ、ゲームキャラクターの移動AIはこのアルゴリズムで動いています。

Layer 2 — 定義・受験・証明

定義

重み付きグラフ $G = (V, E)$ において、始点 $s$ から終点 $t$ までの経路のうち、辺の重みの総和 $\sum e_{ij}$ が最小となるパスを求める問題。エドガー・ダイクストラが考案した「ダイクストラ法」は、確定した最短距離のノードから貪欲法（Greedy）で探索を広げるアルゴリズムである。A*（エイスター）探索は、ゴールまでの推定残り距離（ヒューリスティック関数 $h(n)$ ）を加味することで探索を劇的に高速化する。

公式・数理モデル

f(n) = g(n) + h(n) \quad (g: \text{実績コスト}, \; h: \text{推定コスト})

証明・導出

ダイクストラの最適性の証明（背理法）：始点から距離が最小の未確定ノード $u$ を確定ノード群に追加する際、もし $u$ へのより短い経路が別の未確定ノードを経由して存在すると仮定する。すべての辺のコストが非負（ $\ge 0$ ）であるため、その未確定ノードを経由する経路の長さは必ず $u$ の現在の暫定距離以上になる。これは仮定に矛盾する。したがって、常に最小コストのノードを確定させていく貪欲戦略によって、最終的に全ノードへの最短距離が保証される。

押さえておきたいポイント

全ての辺の重みが非負であるとき、ダイクストラ法は確実に大域的最適解（最短経路）を導く
優先度付きキュー（ヒープ木）を用いることで、計算量は $O((|V| + |E|)\log |V|)$ に抑えられる
A*探索は、直線距離などの「ヒューリスティック関数」を足すことで、ゴール方向へ優先的に波を伸ばす（カーナビやゲームAIの標準）
Googleマップ、電車の乗り換え案内、自律走行ロボットの走行計画の心臓部として使われている

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

ゲームキャラクターの自動追従・ナビゲーションAI

2Dグリッド上で障害物を避けながらターゲットへ向かう幅優先探索（BFS）/ ダイクストラ法のTypeScript実装。

1type Point = { x: number; y: number };
2
3// 2Dグリッド上の幅優先最短経路探索 (BFS)
4function findShortestPath(
5  grid: number[][], // 0: 通路, 1: 壁
6  start: Point,
7  goal: Point
8): Point[] | null {
9  const rows = grid.length;
10  const cols = grid[0].length;
11  const queue: Point[] = [start];
12  const parent = new Map<string, Point | null>();
13  parent.set(`${start.x},${start.y}`, null);
14
15  const dirs = [{ x: 1, y: 0 }, { x: -1, y: 0 }, { x: 0, y: 1 }, { x: 0, y: -1 }];
16
17  while (queue.length > 0) {
18    const curr = queue.shift()!;
19    if (curr.x === goal.x && curr.y === goal.y) {
20      // ゴール到達: 経路を復元
21      const path: Point[] = [];
22      let step: Point | null = curr;
23      while (step) {
24        path.unshift(step);
25        step = parent.get(`${step.x},${step.y}`) ?? null;
26      }
27      return path;
28    }
29
30    for (const d of dirs) {
31      const nx = curr.x + d.x;
32      const ny = curr.y + d.y;
33      const key = `${nx},${ny}`;
34      if (nx >= 0 && nx < cols && ny >= 0 && ny < rows && grid[ny][nx] === 0 && !parent.has(key)) {
35        parent.set(key, curr);
36        queue.push({ x: nx, y: ny });
37      }
38    }
39  }
40  return null; // 経路なし
41}