dat59 |dijk小根堆 和 bellman

在 dijk 求最小路径的过程中我们每次会选择离集合最近的一个点加入进去,并且更新和这个点相连的所有距离。

  • 一个优化方法是在我们维持一个小根堆表示离集合最近的点,
  • 取出最近的点,然后将更新后的距离重新加入的小根堆里面
  • 一个问题就是一个点对应的不同距离会重复加入到小根堆中,我们通过 visited 数组进行判断过滤。

bellman 算法

  • 维护的是一个边集合
  • 我们从 1 号点出发,遍历边集合内的所有边,更新点的所有距离mindist
  • 由于边给的顺序不同,理论上来说最完美的顺序可以一次得到最短距离,而最差我们可以得到所有和 1 号点相连一条边的最短距离
  • 我们距离 n 号点共有n-1条边,也就是无论如何我们只要遍历 n 次所有集合的边就必定能得到最短距离
  • 一个剪枝操作就是当我们遍历所有边都没有进行更新操作的时候可以及时跳出
  • 时间复杂度是n*e
全部评论

相关推荐

面试流程:一面 群名二面  25min1、介绍一下项目,你负责了哪些部分2、说一下项目的亮点和难点3、java的特性,什么是继承和多态,是单继承还是多继承4、有用过泛型吗,讲一下5、什么是反射,有用过吗6、springboot的常用注解7、springboot相比spring的优势8、系统里怎么使用mysql的->spring data jpa9、在做项目中遇到很复杂的需求怎么办10、平时有遇到过经常加班的情况吗,怎么平衡的11、反问美的三面 15min(感觉二面就是HR面了?)1、自我介绍2、说一下你的项目3、说一下项目开发的流程4、聊天5、反问#美的集团2025届校园招聘【企业介绍】集智能家居、楼宇科技、工业技术、机器人与自动化和创新型业务五大业务板块为一体的全球化科技集团,世界五百强企业【招聘岗位】涵盖信息技术、研发技术、财务金融、管理等八大职业群,海量岗位任您选择【招聘对象】2025届高校应届毕业生国内本硕毕业时间:2024.9.1-2025.8.31国内外博士毕业时间:2024.1.1-2025.12.31【工作地点】佛山、合肥、上海、广州、深圳等40+海内外城市【投递链接】https://careers.midea.com/【专属内推】M100004(内部推荐→选择mvp推荐→填写:M100004,简历优先筛选,后续有疑问或者流程问题欢迎随时联系)使用内推码简历优先筛选,有任何问题包括进度查询可以私信我,内推后在评论区留言【姓名缩写+岗位】,方便捞人和确认投递状态
美的集团
|
校招
|
超多精选岗位
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务