概念と仕組み
グラフは、位置を頂点として、および移動可能な関係性を辺として表現します。 パスのコストは、たどる辺のコストの合計、または各頂点に割り当てられたコストの合計として定義されます。
幅優先探索は、辺の移動回数に基づいて拡張されます。ダイクストラ法は、現在の累積最小コストに基づいて候補を選びます。
関係式と成立条件
リラックス更新において、d(v) は min(d(v), d(u)+w(u,v)) に更新される。 より安い経路が見つかった場合、距離と先駆者情報が両方とも更新される。
標準的なダイクストラ法の手順は、負の重みが存在しないという条件に基づいています。この実験では、上、下、左、右の移動のみを使用し、正のコストを用いることを前提とします。また、斜め移動や実際の道路の制約は考慮されていません。
仮想実験で読み取る変化
幅優先は歩数、ダイクストラは総費用を最小化します。
上下左右に移動し費用は正です。壁と始終点は再現可能な設定で変えます。
重要な関係式と記号
d(v) = min[d(u) + w(u,v)]
| 記号 | 意味 | 単位 |
|---|---|---|
| d(v) | 始点からvまでの現在の推定距離 | コスト |
| w(u,v) | uからvへ移動するコスト | コスト |
例で確かめる
全セルの費用が同じなら両手法の最短距離は？
等しいです · 幅優先は歩数、ダイクストラは総費用を最小化します。
よくある誤解
- 幅優先探索が、異なるエッジの重みを持つすべてのグラフにおいて、常に最小コストを保証するわけではありません。