意义与机制
图示以顶点表示位置，以可移动的关系作为边。一条路径的成本定义为经过的边的成本之和，或每个顶点分配的成本之和。
宽度优先搜索根据边上移动的数量来扩展。 迪克斯特算法根据当前已累计的最小成本来选择候选。
关系与条件
放松更新 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 最小化总成本。
常见误解
- 并非宽度优先搜索在所有具有不同边权的有向图中，都能使成本最小化。