2024-09-27 00:22 成都理工大学 Java 发布于四川
关注
Prim算法和迪杰斯特拉算法的区别是什么
首先就是说一下我自己觉得很相似的地方，这也是我经常想着想着就搞混的原因：
这两个算法都是确定了起点，然后根据起点再去更新对应的dist数组，更新完后又去找dist的最小值（minn）对应节点，这个相当于初始化部分
，之后利用来更新dist数组的点都不叫做起点了。然后又去找minn值对应节点，再更新，这里其实是重复初始化部分，不过为了原来起点的说法，又多写了一点。
因为上面描述的过程就是两个算法的第一步骤，重合度很大，然后总是想着这个又跳到另一部分去了
现在来讲区别啦：
dist数组在Prim中可以理解成是到最小生成树的距离，没有被加入的点dist的值在一开始都应被设为自定义的无穷大值，而每有一个点假设为A被加入生成树中，那么A的邻接点B，C，D都可能会因为边权值小于到生成树的距离而被更新，
Dijisktra算法中dist指的是起点到各点的最短距离，它的更新契机是在，当加入顶点的dist值与它邻接点的边权值之和小与邻接点对应的dist值，而且这时候更新后会记录path数组。
其实最重要的就是理解dist的值，然后明白什么时候去更新dist数组，另外就是dijisktra多了一个path数组去维护 #算法#
这两个算法都是确定了起点，然后根据起点再去更新对应的dist数组，更新完后又去找dist的最小值（minn）对应节点，这个相当于初始化部分
，之后利用来更新dist数组的点都不叫做起点了。然后又去找minn值对应节点，再更新，这里其实是重复初始化部分，不过为了原来起点的说法，又多写了一点。因为上面描述的过程就是两个算法的第一步骤，重合度很大，然后总是想着这个又跳到另一部分去了
现在来讲区别啦：
dist数组在Prim中可以理解成是到最小生成树的距离，没有被加入的点dist的值在一开始都应被设为自定义的无穷大值，而每有一个点假设为A被加入生成树中，那么A的邻接点B，C，D都可能会因为边权值小于到生成树的距离而被更新，Dijisktra算法中dist指的是起点到各点的最短距离，它的更新契机是在，当加入顶点的dist值与它邻接点的边权值之和小与邻接点对应的dist值，而且这时候更新后会记录path数组。其实最重要的就是理解dist的值，然后明白什么时候去更新dist数组，另外就是dijisktra多了一个path数组去维护
#算法# 全部评论
相关推荐
查看30道真题和解析