首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

最短路径dijkstra算法精品代码(超详解)

(图来自于参考资料2) 那么如何寻找?还是以上图为例: 1)初始化:设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数),且这些节点都没被处理过。 2)从源节点出发,更新相邻节点(图中为2,3,6)到源节点的距离。然后在所有节点中选择一个最短距离的点作为当前节点。 3)标记当前节点为done(表示已经被处理过),与步骤2类似,更新其相邻节点的距离。(这些相邻节点的距离更新也叫松弛,目的是让它们与源节点的距离最小。因为你是在当前最小距离的基础上进行更新的,由于当前节点到源节点的距离已经是最小的了,那么如果这些节点之前得到的距离比这个距离大的话,我们就更新它)。 4)步骤3做完以后,设置这个当前节点已被done,然后寻找下一个具有最小代价(cost)的点,作为新的当前节点,重复步骤3. 5)如果最后检测到目标节点时,其周围所有的节点都已被处理,那么目标节点与源节点的距离就是最小距离了。如果想看这个最小距离所经过的路径,可以回溯,前提是你在步骤3里面加入了当前节点的最优路径前驱节点信息。 看文字描述显得苍白无力,你可以结合上图,看下这个视频:http://v.youku.com/v_show/id_XMjQyOTY1NDQw.html (dijkstra演示),然后就清楚了。 我比较懒不想打字所以以上文字来源: 代码原创 http://www.cnblogs.com/wb-DarkHorse/archive/2013/03/12/2948467.html 下面代码是带路径的,其他的自己可以修改。

01
领券