文档章节

最短路径之Dijkstra算法

孟飞阳
 孟飞阳
发布于 2017/05/12 19:23
字数 1189
阅读 25
收藏 0

今天为大家分享的算法是为解决最短路径算法的Dijkstra算法(简称D算法),这是一个解决从点到点之间最短路径的问题,看下面这张图:

每天一个算法——最短路径之Dijkstra算法

这里,我们想要得出节点a(节点1)到节点b(节点5)的最短路径,就是怎么走可以使得权重值的和最小,每一条边都有一个权重。

今天我们介绍的D算法就是解决这类问题的,这是一种贪心算法,每次只取权重和最小的点,通过不断加入节点,来更新源节点a到各个节点的最短路径,直到所有节点遍历完。

算法步骤:

1、定义,遍历过的节点集合为S,集合U为其余节点(即未遍历)。初始时,S只包含源点v,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点}。若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

注:这里集合S、U,是为了判断哪些节点已经遍历过,如果U为空了,就不继续执行。

2、从集合U中选取一个距离v最小的顶点k,把k加入到S中。

3、以k为新考虑的中间点,修改v到U中各顶点的距离;若从源点v到顶点w的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改v到w的距离值。

例子:

每天一个算法——最短路径之Dijkstra算法

4、重复步骤2、3直到所有顶点都包含在S中。

上面就是D算法的处理步骤,可能大家第一次看和我一样很迷茫,不要紧,我们结合上面这个图,使用D算法来详细介绍每个步骤:

1、初始化步骤

用一个一维数组DIS来表示节点1到各个节点的最短路径(即权重),没有连线的用∞表示。除此之外,为了防止节点重复计算,我们把节点分成两组,一组已经遍历的节点集合S,另一组还没遍历集合U。初始化的时候,节点1在集合S中。

每天一个算法——最短路径之Dijkstra算法

注:节点1到自己的权重为0。

2、从集合U中获取离节点1最近的点(参考U在数组中的最小值,是节点2),加入到集合S,并重新计算DIS数组。

(1)节点2有到节点3和4的边,所以数组DIS的3和4位置的值可能会变动。

(2)2到3的权重为10,所以1到3的权重为17(7+10),17大于9,所以不用变动。

(3)3到4的权重为15,所以1到4的权重为22(7+15),22小于无穷,所以DIS[4]=22。(这里数组角标大家注意下,DIS[4]表示第四个位置,起始位置为1)

每天一个算法——最短路径之Dijkstra算法

3、重复步骤2,获取U里面距离最近的点(这里为节点3),重新计算DIS数组。

(1)节点3这里和4、6有边,所以DIS的位置4、6可能需要修改值。(节点2在S中,只考虑U中没遍历过的节点)。

(2)3到4的权重为11,所以1到4的权重为20(9+11),小于22(DIS[4]),所以DIS[4]=20。

(3)3到6的权重为2,所以1到6的权重为11(9+2),小于14(DIS[6]),所以DIS[6]=11。

每天一个算法——最短路径之Dijkstra算法

4、重复步骤2,取节点6加入S,重新计算DIS。

节点6只有到5的边了,所以只修改DIS[6]的值。这里节点1到节点5的权重为20(11+9),小于无穷(DIS[5]),所以DIS[5]=20。

每天一个算法——最短路径之Dijkstra算法

5、继续重复。

这次获取到节点4,从DIS数组可以知道1到4的权重(20)已经大于等于1到5的权重(20),所以无论如何也无法从节点4取到权重更小的路径了,所以可以舍弃(D算法是无法解决负权重问题,所以图的权重必须为正)。

 

由于节点1到节点5没有边连接,所以权重为无穷,大于20。所以,算法的最终结果就是:

每天一个算法——最短路径之Dijkstra算法

节点1到节点5的最短路径是20,

顺序是1->3->6->5。

有了算法,必须要有代码才有说服力,这里我用C语言实现了D算法的代码,大家有兴趣慢慢看,慢慢研究。我贴的是部分代码,其他不重要代码省略。

预定义变量:

每天一个算法——最短路径之Dijkstra算法

数据初始化:

每天一个算法——最短路径之Dijkstra算法

D算法具体逻辑方法:

每天一个算法——最短路径之Dijkstra算法

运行结果:

每天一个算法——最短路径之Dijkstra算法

本文转载自:极客码农

孟飞阳
粉丝 217
博文 1057
码字总数 566384
作品 5
朝阳
个人站长
私信 提问
图——图的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
Dijkstra算法--单源最短路径

在http://blog.csdn.net/hackerzhidian/article/details/54898064这一篇博客中总结了一下在求图的最短路中的一个算法-Floyd算法,Floyd算法用于求图的多源最短路径(多源最短路径:图的所有顶...

Hacker_ZhiDian
2017/02/07
0
0
数学:Dijkstra算法

一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的...

pricker
2015/09/12
125
0
加权有向图----单点最短路径问题(Dijkstra算法)

单点最短路径问题是求解从s到给定顶点v之间总权重最小的那条路径的问题。Dijkstra算法可以解决边的权重非负的最短路径问题。 Dijkstra算法无法判断含负权边的图的最短路径,但Bellman-Ford算...

Superheros
2017/12/21
8
0

没有更多内容

加载失败,请刷新页面

加载更多

JMM内存模型(一)&volatile关键字的可见性

在说这个之前,我想先说一下计算机的内存模型: CPU在执行的时候,肯定要有数据,而数据在内存中放着呢,这里的内存就是计算机的物理内存,刚开始还好,但是随着技术的发展,CPU处理的速度越...

走向人生巅峰的大路
18分钟前
40
0
你对AJAX认知有多少(2)?

接着昨日内容,我们几天继续探讨ajax的相关知识点 提到ajax下面几个问题又是必须要了解的啦~~~ 8、在浏览器端如何得到服务器端响应的XML数据。 通过XMLHttpRequest对象的responseXMl属性 9、 ...

理性思考
27分钟前
4
0
正则表达式基础(一)

1.转义 转义的作用: 当某个字符在表达式中具有特殊含义,例如字符串引号中出现了引号,为了可以使用这些字符本身,而不是使用其在表达式中的特殊含义,则需要通过转义符“\”来构建该字符转...

清自以敬
30分钟前
4
0
idea中@Data标签getset不起作用

背景:换电脑以后在idea中有@data注解都不生效 解决办法:idea装个插件 https://blog.csdn.net/seapeak007/article/details/72911529...

栾小糖
35分钟前
4
0
Apache Kudu 不能删除不存在的数据

使用Apache Kudu客户端,对KafkaConnect Sink 进行扩展。 使用的Apache Kudu 的Java 客户端。突然有天发现作业无法提交,一直报错。 后来才发现这是Kudu自身的一种校验机制。为了忽略这种校验...

吐槽的达达仔
46分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部