首页 > 代码库 > dijkstra 算法 找图的最短路 单源最短路
dijkstra 算法 找图的最短路 单源最短路
基本思路是 一个path数组存路径 一个distance数组存距离 distance[k]表示 k结点到指定的初始结点的最短路 还要个collect数组收集已经被操作过的点
先初始化distance 把目标结点的子结点的距离放进去,其他的初始化为无穷大, 每次找d中未被收集到collection中的最小值,这是最重要的,有这步才能证明最后得到的是最短路,这步是贪心思想,每次找距离最小的未在collection里的结点来,保证最后得到的最小路径,这是被证明的,这步也保证了遍历所有的路径从而得到最小值,
具体体现在 比如 先对3结点操作,3结点到4结点来更新4的最短距离后,把3放进collect里 然后到5结点 它的子节点也有3 但是不用再去对3到5来更新5到目标点的最短距离了,因为5结点在后,它到目标点的距离必定比到3的距离大 而距离都是大于0的 所以不用去走这步了 所以必须要有 选最小这个思想 程序才对,所有路线才被考虑到,而且着步直接去掉了许多不用考虑的。 而且说明 有负值的 边权的图是不可以用这种算法的,因为找的最短路是错的,就是因为这儿。
dijkstra 算法 找图的最短路 单源最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。