Dijkstra算法
Dijkstra算法
fengsehng 发表于1年前
Dijkstra算法
  • 发表于 1年前
  • 阅读 6
  • 收藏 1
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

算法描述

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

步骤

a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则{u,v}正常有权值,若u不是v的出边邻接点,则{u,v}权值为∞。

b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

执行动画:

这里写图片描述

具体的实例:

这里写图片描述

实例的步骤:

这里写图片描述
参考:
july的博客:
http://blog.csdn.net/v_JULY_v/article/details/6096981
其他:
http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

共有 人打赏支持
粉丝 4
博文 284
码字总数 214494
×
fengsehng
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: