Prim算法和迪杰斯特拉算法的区别是什么

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

相关推荐

异步编程是一种编程模式,用于处理可能会花费较长时间的操作,而不会阻塞其他代码的执行。在同步编程中,代码会按照顺序一步一步执行,每个操作的完成都会等待前一个操作完成后才继续执行。这样的执行方式可能会导致程序在等待某些操作完成时出现阻塞,影响用户界面的响应性或导致整个程序的执行速度变慢。异步编程通过将长时间运行的操作(如网络请求、文件读取、数据库查询等)放置在后台,不会阻塞主线程的执行。在进行异步编程时,可以在发起异步操作后继续执行后续的代码,而不需要等待异步操作完成。💦当异步操作完成时,系统会通知相应的回调函数或执行注册的事件处理程序,以便使用异步操作的结果继续处理。💢常见的异步编程模式和技术包括:https://www.nowcoder.com/issue/tutorial?zhuanlanId=Mg58Em&uuid=aa2d7fa706914dfc9afef6476efb3004🔼回调(Callback): 将一个函数作为参数传递给异步操作,并在操作完成时调用该函数。这是一种传统的异步编程模式,但它容易造成回调地狱(callback hell)的问题,即多层嵌套的回调函数,难以维护和阅读。🔼Promise: Promise 是一种表示异步操作的对象,可以在异步操作完成后进行处理。使用 Promise,可以链式地调用 then() 方法来处理成功的结果,以及 catch() 方法来处理失败的情况,避免了回调地狱问题。🔼Async/await: Async/await 是基于 Promise 的语法糖,它提供了更加简洁和易读的方式来处理异步操作。通过使用 async 关键字声明一个函数,并在其中使用 await 关键字等待异步操作的结果,可以以同步的方式编写异步代码。异步编程使我们能够更好地处理网络请求、文件读写、数据库操作等耗时任务,同时保持应用程序或系统的响应性。它对于处理事件驱动的操作和并发任务非常有用,提高了代码的性能和可维护性。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务