prim算法(prim算法构造最小生成树)

Dijkstra算法与Prim算法的异同

Dijkstra算法用于构建 单源点的最短路径树 (MST)——即树中某个点到任何其他点的距离都是最短的。

例如，构建地图应用时查找自己的坐标离某个地标的最短距离。

可以用于有向图，但是 不能存在负权值 (Bellman-Ford可以处理负权值)。

Prim算法用于构建 最小生成树 ——即树中所有边的权值之和最小。

例如，构建电路板，使所有边的和花费最少。

只能用于 无向图 。

/
/
无向图G, 权值w, 起始点r MST(G, w, r) { for each u in G,V { /
/
此处做初始化操作，给每个节点u赋键值+∞，设置空为父节点 u.key = +∞ u.parent = NULL } /
/
选初始点r，Q是无向图G中所有点V的权值优先队列，key可看作u到下一个节点v的距离 r.key = 0 Q = G,V while(Q != ∅
) ｛ /
/
取出Q中权值最小值的点u u = extractMin(Q) /
/
取点u连接的所有节点(即无向图G的邻接表中的第u个链表) for each v ∈ G.Adj[u] { if (v ∈ Q) and (w(u, v) <
key) { /
/
若该节点仍在Q中且权值w(w,v)小于其原始权值，则进行松弛操作！ v.parent = u v.key = w(u, v) } } } }。

Prim和Dijkstra算法的区别

在图论中，Prim算法是计算最小生成树的算法，而Dijkstra算法是计算最短路径的算法。

二者看起来比较类似，因为假设全部顶点的集合是V，已经被挑选出来的点的集合是U，那么二者都是从集合V-U中不断的挑选权值最低的点加入U，那么二者是否等价呢？也就是说是否Dijkstra也可以计算出最小生成树而Prim也可以计算出从第一个顶点v0到其他点的最短路径呢？答案是否定的，否则就不必有两个算法了。

二者的不同之处在于“权值最低”的定义不同，Prim的“权值最低”是相对于U中的任意一点而言的，也就是把U中的点看成一个整体，每次寻找V-U中跟U的距离最小（也就是跟U中任意一点的距离最小）的一点加入U；
而Dijkstra的“权值最低”是相对于v0而言的，也就是每次寻找V-U中跟v0的距离最小的一点加入U。

一个可以说明二者不等价的例子是有四个顶点(v0, v1, v2, v3)和四条边且边值定义为(v0, v1)=20, (v0, v2)=10, (v1, v3)=2, (v3, v2)=15的图，用Prim算法得到的最小生成树中v0跟v1是不直接相连的，也就是在最小生成树中v0v1的距离是v0->
v2->
v3->
v1的距离是27，而用Dijkstra算法得到的v0v1的距离是20，也就是二者直接连线的长度。

普里姆算法是什么?

在计算机科学中，普里姆(也称为Jarník'
s)算法是一种贪婪算法，它为加权的无向图找到一个最小生成树 。

相关简介：这意味着它找到边的一个子集，能够形成了一个包括所有顶点的树，其中在树中所有边的权重总和最小。

该算法通过从任意起始顶点开始一次给树增加一个顶点来操作，在每个步骤中添加从树到另一个顶点的花费最小的可能的连接。

该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后，后来在1957年被计算机科学家罗伯特·普里姆，以及在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。

因此，它有时也被称为Jarník算法,普里姆-jarník算法。

普里姆-迪克斯特拉算法或者DJP算法。

这个问题的其他众所周知的算法包括克鲁斯卡尔算法和 Borvka'
s算法。

这些算法在一个可能的非连通图中找到最小生成森林；
相比之下，普里姆算法最基本的形式只能在连通图中找到最小生成树。

然而，为图中的每个连通分量单独运行普里姆算法，也可以用于找到最小生成森林。

就渐近时间复杂度而言，这三种算法对于稀疏图来说速度相同，但比其他更复杂的算法慢。

然而，对于足够密集的图，普里姆算法可以在线性时间内运行，满足或改进其他算法的时间限制。

普里姆算法是什么？

普里姆(Prim)算法，和克鲁斯卡尔算法一样，是用来求加权连通图的最小生成树的算法。

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。

意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；
并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；
1959年，艾兹格·迪科斯彻再次发现了该算法。

因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

基本思想：对于图G而言，V是所有顶点的集合；
现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。

从所有uЄ
U，vЄ
(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。

如何利用循环不变式证明算法部分正确性

就是个思想，说明正确算法的循环过程中总是存在一个维持不变的特性，这个特性一直保持到循环结束乃至算法结束，这样就可以保证算法的正确了。

比方说插入排序，算法每次循环后，前n个数一定是排好序的（n为已经循环的次数）。

由于这个特性一直成。

prim算法

指的是最小生成树的一种算法么，和dijstra算法思想接近，但是第一步是先将权最小的边的两个点加入以确定set。

然后一步步从un set加入与这个集合距离最短的点,然后更新这个set到unset的每一点的最短距离，直到全部加入。