Dijistra其实就是一种搜索算法， 它是BFS的升级版。假设每条路径的值为1，那么两点之间的最短路径可以直接用BFS求解。
如果每条路径值不一样呢？和BFS相比，又有什么特殊之处？
BFS算法基于队列实现，扩展节点时，直接取队列第一个节点。而Dijstra算法基于优先队列实现，扩展节点时，直接取最短路径节点。
如下图所示：其实，Dijstra和BFS都是属于uniform-cost search （UCS）算法的特殊情况。 UCS在每次扩展节点的时候， 都扩展代价最小的节点。
有趣的是：而UCS算法是属于A*算法的特殊情况， 对上述算法感兴趣的话，可以参考《人工智能 一种现代的方法》
搜索算法关系图
网友评论