なぜダイクストラは最短を保証できるのか？Pythonで手を動かして学ぶ経路生成①

はじめに

この記事を読み終えると、あなたは下のGIFのように、グリッド（格子）状のマップの上で、スタートからゴールまでの最短経路を「自動で・確実に」引くプログラムを、NumPyとMatplotlibだけで書けるようになります。

使うのは、経路探索のすべての出発点といえる古典アルゴリズム、ダイクストラ法（Dijkstra：始点から近いノードへ順に「ここまでの最短コスト」を確定させていく探索アルゴリズム）です。この記事の主役は、タイトルの問い ── 「貪欲に近い順で選んでいるだけなのに、なぜ最短が保証されるのか？」 です。ここが腹落ちすると、次回以降のA*やRRTが一気に理解しやすくなります。

このシリーズについて

本記事は、Pythonで経路生成（パスプランニング：ロボットやゲームのキャラが障害物をよけて目的地へ進む道すじを計算すること）を基礎から学ぶ全4回のシリーズの第1回です。

図：シリーズのマップ。各手法は「前の手法のここが不満、だからこれを足した」という差分のシリーズとしてつながっている。

ダイクストラ法は、このシリーズの第1ページです。あとの全手法が比較される**基準（ものさし）**になるので、まずはここをしっかり自分のものにしましょう。

想定読者と環境

• 想定読者：Pythonが少し書ける方で、経路探索アルゴリズムを初めて学ぶ人
• 前提知識：for文・if文・辞書・リストがわかればOK。グラフ理論やアルゴリズムの事前知識は不要です

環境は次の2つだけ。どちらも定番ライブラリです。

ライブラリ	用途	インストール
NumPy	マップ（格子）を配列で持つ	pip install numpy
Matplotlib	経路と探索の様子を可視化	pip install matplotlib

優先度キューに使う heapq（ヒープキュー）はPython標準ライブラリなので、追加インストールは不要です。

なお本記事のマップには、少し工夫を入れます。マスは 通行可(0)／障害物(1)／ぬかるみ(2) の3種類。このように格子状のマスごとに「通れるか／通れないか」を記録したマップ形式を、占有格子地図（occupancy grid map：ロボット分野でいちばん基本的なマップ表現）と呼びます。ぬかるみは「通れるがコストが大きい地形」で、ここでダイクストラの本領 ── 最短とは距離ではなくコスト合計の最小のこと ── がはっきり見えてきます。

1. マップを「グラフ」とみなす

最短経路を求めるアルゴリズムの多くは、グラフ（graph：「点」と、それらを結ぶ「線」だけで世界を表したもの）の上で動きます。そこでまず、格子状のマップを、グラフとして見直します。やることは、たった3つの読み替えです。

図：1マスを1つのノード（点）、隣のマスへの移動を1本のエッジ（線）とみなす。8近傍なら、1つのセルから8本のエッジが伸びる（縦横の4本＝コスト1、斜めの4本＝コスト√2）。

• セル（マス）→ ノード（node：グラフの点）… 通行できるマス1つを1個のノードとみなす
• 隣り合うセル → エッジ（edge：グラフの線。2ノードのつながり）… 隣へ直接移動できることを1本の線で表す
• 1回の移動 → コスト（cost：その線を通る「重み」。距離だと思ってOK）… 移動の大変さを数値にする

本記事では隣を8近傍（上下左右の4方向＋斜め4方向）とし、移動コストを 基本コスト（縦横1・斜め√2）×「入る先の地形の重み」 で決めます。

地形	記号（値）	地形の重み	意味
ふつうの地面	CELL_FREE(0)	1.0	基準
ぬかるみ	CELL_MUD(2)	3.0	通れるが3倍たいへん
障害物	CELL_OBSTACLE(1)	―	通行不可（そもそも通れない）

たとえば、ふつうの地面へまっすぐ入るなら $1 \times 1.0 = 1$、ぬかるみへまっすぐ入るなら $1 \times 3.0 = 3$、ぬかるみへ斜めに入るなら $\sqrt{2} \times 3.0 \approx 4.24$ です。

