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