漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

栏目: 编程工具 · 发布时间: 5年前

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

作者小灰, 本文经授权转载自 程序员 小灰(ID:chengxuyuanxiaohui)。

在《 漫画:图的 “最短路径” 问题 》一文中小灰介绍了单源最短路径算法 Dijkstra。当时 漫画中我们遗留了一个问题: 如何求得最短路径的详细节点,而不仅仅是距离? —— 在本篇中,我们将会给与解答。

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

我们仍然以下面这个带权图为例,找出从顶点A到顶点G的最短距离。

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

详细过程如下:

第1步,创建距离表和前置顶点表。

距离表的Key是顶点名称,Value是从起点A到对应顶点的已知最短距离,默认为无穷大;前置顶点表的Key是 顶点名称,Value是从起点A到对应顶点的已知最短路径的前置定点。

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第2步,遍历起点A,找到起点A的邻接顶点B和C。从A到B的距离是5,从A到C的距离是2。把这一信息刷新到距离表当中。

同时,顶点B、C的前置顶点都是A,顶点A在邻接表中下标是0,所以把前置顶点表的B、C值更新为0:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第3步,从距离表中找到从A出发距离最短的点,也就是顶点C。

第4步,遍历顶点C,找到顶点C的邻接顶点D和F(A已经遍历过,不需要考虑)。从C到D的距离是6,所以A到D的距离是2+6=8;从C到F的距离是8,所以从A到F的距离是2+8=10。把这一信息刷新到表中。

同时,顶点D、F的前置顶点都是C,顶点C在邻接表中下标是2,所以把前置顶点表的D、F值更新为2:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

接下来重复第3步、第4步所做的操作:

第5步,也就是第3步的重复,从距离表中找到从A出发距离最短的点(C已经遍历过,不需要考虑),也就是顶点B。

第6步,也就是第4步的重复,遍历顶点B,找到顶点B的邻接顶点D和E(A已经遍历过,不需要考虑)。从B到D的距离是1,所以A到D的距离是5+1=6, 小于距离表中的8 ;从B到E的距离是6,所以从A到E的距离是5+6=11。把这一信息刷新到表中。

同时,顶点D、E的前置顶点都是B,顶点B在邻接表中下标是1,所以把前置顶点表的D、E值更新为1:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第7步,从距离表中找到从A出发距离最短的点(B和C不用考虑),也就是顶点D。

第8步,遍历顶点D,找到顶点D的邻接顶点E和F。从D到E的距离是1,所以A到E的距离是6+1=7, 小于距离表中的11 ;从D到F的距离是2,所以从A到F的距离是6+2=8, 小于距离表中的10 。把这一信息刷新到表中。

同时,顶点E、F的前置顶点都是D,顶点D在邻接表中下标是3,所以把前置顶点表的E、F值更新为3:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第9步,从距离表中找到从A出发距离最短的点,也就是顶点E。

第10步,遍历顶点E,找到顶点E的邻接顶点G。从E到G的距离是7,所以A到G的距离是7+7=14。把这一信息刷新到表中。

同时,顶点G的前置顶点是E,顶点E在邻接表中下标是4,所以把前置顶点表的G值更新为4:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第11步,从距离表中找到从A出发距离最短的点,也就是顶点F。

第12步,遍历顶点F,找到顶点F的邻接顶点G。从F到G的距离是3,所以A到G的距离是8+3=11, 小于距离表中的14 。把这一信息刷新到表中:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

就这样,除终点以外的全部顶点都已经遍历完毕,距离表中存储的是从起点A到所有顶点的最短距离,而前置定点存储的是从起点A到所有顶点最短路径的前置顶点。

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

如何把前置顶点表“翻译”成图的最短路径呢? 我们可以使用回溯法,自后向前回溯:

第1步,找到图的终点G,它是最短路径的终点:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第2步,通过前置定点表找到顶点G对应的前置下标5,在顶点数组中找到下标5对应的顶点F,它是顶点G的前置顶点:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第3步,通过前置定点表找到顶点F对应的前置下标3,在顶点数组中找到下标3对应的顶点D,它是顶点F的前置顶点:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第4步,通过前置定点表找到顶点D对应的前置下标1,在顶点数组中找到下标1对应的顶点B,它是顶点D的前置顶点:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

第5步,通过前置定点表找到顶点B对应的前置下标0,在顶点数组中找到下标0对应的顶点A,它是顶点B的前置顶点:

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

如此一来,我们把前置顶点表(0,0,1,3,3,5)转化成了最短路径(A-B-D-F-G)。

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

代码中,距离表和前置顶点表都是采用数组存储,这样比较方便。

输出最短路径的时候,代码中采用了递归的方式进行回溯。

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

作为码一代,想教码二代却无从下手:

听说少儿编程很火,可它有哪些好处呢?

孩子多大开始学习比较好呢?又该如何学习呢?

最新的编程教育政策又有哪些呢?

下面给大家介绍CSDN新成员: 极客宝宝(ID: geek_baby)

戳他了解更多↓↓↓

漫画:数据结构之最短路径 Dijkstra 算法的优化 | 技术头条

 热 文推 荐 

  杨镭访谈:UCloud 的技术价值观

JavaScript 中的垃圾回收和内存泄露如何处理?| 技术头条

☞ 19 岁当老板,20 岁 ICO 失败,编程少年的创业辛酸史

☞ 养生 996 的崛起:马云竟给他最痛恨的「兔子」站台?

☞ 打开阿兹海默之门:华裔张复伦利用RNN成功解码脑电波,合成语音 | Nature

☞ 澳洲生活7年, 前阿里程序员谈我们的区块链差距究竟在哪?

☞ 关于谷歌云,你应该知道的一切!| 技术头条

☞ 她说:为啥程序员都特想要机械键盘?这答案我服!

System.out.println("点个在看吧!");
console.log("点个在看吧!");
print("点个在看吧!");
printf("点个在看吧!\n");
cout << "点个在看吧!" << endl;
Console.WriteLine("点个在看吧!");
Response.Write("点个在看吧!");
alert("点个在看吧!")
echo "点个在看吧!"

你点的每个“在看”,我都认真当成了喜欢


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Linux程序设计

Linux程序设计

马修 / 陈健 / 人民邮电出版社 / 2007-7 / 89.00元

《Linux 程序设计(第3版)》讲述在Linux系统及其他UNIX风格的操作系统上进行的程序开发,主要内容包括标准Linux C语言函数库和由不同的Linux或UNIX标准指定的各种工具的使用方法,大多数标准Linux开发工具的使用方法,通过DBM和MySQL数据库系统对Linux中的数据进行存储,为X视窗系统建立图形化用户界面等。《Linux 程序设计(第3版)》通过先介绍程序设计理论,再以适......一起来看看 《Linux程序设计》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

URL 编码/解码
URL 编码/解码

URL 编码/解码