首页 > 笔记 > Prim算法与Dijsktra算法的异同

Prim算法与Dijsktra算法的异同

写完最小生成树与最短路,大脑一片混乱。。。尤其是prim与dijsktra。。。理了一晚上才出来。。。

先回顾一下

Dijsktra:求单源最短路

Prim:求最小生成树

【通过找不同,两个伪算法的差别只在于最后循环体内的松弛操作。

最小生成树只关心所有边的和最小,所以有v.key = w(u, v),即每个点直连其他点的最小值(最多只有两个节点之间的权值和)

最短路径树只搜索权值最小,所以有v.key = w(u, v) + u.key,即每个点到其他点的最小值(最少是两个节之间的权值和)

简单总结就是,Dijkstra的松弛操作加上了到起点的距离,而Prim只有相邻节点的权值。

思想

都是使用贪心和线性规划,每一步都是选择权值/花费最小的边。
贪心:一个局部最有解也是全局最优解;
线性规划:主问题包含n个子问题,而且其中有重叠的子问题。

Dijkstra算法通过线性规划缓存了最优子路径的解,每一步也通过贪心算法来选择最小的边。
Prim算法通过贪心来选择最小的边,而Prim的每个子树都是最小生成树说明满足线性规划的两个条件。

时间复杂度

Time = θ( V * T1 + E * T2)
其中T1为取出键值最小点的时间,T2为降低键值的时间,取决于数据结构。

数组
T1= O(V), T2 = O(1), TIME = O(V * V + E) = O(V * V)
二叉堆
T1 = O(lgV), T2 = O(lgV), TIME = O(V * lgV + E * lgV)
斐波那契堆
T1 = O(lgV), T2 = O(1), TIME = O(V * lgV + E) = O(V * lgV)
对于稀疏图来说,E远小于V*V,所以二叉堆比较好;
而对于密集图来说,E=V*V,所以数组比较好;
斐波那契堆是最好的情况。

 


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×