こうしてマップは「重みつきグラフ」に姿を変え、問題はすっきりした形になります ── スタートからゴールまで、たどったエッジのコスト合計がいちばん小さい道すじを見つけよ。これが「最短経路問題」です。

「最短」＝マスの数が最少、ではありません。斜めは√2、ぬかるみは3倍。本記事の「最短」はコスト合計が最小の道すじです。だからダイクストラは、遠回りでもぬかるみを避けた方が得なら、迷わず迂回します（これは後で実際に目で確かめます）。

2. ダイクストラの考え方 ── 「到着が早い順」に確定させる

コスト合計が最小の道すじを、どう見つけるか。「全部の道を試して比べる」は、マップが少し大きくなるだけで組み合わせが天文学的になり、非現実的です。

ダイクストラのアイデアはまったく違います。ひとことで言えば、

スタートに近いノードから順に、「ここまでの最短コスト」を1つずつ確定させていく。

一度に全部を考えず、確実にわかるところから少しずつ地面を固めていくイメージです。

これを、こんな場面で考えてみてください。スタート地点から、大勢の探検隊がいっせいに歩き出します。全員おなじ速さで歩きますが、ぬかるみに入ると足を取られて3倍の時間がかかります。隊は分かれ道のたびに枝分かれし、あらゆる方向へ散っていきます。

ここで、あるマスに 「最初に誰かが到着した時刻」 に注目してください。その時刻こそが、スタートからそのマスまでの最短コストです。あとから別の隊が同じマスへ来ても、先に着いた人より早いことはありえません。だから、最初の到着を見た瞬間に、そのマスの値は確定してよいのです。

ダイクストラがやっているのは、この 「到着した順に、時刻を記録して確定させる」という作業だけです。いま到着済みの場所のうちいちばん時刻の早いところを選び、そこから隣のマスへ一歩進める。これをくり返します。

コスト＝「到着時刻」 と読み替えると、すべてが噛み合います。ぬかるみは時間を3倍食うから遅れて到着する。遠回りは距離のぶん遅れて到着する。そして先に着いた道が勝ち ── それが「最短」の正体です。

このようにその場その場で最善に見えるものを選ぶやり方を貪欲法（greedy：目先の最善をとる戦略）と呼びます。貪欲法は間違うことも多いのですが、ダイクストラはちゃんと最短が保証される（理由は第3節）のがうれしい性質です。

式：実コスト g(v) と「緩和」

各ノード $v$ について、次の値を考えます。

g(v) = \text{スタートから } v \text{ までの、いまわかっている最短コスト}

$g$ は goal ではなく、スタートからの「実際にかかったコスト」を表す記号です。この $g$ は次回A*でも、その先のRRT*でも、ずっと主役として登場します。「いま、ここまで来るのに最小でどれだけかかったか」が $g$ ── これだけは覚えてください。

最初はスタート $s$ だけ $g(s)=0$、ほかは「まだ行き方がわからない」意味で $g(v)=\infty$ にします。探索中、あるノード $u$ から隣の $v$ へ移れるとわかったとき、次を比較します。

g(u) + w(u, v) < g(v) \quad \Longrightarrow \quad g(v) \leftarrow g(u) + w(u, v)

$w(u,v)$ はエッジ $u \to v$ のコスト（さっきの $1$ や $\sqrt{2}$、ぬかるみなら $3$ や $4.24$）です。意味は「$u$ を経由して $v$ へ行くほうが今まで知っていた道より短いなら、$v$ の最短コストを更新する」。この更新を緩和（relax：これまでの見積もりを、より短い値へゆるめて書き換えること）と呼びます。ダイクストラは、結局この緩和をひたすらくり返すだけのアルゴリズムです。

あわせて「$v$ へは $u$ から来るのが最短だった」という**来た道（親ノード）**も記録します。ゴール到達後にこれを逆にたどれば、経路そのものを復元できます。

優先度キューという「係」

