文档章节

Dijkstra算法

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 437
阅读 10
收藏 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面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
荷兰资格最老的程序员告诉你,如何用短短20分钟影响整个20世纪

  保持对同一个问题的思考   在那一个瞬间找到了答案   一个既是贪心又是最优的最短路径算法   1   人们总是在做一件事情:   找最短路径      公元前32世纪,苏美尔人在粘土...

超级数学建模
2018/01/23
0
0
图——图的Dijkstra法最短路径实现

1,最短路径的概念: 1,从有向图中某一顶点(起始顶点)到达另一顶点(终止顶点)的路径中,其权值之和最小的路径; 2,问题的提法: 1,给定一个带权有向图 G 与起始顶点 v,求从 v 到 G ...

子宇24
05/26
0
0
Dijkstra算法|单源最短路径|贪心算法

单愿最短路径描述:给定带权有向图G=(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称之为源(origin)。现在要计算从源到其他各顶点的最短路径的长度。这里的路径长度指的是到...

掬一捧
2012/09/26
1K
0
1.1.1最短路(Floyd、Dijstra、BellmanFord)

转载自hr_whisper大佬的博客 一、Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。 使用邻...

fire_to_cheat_
2018/03/04
0
0
像名字一样容易忘记的Dijkstra

Dijkstra算法是经典的求解一个顶点到其他顶点的最短距离的算法。每次学习的时候总是觉得思路简单明了,但每当要用到时,就忘记了实现的细节。归根结底还是应用的少。相信做地图导航的应该对其...

dugangabc
2016/02/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

64.监控平台介绍 安装zabbix 忘记admin密码

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍: 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111
今天
9
0
当餐饮遇上大数据,嗯真香!

之前去开了一场会,主题是「餐饮领袖新零售峰会」。认真听完了餐饮前辈和新秀们的分享,觉得获益匪浅,把脑子里的核心纪要整理了一下,今天和大家做一个简单的分享,欢迎感兴趣的小伙伴一起交...

数澜科技
今天
7
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

本文作者:PETER LAI ,是 Diode 的区块链工程师。在进入软件开发领域之前,他主要是在做工商管理相关工作。Peter Lai 也是一位活跃的开源贡献者。目前,他正在与 Diode 团队一起开发基于区块...

红薯
今天
6
0
CC攻击带来的危害我们该如何防御?

随着网络的发展带给我们很多的便利,但是同时也带给我们一些网站安全问题,网络攻击就是常见的网站安全问题。其中作为站长最常见的就是CC攻击,CC攻击是网络攻击方式的一种,是一种比较常见的...

云漫网络Ruan
今天
11
0
实验分析性专业硕士提纲撰写要点

为什么您需要研究论文的提纲? 首先当您进行研究时,您需要聚集许多信息和想法,研究论文提纲可以较好地组织你的想法, 了解您研究资料的流畅度和程度。确保你写作时不会错过任何重要资料以此...

论文辅导员
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部