ダイクストラ法
スタートからゴールまでの最も安い道を見つけます。優先度付きキューで待っている最も安い場所を常に取り出すので、コストがスタートから洪水のように広がります。
- 時間 O((V + E) log V)
- メモリ O(V)
- 優先度付きキューを使う
用語の意味
- コスト:移動にかかる値段。迷路では地面が1、泥が3、水が9。グラフでは辺に書かれた数です。
- 優先度付きキュー:先に来た順ではなく、最も安いものから出ていく待ち行列。
- 見積もり(h):残りコストの予想。A*が正確でいられるのは、見積もりが決して高すぎない場合だけです。
- 辺の緩和:今の場所を通ると隣のコストが下がるかを確かめ、下がるならそれを採用すること。
0 / 294 ステップ
- キュー内
- 現在
- 完了
- 最も安い道
- 地面 · 1
- 泥 · 3
- 水 · 9
- 壁
発見: A1 からスタート、コスト0。キューにはこれだけです。
スペースキー: 再生・一時停止。左右の矢印キー: ステップ移動。Home キーと End キー: ジャンプ。
試してみましょう: 「沼地」を選んでください。最も安い道は泥をぐるりと迂回します。直線の2倍の手数なのに、それでも安いのです(36に対して34)。
仕組み
各場所にコストを付けます。スタートは0、ほかは無限大です。ダイクストラ法は到達した場所を優先度付きキューに入れ、常に最も安いものを取り出します。その時点でコストは確定します。ほかの道は少なくとも同じくらい高い場所を通るしかないからです。次に隣を一つずつ見ます。今取り出した場所を通る方が隣のこれまでのコストより安ければ、隣は新しいコストを受け取り、どこから来たかを覚えます。ゴールを取り出したら、その記録をたどると最も安い道に戻れます。
向いている場面
移動のコストがまちまちで、どれもゼロ未満でないときに使います。道路地図やカーナビ、ネットワークの経路制御、最も安い乗り継ぎ便などです。どの移動も同じコストなら、BFSの方が同じ答えを簡単に出せます。負のコストがあるとダイクストラ法は誤ることがあり、その場合はベルマン–フォード法を使います。