第2節で「いま手元にある中でいちばんコストの小さいノードを選ぶ」と言いました。毎回ぜんぶ見比べると遅くなるので、優先度キュー（priority queue：入れるのは自由だが、取り出すと必ず「いちばんコストが小さいもの」が出てくる特別な箱）を使います。Pythonでは標準ライブラリ heapq がこれにあたります。「最小コストのノードを素早く取り出す係」がいる、と押さえておけば十分です。

3. なぜ最短が保証されるのか（この記事の核心）

貪欲に「近い順」で選ぶだけなのに、なぜ最短になるのか。カギは次の事実です。

優先度キューから取り出して「確定」したノードの $g$ 値は、もう二度と更新されない（それ以上短くならない）。

なぜか。あるノード $v$ がキューから取り出されたということは、その時点で未確定のすべてのノードの中で $v$ がいちばんコストが小さかったということです。

図：確定ノード v のコストが二度と更新されない理由。あとから来る道は、必ず「v よりコストの大きい未確定ノード X」を経由する。そこへさらに 0 以上のコストを足すのだから、合計は g(v) を超える ── どうやっても追い越せない。

もし「あとから $v$ へのもっと短い道」があるなら、その道はまだ確定していない別のノードを経由するはず。でもその経由ノードは（未確定なので）$v$ よりコストが大きい。コストが大きいノードを経由して $v$ より小さいコストで着くことは、コストがマイナスにならない限りありえない。だから $v$ の値はもう動かない ── これがダイクストラの美しさです。

だいじな前提：コストにマイナスがないこと。 上の理屈は「経由ノードのコストが大きければ追い越せない」という一点に支えられています。「通るとコストが減る」エッジがあるとこれが崩れ、ダイクストラは正しい答えを出せません。さいわい「移動距離」や「地形の重み」のコストは必ず $0$ 以上なので、この前提はいつも満たされます。

4. 実装する

いよいよコードです。処理の流れは次のとおり。

図：ダイクストラ法の処理フロー。「取り出す → 確定 → 隣を緩和」をキューが空になるまでくり返すだけ。

ファイルは、役割ごとに小さく分けます。各ファイルはフラットな名前で import し合うので、実行するときは必ずそのフォルダに移動してから python main.py としてください。

ファイル	役割
constant.py	共通の定数（セルの種類・地形の重み・移動コスト）
grid_map.py	占有格子地図 GridMap とサンプルマップ
dijkstra.py	ダイクストラ法の本体
plot.py	可視化（静止画・gif）
main.py	マップを作り、解いて、図を出す

4-1. 定数とマップを用意する

まず定数です。セルの種類と、地形ごとの重み（ふつうの地面は1・ぬかるみは3）を決めておきます。

# constant.py
import numpy as np
from enum import Enum    # 近傍の種類を名前で表す

# セルの種類（占有格子地図の各マスがとる値）
CELL_FREE     = 0    # 通行可（ふつうの地面）
CELL_OBSTACLE = 1    # 障害物（通行不可）
CELL_MUD      = 2    # ぬかるみ（通れるが、通るのが大変な地形）

# 各地形の「通りにくさ」の重み（障害物は通行不可なのでここには含めない）
TERRAIN_COST = {
    CELL_FREE: 1.0,    # ふつうの地面 … 重み1
    CELL_MUD:  3.0,    # ぬかるみ     … 重み3（3倍たいへん）
}

# 1マス移動の基本コスト（地形の重みをかける前の値）
COST_STRAIGHT = 1.0                    # 上下左右へ1マス
COST_DIAGONAL = float(np.sqrt(2))      # 斜めへ1マス（直角三角形の斜辺）


class CONNECTIVITY(Enum):
    """近傍の種類（何方向へ動けるか）"""
    FOUR  = 4    # 上下左右の4方向
    EIGHT = 8    # 4方向＋斜め4方向＝8方向

次にマップです。GridMap は「各マスの種類」を持ち、neighbors() があるセルの隣（通行可能なもの）を「セルと移動コスト」のペアで返します。ここが地形コストの心臓部です ── 入る先がぬかるみなら、移動コストが3倍になります。

