Dijkstra
Dijkstra 伪代码
Dijkstra 为什么不能有负权重
注意: 文中提到的云即指优先队列。放入云中其实就是从优先队列中取出。
简而言之:u是z的下一个顶点,并且u是最短路上的点,D[u]>d(v,u)。如果z没有先于u被永久标记的话(没有进入点云),D[u]<D[z]。但是由于u点是第一个不满足条件的点,所以z是满足条件的,所以D[z]就是最短路。这说明D[z]=d(v,z)>D[u]>d(v,u)。除非(z,u)的权重为负,不然上式子是不可能成立的。
Dijkstra算法复杂度
当算法中的队列通过二叉堆实现时,需要的算法复杂度为:
Bellman-Ford算法
Bellman-Ford算法伪代码
注意:: 虽然该算法允许负权重的弧线,弧线必须是有限的,不然就相当于存在负权重的圈。
Bellman-Ford判断是否有负权
如果在循环了n次后某些节点还能够优化,说明有包含负权重的圈。
Bellman-Ford为什么能找到单源最短路?
Bellmon-ford算法复杂度
Dijkstra 与Bellmon-ford算法特点对比
(1)Dijkstra为贪心算法,Bellmon-Ford算法不是贪心算法
(2)Dijkstra在有负权的情况下无法工作,Bellmon-Ford算法允许有负权。
(3)Dijkstra算法确定的是两点之间的最短路,而Bellmon-Ford算法确定的是单源到其他点的最短路。
(4)Bellmon-Ford算法可以用来判定是否有负权环。