Dijkstra 算法
找出从起点到终点最便宜的路。它总是先取出优先队列里最便宜的位置,所以代价会像洪水一样从起点向外扩散。
- 时间 O((V + E) log V)
- 内存 O(V)
- 使用优先队列
这些是什么意思？
- 代价:一步要付出的成本。迷宫中踩上地面为 1、泥地为 3、水为 9;图中是边上的数字。
- 优先队列:不是先到先出,而是最便宜的先出。
- 估计(h):对剩余代价的猜测。只有它从不偏高,A* 才能保持精确。
- 松弛一条边:检查经过当前位置能否让邻居的代价更低,如果能就采用。
0 / 294 步
- 在队列中
- 当前
- 已完成
- 最便宜的路
- 地面 · 1
- 泥地 · 3
- 水 · 9
- 墙
新: 从 A1 出发,代价 0。它是队列中唯一的元素。
空格键：播放或暂停。左右方向键：单步移动。Home 和 End 键：跳转。
试试看： 选择“沼泽”。最便宜的路要绕过整片泥地:步数是直线的两倍,却仍然更便宜(34 对 36)。
工作原理
每个位置都有一个代价:起点为 0,其余为无穷大。Dijkstra 把到达过的位置放进优先队列,每次都取出最便宜的那个。此时它的代价就确定了,因为通往它的任何其他路都必须经过至少同样昂贵的位置。然后它逐个查看邻居:如果经过刚取出的位置比邻居目前的代价更便宜,邻居就采用新代价,并记下自己从哪里来。取出终点后,沿着这些记录往回走就是最便宜的路。
适用场合
当各步代价不同且都不小于零时使用 Dijkstra:道路地图和导航、网络路由、最便宜的航班中转。如果每一步代价都一样,BFS 能更简单地给出同样的答案。有负代价时 Dijkstra 可能出错,这时用 Bellman–Ford。