很多同学在学习完Prim算法和Dikstra算法后,都会感觉这两个算法相似度极高。
两个算法都是图论中的经典算法:Prim算法和Dijkstra算法都是解决图论中特定问题的经典算法,在计算机科学和工程领域有广泛应用。两者都使用了贪心策略:两种算法都采用了贪心策略,即每一步都选择当前状态下的最优解,以期望达到全局最优。
在图论中,Prim算法解决的问题是连通无向有权图中最小生成树问题,常用于网络设计、电路设计等需要构建最小成本树的场景。而Dikstra算法解决的问题是源点到目标点的最短路径问题,更多用于地图导航、路由选择等需要找出单源最短路径的场景。
虽然这两个算法在添加新结点时,都是选择“距离最短"的结点加入集合,但是Prim算法中,“距离最短”是指未访问的结点到已经访问的所有结点距离最小,即将已经访问的结点视为一个整体,将距离最小的结点加入到已访问的集合中;而在Dikstra算法中,“距离最短"是指所有未访问结点(通过已访问的结点)到源点距离最小。
在Prim算法中,数组元素dis[表示未访问结点i到已访问结点集合的最短距离,所以此时需要len记录最短距离。而Dikstra算法中,数组元素dis[i]表示未访问结点i到源点的最短距离。
综上所述,Prim算法和Dijkstra算法虽然都是基于贪心策略的图论算法,但它们在解决的问题、选择节点的标准、时间复杂度以及应用场景等方面存在显著差异。