请稍候,载入中。。。
请稍候,载入中。。。
 
Prim算法和Dijkstra算法区别
[ 2024/7/5 21:22:00 | By: mingko ]
 

很多同学在学习完Prim算法和Dikstra算法后,都会感觉这两个算法相似度极高。 

两个算法都是图论中的经典算法:Prim算法和Dijkstra算法都是解决图论中特定问题的经典算法,在计算机科学和工程领域有广泛应用。两者都使用了贪心策略:两种算法都采用了贪心策略,即每一步都选择当前状态下的最优解,以期望达到全局最优。

 在图论中,Prim算法解决的问题是连通无向有权图中最小生成树问题,常用于网络设计、电路设计等需要构建最小成本树的场景。而Dikstra算法解决的问题是源点到目标点的最短路径问题,更多用于地图导航、路由选择等需要找出单源最短路径的场景。 

虽然这两个算法在添加新结点时,都是选择“距离最短"的结点加入集合,但是Prim算法中,“距离最短”是指未访问的结点到已经访问的所有结点距离最小,即将已经访问的结点视为一个整体,将距离最小的结点加入到已访问的集合中;而在Dikstra算法中,“距离最短"是指所有未访问结点(通过已访问的结点)到源点距离最小。 

Prim算法中,数组元素dis[表示未访问结点i到已访问结点集合的最短距离,所以此时需要len记录最短距离。而Dikstra算法中,数组元素dis[i]表示未访问结点i到源点的最短距离。 

综上所述,Prim算法和Dijkstra算法虽然都是基于贪心策略的图论算法,但它们在解决的问题、选择节点的标准、时间复杂度以及应用场景等方面存在显著差异。

 

发表评论:
请稍候,载入中。。。
 
 
:: 信 息 公 告 ::
请稍候,载入中。。。
:: 时 间 记 忆 ::
请稍候,载入中。。。
:: 最 新 日 志 ::
请稍候,载入中。。。
:: 最 新 评 论 ::
请稍候,载入中。。。
:: 最 新 留 言 ::
请稍候,载入中。。。
:: 用 户 登 入 ::
请稍候,载入中。。。
:: 友 情 链 接 ::
:: 日 志 搜 索 ::

请稍候,载入中。。。



 
Powered by Oblog.