# grid_map.py
# 占有格子地図（occupancy grid map）と、その上の近傍の定義

# ライブラリの読み込み
import numpy as np    # 数値計算

# 自作モジュールの読み込み
from constant import *    # 定数（セルの種類・地形コスト・移動コスト）


# 近傍の相対位置（row, col の増分）
NEIGHBOR_STRAIGHT = [(-1, 0), (1, 0), (0, -1), (0, 1)]           # 上下左右
NEIGHBOR_DIAGONAL = [(-1, -1), (-1, 1), (1, -1), (1, 1)]         # 斜め4方向


class GridMap:
    """占有格子地図（各マスが 通行可/障害物/ぬかるみ のいずれか）"""

    def __init__(self, grid: np.ndarray, start: tuple, goal: tuple) -> None:
        """
        パラメータ
            grid: 各セルの種類を並べた2次元配列（CELL_FREE / CELL_OBSTACLE / CELL_MUD）
            start: スタートセル (row, col)
            goal: ゴールセル (row, col)
        """
        self.grid  = grid
        self.start = start
        self.goal  = goal
        self.rows, self.cols = grid.shape

    def in_bounds(self, cell: tuple) -> bool:
        """
        セルがマップの内側にあるか判定する

        パラメータ
            cell: 判定したいセル (row, col)

        戻り値
            True: マップの内側 / False: マップの外
        """
        row, col = cell
        return 0 <= row < self.rows and 0 <= col < self.cols

    def is_free(self, cell: tuple) -> bool:
        """
        セルが通行可能か判定する（マップの内側で、かつ障害物でない）

        ぬかるみ（CELL_MUD）は「コストは高いが通れる」ので通行可能と判定する。

        パラメータ
            cell: 判定したいセル (row, col)

        戻り値
            True: 通行可能 / False: マップの外 または 障害物
        """
        if not self.in_bounds(cell):
            return False
        return self.grid[cell] != CELL_OBSTACLE

    def neighbors(self, cell: tuple, connectivity: CONNECTIVITY = CONNECTIVITY.EIGHT):
        """
        指定セルの隣（通行可能なもの）を「セルと移動コスト」のペアで返す

        移動コスト＝基本コスト（縦横1・斜め√2）×「入る先の地形の重み」。
        ぬかるみ（重み3）へ入る移動は、そのぶん高コストになる。

        パラメータ
            cell: 対象セル (row, col)
            connectivity: 近傍の種類（4近傍 / 8近傍）

        戻り値
            (隣のセル, 移動コスト) を順に返すジェネレータ
        """
        row, col = cell

        # 縦横の移動（基本コスト1）
        moves = [(dr, dc, COST_STRAIGHT) for dr, dc in NEIGHBOR_STRAIGHT]
        # 8近傍なら斜め（基本コスト√2）も加える
        if connectivity == CONNECTIVITY.EIGHT:
            moves += [(dr, dc, COST_DIAGONAL) for dr, dc in NEIGHBOR_DIAGONAL]

        for dr, dc, base_cost in moves:
            n_cell = (row + dr, col + dc)
            if not self.is_free(n_cell):
                # マップの外 or 障害物なら通れない
                continue
            # 入る先の地形の重みをかける（ふつうの地面は1倍、ぬかるみは3倍）
            terrain = TERRAIN_COST[self.grid[n_cell]]
            move_cost = base_cost * terrain
            yield n_cell, move_cost

サンプルマップは、同じ grid_map.py の末尾にこう書きます。中央に縦の壁を置き、1マスだけ隙間（隘路）を空け、その先にぬかるみの帯を置きます。

