意義與機制
圖示以頂點表示位置，以可移動的關係作為邊。一條路徑的成本定義為經過的邊的成本之和，或每個頂點分配的成本之和。
寬度優先搜尋根據邊上移動的數量來擴充套件。 迪克斯特演算法根據當前已累計的最小成本來選擇候選。
關係與條件
放鬆更新 d(v) 為 min(d(v), d(u)+w(u,v))。 當找到更短的路徑時，距離和前驅資訊都會被更新。
標準流程依賴於迪克斯特演算法的前提，即沒有負權值。該實驗僅使用向上、向下、向左和向右的移動，採用正的成本，而忽略了對角線或實際道路的限制。
觀察實驗中需要注意的事物
BFS 最小化步數；Dijkstra 最小化總成本。
移動是正交的，並且成本為正值。可重複的預設設定牆壁和終點。
關鍵關係與符號
d(v) = min[d(u) + w(u,v)]
| 符號 | 含義 | 單位 |
|---|---|---|
| d(v) | 當前從起點到 v 的距離估計 | 成本 |
| w(u,v) | u 移動到 v 的成本 | 成本 |
透過範例確認
在成本相等的情況下，最短距離如何比較？
等量·BFS 減少步數； Dijkstra 最小化總成本。
常見誤解
- 並非寬度優先搜尋在所有具有不同邊權的有向圖中，都能使成本最小化。