普里姆迪杰斯特拉克鲁斯卡尔弗洛伊德比较

《普里姆迪杰斯特拉克鲁斯卡尔弗洛伊德比较》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一、Prim算法与Dijkstra算法：1、相同：1）都利用了顶点集Ｕ和Ｖ－Ｕ中顶点的最小值；2）都有一出发点；3）每次都是选出最小的值并入Ｕ中以作为过渡顶点，而不再求其最小；4）都涉及最短问题；5）它们都是从一个原始顶点开始将顶点一个个按一定顺序转移到所求终点中。6）都用到了辅助向量；7）都从顶点出发，并在过程中都依据了顶点；8）都包含其顶点连通分量；9）都是对网进行操作；10）用找到的路径将顶点连接起来都是树；2、相异：1）普里姆算法从顶点集U中任一顶点出发到V—U中顶点，迪杰斯特拉算法从源点出发通过顶

2、点Ｕ到找到Ｖ—Ｕ中顶点的最小值；2）普里姆算法的出发点是算法的开始点；而迪杰斯特拉算法的出发点是求最短路径的源点；3）普里姆算法用lowcost数组，而迪杰斯特拉算法用Ｄ[j]=Min{D[i]vi属于顶点集Ｖ－Ｓ}4）普里姆算法解决最小生成树，迪杰斯特拉算法解决最短路径；5）普里姆算法是顺着已找到的顶点找其余应并入Ｕ中的顶点，而迪杰斯特拉算法是顺着顶点去找其余顶点到源点的最短路径；6）普里姆算法的最短是两个顶点集间的最短，而迪杰斯特拉算法的最短是某点通过一个顶点集Ｕ到源点的最短。7）普里姆算法的最短是两个

3、顶点间的最短，而迪杰斯特拉算法的最短是某点到源点的最短。8）普法无需按最短的并入，它寻找并入U的点的依据是在U和V-U之间的最短路径。9）迪法在找到最短路径后，还要对其余结点的当前最短路径进行修改，而普法则不进行修改。10）普法是从顶点集的思路出发，而迪法则是按路径长度递增思路出发。11）普法的出发点是任意的，而迪法的出发点是规定的。12）普法在执行过程中不改变两点间的权值，而迪法在执行过程中会求出一个或者是两点的权值或者是权值之和作为最短的路径；13）迪法具有方向性，而普法则可以不具有；14）二、Prim

4、算法与Krukal算法：1、相同：1）都是找最小生成树的方法；2）都用到了ＭＳＴ性质；3）算法执行前都把n个结点看成是n棵树，而算法完成后，都成为了一棵树。4）两者找到的边都要求在不同的连通分量上。5）最终得到的最小生成树应该是一样的，而且都是n个结点,n-1条边。2、相异：1）普里姆算法从顶点出发，克法从边出发；2）普法求Ｕ与Ｖ－Ｕ之间任两顶点的最短；而克法是求任两不同连通分量之间的最短；3）普法在执行过程中只有一棵结点个数大于1的树，而克法则可能有多棵结点个数大于1的数。4）普法适用于边稠密的网，而克法

5、适用于边稀疏的网。5）普法的时间复杂度与边的数目无关是O(n2)，而克法的时间复杂度与时间有关是：O(eloge)二、Dijkstra算法与Floyd算法：1、相同：1）是按路径长度递增的思路进行查找最短路径。2）都需要借助带权领接矩阵；3）都引进了辅助数组；4）弗法的替代算法是N次调用迪法；2、相异：1）迪杰斯特拉算法是从一点出发到其余路径的最短路径，而弗法是找图中所有顶点间的最短路径；2）迪杰斯特拉算法是找到最短后再尝试利用该最短辅助找其余最短的；而弗法是在插入第i-1个顶点的基础上比较插入第i个后和之

6、前的最短。3）路径长度递增不一样：迪法增的路径是比较出最短的增，而弗法增的路径是按编号递增。4）迪法从源点出发，而弗法可以从任意点出发；5）结果不同，迪法找到的是从源点到其余顶点的最短路径；弗法则是任两点之间的最短路径。