def make_sample_map() -> GridMap:
    """
    本記事共通のサンプルマップをつくる

    - 20×20 のグリッド
    - 中央に縦の壁。1マスだけ隙間（隘路）を空けてある
    - 直進ルート上に「ぬかるみ帯（重み3）」を置き、最短経路がそこを避けるか観察する

    戻り値
        スタート(18,1)・ゴール(1,18) を設定済みの GridMap
    """
    rows, cols = 20, 20
    grid = np.full((rows, cols), CELL_FREE, dtype=int)

    # 中央の縦の壁（col=10）。row=8 の1マスだけ隙間を空ける（隘路）
    grid[0:20, 10] = CELL_OBSTACLE
    grid[8, 10]    = CELL_FREE

    # ぬかるみ帯（重み3）。隙間を抜けた先、ゴールへ向かう斜めライン上に置く
    grid[3:9, 12:16] = CELL_MUD

    start = (18, 1)     # 左下
    goal  = (1, 18)     # 右上
    return GridMap(grid, start, goal)

4-2. ダイクストラ本体

理論編の登場人物を、コードでは次のデータで持ちます。

理論の言葉	コードでの持ち方	中身
実コスト $g(v)$	dist（辞書）	各セルの最短コスト
来た道（親）	came_from（辞書）	各セルへ「どこから来たか」
確定済みノード	visited（集合）	もう動かないと札を立てたセル
確定した順番	explored（リスト）	可視化・比較用の記録
優先度キュー	queue（heapq）	最小コストのセルを取り出す箱

本体は「キューから取り出す → visitedで確定 → 隣を緩和」を書き下すだけです。

# dijkstra.py
import heapq    # 優先度キュー（取り出すたびに最小コストの要素が出る）

from constant import CONNECTIVITY
from grid_map import GridMap


def dijkstra(grid_map: GridMap, connectivity: CONNECTIVITY = CONNECTIVITY.EIGHT) -> tuple:
    """
    Dijkstra 法でスタートからゴールまでの最短経路（コスト最小の経路）を求める

    パラメータ
        grid_map: 占有格子地図（スタート・ゴール設定済み）
        connectivity: 近傍の種類（4近傍 / 8近傍）

    戻り値
        path: 最短経路（セルのリスト。到達できなければ空リスト）
        explored: 確定した順に並べた探索済みセルのリスト（可視化・比較用）
        cost: ゴールまでの最短コスト（到達できなければ無限大）
    """
    start = grid_map.start
    goal  = grid_map.goal

    # g 値（始点からの実コスト最小値）と，経路復元用の親ノード
    dist      = {start: 0.0}
    came_from = {}

    # 確定済みノード（コストが二度と更新されない）の集合と，確定順
    visited  = set()
    explored = []

    # 優先度キュー。要素は (コスト, セル)
    queue = [(0.0, start)]

    while queue:
        # いま未確定の中で最小コストのノードを取り出す
        cost, current = heapq.heappop(queue)
        if current in visited:
            # すでに確定済み（より小さいコストで処理済み）なので飛ばす
            continue
        visited.add(current)
        explored.append(current)

        if current == goal:
            # ゴールを確定したら終了（これ以上小さいコストでは来られない）
            break

        # 近傍ノードを緩和（relax）する
        for n_cell, move_cost in grid_map.neighbors(current, connectivity):
            new_cost = cost + move_cost
            # g(u) + w(u,v) < g(v) なら，より短い経路が見つかったので更新
            if n_cell not in dist or new_cost < dist[n_cell]:
                dist[n_cell]      = new_cost
                came_from[n_cell] = current
                heapq.heappush(queue, (new_cost, n_cell))

    # 経路を復元
    path = reconstruct_path(came_from, start, goal)
    cost = dist.get(goal, float("inf"))

    return path, explored, cost

理論とコードを、4つの勘どころで結びつけておきます。

• 最小コストを一発で取り出す：heapq.heappop(queue) が、いま未確定の中でいちばん小さいセルを返す。要素を (コスト, セル) のタプルにしておくと、heapq がコスト順に並べてくれる
• 緩和の本体：new_cost = cost + move_cost が式 $g(u)+w(u,v)$ そのもの。move_cost は neighbors() が地形の重みごと返してくれる。「今より短ければ dist を更新」が緩和
• 親の記録：came_from[n_cell] = current で「このセルへは current から来るのが最短」を覚える（あとで経路を復元するパンくず）
• 確定したら二度と疑わない：取り出したセルが visited にあれば continue で飛ばす。これが「確定ノードの $g$ は更新されない」をコードで保証する部分

