bat365手机版app
首页 / bat365官网登录

dijkstra算法答题进程

迪杰斯特拉算法用来处理从极点v0出发到其他极点的最短途径,该算法依照最短途径长度递加的次序发生所以最短途径。

关于图G=(V,E),将图中的极点分红两组:

第一组S:已求出的最短途径的结尾调集(开端为{v0})。

第二组V-S:没有求出最短途径的结尾调集(开端为V-{v0}的悉数结点)。

算法将按最短途径长度的递加次序逐一将第二组的极点参加到第一组中,直到一切极点都被参加到第一组极点集S停止。

Dijkstra算法选用的是一种贪心的战略,声明一个数组dis来保存源点到各个极点的最短间隔和一个保存现已找到了最短途径的极点的调集:T,初始时,原点 s 的途径权重被赋为 0 (dis[s] = 0)。若关于极点 s 存在能直接抵达的边(s,m),则把dis[m]设为w(s, m),一起把一切其他(s不能直接抵达的)极点的途径长度设为无穷大。初始时,调集T只要极点s,最终从dis数组挑选最小值,则该值便是源点s到该值对应的极点的最短途径,而且把该点参加到T中,OK,此刻完结一个极点,然后,咱们应该看看新参加的极点是不是可以抵达其他极点而且看看经过该极点抵达其他点的途径长度是否比源点直接抵达短,如果是,那么就替换这些极点在dis中的值。

然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的一切极点。

版权说明:
1.版权归本网站或原作者所有;
2.未经本网或原作者允许不得转载本文内容,否则将视为侵权;
3.转载或者引用本文内容请注明来源及原作者;
4.对于不遵守此声明或者其他违法使用本文内容者,本人依法保留追究权等。
留言
访客
搜索
热门标签
最新留言
  • 暂无
  • 暂无
  • 暂无
  • 暂无
  • 暂无
  • 暂无
关注我们
关注我们
微信
关注我们
微博
bat365手机版app

Powered ByZ-Blog. Copyright Your WebSite.Some Rights Reserved.