Dijkstra vs A*
Dijkstra vs A* compared — heuristics, speed, optimality and use cases, with interactive pathfinding visualizers.
Dijkstra finds shortest paths from a source to every node; A* adds a heuristic that aims at a single goal, exploring far fewer nodes. A* with a good heuristic is Dijkstra, only smarter about direction.
Dijkstra vs A* at a glance
| Dijkstra | A* | |
|---|---|---|
| Heuristic | None | Yes (estimate to goal) |
| Target | All nodes | One goal |
| Nodes explored | More | Fewer |
| Optimal | Yes | Yes (admissible heuristic) |
When to use Dijkstra
Use Dijkstra for shortest paths to all nodes or when no good heuristic exists.
When to use A*
Use A* for point-to-point pathfinding where you can estimate distance to the goal.
Tools for Dijkstra & A*
ダイクストラ法ビジュアライザー
グリッド上でダイクストラ法による経路探索を可視化。壁を描き、始点・終点を動かし、迷路を生成し、探索の進行をステップごとに確認できます。すべてブラウザ上で動作します。
ツールを開くA*経路探索ビジュアライザー
マンハッタン距離ヒューリスティックを使ったA*経路探索をグリッド上でインタラクティブに可視化。壁を描いてスタート/ゴールを動かし、迷路を自動生成し、探索をステップごとに実行できます。すべてブラウザ内で完結します。
ツールを開く幅優先探索(BFS)ビジュアライザー
グリッド上でインタラクティブに幅優先探索を体験できるツール。壁を描き、スタート地点とゴール地点を自由に動かし、迷路を自動生成しながら、探索が層ごとに広がっていく様子をステップ単位で観察できます。ブラウザだけですぐに動きます。
ツールを開く迷路ジェネレーター
再帰分割法（recursive division）によるアニメーション付き迷路ジェネレーター — 壁が組み上がっていく過程をステップごとに確認し、速度を調整して、新しい迷路を何度でも生成できます。経路探索アルゴリズムのビジュアライザーと組み合わせて使うのに最適です。すべてブラウザ上で完結します。
ツールを開くDijkstra vs A*
再帰分割アルゴリズムはどのように迷路を作るのですか？
まず何もない空間から始め、各区画をランダムな位置に隙間を残した1本の直線の壁で再帰的に仕切っていきます。これを区画がそれ以上分割できなくなるまで繰り返します。
「完全な迷路」とは何ですか？
任意の2マス間にちょうどひとつの経路しか存在しない迷路のことです——ループも孤立した領域もありません。再帰分割アルゴリズムは常に完全な迷路を生成します。
この迷路を解くことはできますか？
はい——同じ方眼グリッドを使うBFS、Dijkstra、A*のビジュアライザーにレイアウトをコピーすれば、経路探索アルゴリズムがどのように迷路を進んでいくか確認できます。
他にどんな迷路生成アルゴリズムがありますか？
Recursive backtracker（ランダム化DFS）、Prim法、Kruskal法、Wilson法、Eller法などがあり、それぞれ見た目の異なる構造の迷路が生成されます。