つまずきポイント：なぜ更新時に古い要素を消さないの？ heapq には「中の要素を書き換える／消す」機能がありません。そこで、より短い道が見つかるたびに新しい (コスト, セル) を push し、古いほうは取り出したときに visited で弾く、という割り切りをします。同じセルがキューに重複して入りますが、確定処理は一度だけなので、結果は正しいまま、コードはぐっと素直になります。ここは自分で書くと必ず一度は悩むところなので、先に種明かししておきます。

4-3. 経路の復元

came_from（親のパンくず）を、ゴールから逆にたどればスタートまでの経路がよみがえります。ゴールに記録がなければ（壁に囲まれて届かない場合）空リストを返します。

def reconstruct_path(came_from: dict, start: tuple, goal: tuple) -> list:
    """
    親ノードの記録をたどって，スタートからゴールまでの経路を復元する

    パラメータ
        came_from: 各ノードの親ノードを記録した辞書
        start: スタートセル (row, col)
        goal: ゴールセル (row, col)

    戻り値
        path: スタートからゴールまでのセルのリスト（到達できなければ空リスト）
    """
    if goal not in came_from:
        # ゴールに到達できなかった
        return []

    # ゴールから親をたどり，最後に反転して「始点 → 終点」の順にする
    path = [goal]
    current = goal
    while current != start:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

4-4. 動かす

main.py でサンプルマップを作り、解いて、図に落とします。

# main.py
from constant import *
from grid_map import make_sample_map
from dijkstra import dijkstra
from plot import plot_result, plot_search_animation    # 可視化（全文は 4-4 末尾の折りたたみに）


def main() -> None:
    grid_map = make_sample_map()

    # Dijkstra 法で最短経路を求める（8近傍）
    path, explored, cost = dijkstra(grid_map, CONNECTIVITY.EIGHT)

    if not path:
        print("経路が見つかりませんでした")
        return

    print(f"通過点数（セル数）= {len(path)}")
    print(f"経路コスト        = {cost:.2f}")
    print(f"展開ノード数      = {len(explored)}")

    plot_result(grid_map, path, explored, "dijkstra_path.png",
                title=f"Dijkstra (explored={len(explored)}, cost={cost:.2f})")
    plot_search_animation(grid_map, path, explored, "dijkstra_anime.gif",
                          step=10, title="Dijkstra")


if __name__ == "__main__":
    main()

可視化 plot.py は本筋ではないので本文では触れませんが、Matplotlibで「障害物＝黒・ぬかるみ＝薄茶・探索済み＝水色・経路＝橙」を重ねて描いているだけです。この記事だけで図を再現できるよう、全文を下に置いておきます（コピペしてそのまま使えます）。

plot.py の全文（クリックで展開）

# plot.py
# 可視化（静止画・アニメーション）

# ライブラリの読み込み
import matplotlib
matplotlib.use("Agg")    # 画面を出さずに画像ファイルへ保存（ヘッドレス）
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
import matplotlib.animation as animation
import numpy as np

# 自作モジュールの読み込み
from constant import *
from grid_map import GridMap

# 日本語が豆腐（□）にならないようフォントを指定（macOS の場合）
# ※ 本記事の図タイトルは英語なので、この2行は無くても動きます。
#    Windows なら "Meiryo"、Linux なら "IPAexGothic" などに読み替えてください。
plt.rcParams["font.family"] = "Hiragino Sans"
plt.rcParams["axes.unicode_minus"] = False

# 背景（地形）の色：通行可=白, 障害物=黒, ぬかるみ=薄茶
_TERRAIN_CMAP = ListedColormap(["white", "black", "#d2b48c"])


def _draw_base(ax, grid_map: GridMap) -> None:
    """地形・スタート・ゴールの下地を描く"""
    ax.imshow(grid_map.grid, cmap=_TERRAIN_CMAP, vmin=0, vmax=2, origin="upper")
    sr, sc = grid_map.start
    gr, gc = grid_map.goal
    ax.plot(sc, sr, "o", color="tab:green", markersize=10, label="start")
    ax.plot(gc, gr, "*", color="tab:red",   markersize=14, label="goal")
    ax.set_xticks([]); ax.set_yticks([])


def plot_result(grid_map: GridMap, path: list, explored: list,
                filename: str, title: str = "") -> None:
    """最短経路＋探索済みセルの静止画を保存"""
    fig, ax = plt.subplots(figsize=(6, 6))
    _draw_base(ax, grid_map)

    # 探索済みセル（水色）
    if explored:
        er = [c[0] for c in explored]
        ec = [c[1] for c in explored]
        ax.plot(ec, er, "s", color="skyblue", markersize=6, alpha=0.5)

    # 最短経路（橙）
    if path:
        pr = [c[0] for c in path]
        pc = [c[1] for c in path]
        ax.plot(pc, pr, "-", color="tab:orange", linewidth=2.5)

    # スタート・ゴールを前面に描き直す
    _draw_base(ax, grid_map)
    ax.set_title(title)
    fig.savefig(filename, dpi=110, bbox_inches="tight")
    plt.close(fig)


def plot_search_animation(grid_map: GridMap, path: list, explored: list,
                          filename: str, step: int = 10, title: str = "") -> None:
    """探索フロントが広がり，最後に経路が引かれるアニメーションを保存"""
    fig, ax = plt.subplots(figsize=(6, 6))

    frames = list(range(0, len(explored), step)) + [len(explored)]

    def update(i: int) -> None:
        ax.clear()
        _draw_base(ax, grid_map)
        shown = explored[:frames[i]]
        if shown:
            er = [c[0] for c in shown]
            ec = [c[1] for c in shown]
            ax.plot(ec, er, "s", color="skyblue", markersize=6, alpha=0.5)
        # 最終フレームで経路を描く
        if i == len(frames) - 1 and path:
            pr = [c[0] for c in path]
            pc = [c[1] for c in path]
            ax.plot(pc, pr, "-", color="tab:orange", linewidth=2.5)
        _draw_base(ax, grid_map)
        ax.set_title(title)

    anim = animation.FuncAnimation(fig, update, frames=len(frames), interval=120)
    anim.save(filename, writer="pillow")
    plt.close(fig)

GIFの保存には Pillow を使います（pip install pillow）。step=10 は「探索10ステップぶんを1フレームに間引く」という意味で、大きくするとGIFが軽く・粗くなります。

5. 動かして、目で確かめる

5つのファイル（constant.py / grid_map.py / dijkstra.py / plot.py / main.py）を同じフォルダに置き、そのフォルダへ移動して実行します。

cd dijkstra          # 5つの .py を置いたフォルダ
python main.py

ターミナルには、次のように表示されます。

通過点数（セル数）= 23
経路コスト        = 26.97
展開ノード数      = 369

この図のいちばんの見どころは、橙色の経路が薄茶色の「ぬかるみ」をきれいに避けて縁を回り込んでいることです。試しに constant.py の TERRAIN_COST[CELL_MUD] を 1.0（＝ふつうの地面と同じ）にして走らせると、経路はぬかるみを4マス突っ切り、コストは 26.97 → 24.63 に下がります。それでもダイクストラが迂回を選んだのは、「ぬかるみ4マス分の割増コスト」より「回り道の距離」の方が安かったから ── 距離ではなくコストで最短を測っている動かぬ証拠です。

3つの数字も読み解いておきます。

• 通過点数 = 23：スタートからゴールまで23セルを通過
• 経路コスト = 26.97：縦横 $1$・斜め $\sqrt{2}$・ぬかるみ×3を足したコスト合計。これがダイクストラの保証する「最小」
• 展開ノード数 = 369：今回いちばん注目してほしい数字。マップは $20\times20=400$ セル、障害物19を除くと381セル。その369セル（ほぼ全部）を調べたことになる

第2節の「探検隊が全方向へ均等に散っていく」直感が、この水色の広がりとして目に見えます。

6. まとめ ── 「369の無駄」が次のA*への扉

ダイクストラで、グリッド上の最短経路を自動で・確実に引けるようになりました。ここまでの要点です。

• マップを「重みつきグラフ」とみなし、実コスト $g(v)$ を緩和でくり返し更新する
• 優先度キューで「いちばん近い未確定ノード」を取り出し、確定させる
• 確定ノードは二度と更新されない（＝最短保証。ただしコストが非負のとき）
• 「最短」は距離ではなくコスト合計の最小。だからぬかるみを避けて迂回する

一方で、展開ノード数369をかみしめてください。最短経路は23セルなのに、それを見つけるためにマップのほぼ全部を調べていました。ダイクストラは「ゴールがどこにあるか」をまったく気にせず、近い順に広げるだけだからです。

手法	経路コスト	展開ノード数	ゴール方向を意識？
ダイクストラ（今回）	26.97	369	しない
A*（次回）	同じマップで比較	←どこまで減る？	する

「ゴールはあっちにあるんだから、そっちを重点的に探せばいいのに」── その素直な不満こそ、次回A*への扉です。A*は、ダイクストラの $g$（ここまでの実コスト）に、「ゴールまであとどれくらいか」という見積もり $h$ を足すことで、探索をゴール方向へ引き寄せます。まったく同じマップでA*を動かし、この369がどこまで減るかを次回フェアに見比べます。

章末：やってみよう

手を動かすと、ダイクストラの性質がぐっと体に入ります。

1. ぬかるみを消す／広げる：make_sample_map() の grid[3:9, 12:16] = CELL_MUD を消すと、経路はまっすぐ突っ切ってコストは 24.63 に。逆にぬかるみを広げると、迂回が大きくなります。「距離ではなくコスト最小」を体感してください。
2. 4近傍にしてみる：main.py の dijkstra(grid_map, CONNECTIVITY.EIGHT) を CONNECTIVITY.FOUR（上下左右だけ）に変えると、斜め移動が禁じられて経路は階段状に。コストは 26.97 → 34.00 に増えます。「最短」が近傍の決め方しだいで変わるのが分かります。
3. 隙間の位置を下へ動かす：make_sample_map() の grid[8, 10] = CELL_FREE を grid[18, 10] = CELL_FREE に変えると、通り抜け口がマップの下端近くへ移ります。経路は壁の下まで回り込んでからゴールを目指すので、コストは 26.97 → 29.31 に増えます。「壁のどこに穴が空いているか」だけで最短経路がまるごと変わることを体感してください。
   なお grid[8, 10] = CELL_FREE の行を消すと、壁が列を完全にふさいでスタートとゴールが分断され、「経路が見つかりませんでした」と表示されます（＝迂回すらできない）。
4. 閉じ込める：return の直前に grid[16, 0:4] = CELL_OBSTACLE と grid[16:20, 3] = CELL_OBSTACLE を足すとスタートが孤立し、「経路が見つかりませんでした」と表示されます。reconstruct_path の「届かなければ空リスト」が効いている証拠です。
5. 展開ノード数を覚えておく：いまの 369 をメモ。次回A*で同じマップを解いたとき、この数字がどれだけ小さくなるか ── それがA*の賢さの大きさです。

終わりに

今回は経路生成の出発点・ダイクストラ法を、理論と実装の両面から手を動かして学びました。「確定したら二度と疑わない」という一点で最短が保証される、そして「最短とはコスト合計の最小」だからぬかるみを避けて迂回する ── この2つが腹落ちしていれば大成功です。

経路生成シリーズ全体は、こちらのまとめから辿れます。

この先のRRT・RRT*といったサンプリングベースの手法（点を撒いてマップを作る系）も、上のまとめから読めます。

次回は ②A*（エースター） です。今回の「369の無駄」が、ヒューリスティック $h$ でどこまで減るか ── お楽しみに。

役に立ったら いいね・ストック で応援いただけると、次回の励みになります