综合编程

C++用Dijkstra(迪杰斯特拉)算法求最短路径,秒懂详解!

微信扫一扫,分享到朋友圈

C++用Dijkstra(迪杰斯特拉)算法求最短路径,秒懂详解!
0

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。下面这篇文章就给大家介绍关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的方法,下面来一起看看吧。

image

算法介绍

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

9693047-4e3847865e1a0b6c.png

image

算法思想

按路径长度递增次序产生算法:

把顶点集合V分成两组:

(1)S:已求出的顶点的集合(初始时只含有源点V0)

(2)V-S=T:尚未确定的顶点集合

将T中顶点按递增的次序加入到S中,保证:

(1)从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

(2)每个顶点对应一个距离值

S中顶点:从V0到此顶点的长度

T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

依据:可以证明V0到T中顶点Vk的,或是从V0到Vk的直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和

image

应用举例

(1)题目:编写一个校园导游程序,为来访的客人提供各种信息查询服务。

主要功能:1.设计学校的校园平面图,所含景点不少于10个:顶点表示景点,边表示路径等;

2.为客人提供图中任意景点相关信息的查询;

3.为客人提供图中任意景点的问路查询,即查询人以景点间的一条最短路径。

要求:1.设计一个主界面;

2.设计功能菜单,供用户选择

3.有一定的实用性。

image

(2)设计思路:

1、该题主要有算法思路以及程序的逻辑思路,首先从逻辑思路讲,进入程序,首先设计一个主菜单,选项有景点信息查询,最短路径查询以及显示景点的平面视图三个子菜单,然后根据用户的输入选择的子菜单前的编号,分进入不同的子菜单;该功能是由if….else if…. 语句实现。在景点信息查询和最短路径查询子菜单下还有二级子菜单,都是列 出所有景点并在前面编号,查询景点信息时,输入景点前面的编号即可,查询最短路径时,先输入起点的编号,再输入终点的编号。而显示景点视图则调用景点平面图函数即可显 示。

2、算法思路主要是迪杰斯特拉算法的思路,利用迪杰斯特拉算法求最短路径。

3、先定义好图的储存结构,本题采用邻接矩阵的方式来表示图,并在主函数中初始化该图;

image

4、定义三个全局一维数组,一个bool类型数组S[]用来记录从v0到vi是否已经确定了最短路径,是则记S[i]=true ,否记S[i]= flase;一个int 类型数组Path[]用来记录从v0到vi的当前最短路径上的vi的直接前驱顶点编号,若v 到vi之间有边则记Path[i] = v的编号,否则记Path[i] = -1;最后一个数组D[]用来记录从v0到vi之间的最短路径长度,存在则记v0到vi之间边的权值或者权值和,否则记为MAX

5、定义一个求最短路径的函数,传入的参数为图和起点,首先进行初始化工作,初始化S[]数组全为false,D[]数组初始化为起点到各个顶点的权值,Path[]数组初始化为起点是否与各顶点有边,有则记v0否则记-1;

6、然后进行n-1次for循环,找出vo到其余n-1个顶点之间的最短路径,比较当前D[]数组中最小值,找到最小值的编号v,该编号就是从v0出发到所有顶点中距离最短的顶点编号,然后把S[v]的值置为true。说明从v0出发到顶点v已经找到最短路径;

7、接着就要更新D[]数组,因为D[]数组是记录最短路径的,现在已经找到了一个顶点的最短路径,已该顶点v为中间点,判断从该顶点v出发到剩下的顶点的路径长度加上该点到v0的路径长度是否小于直接从v0出发到其余顶点的路径长度,如果小于,则更新D[i]为以该顶点v为中间点求得的路径长度。更新Path[i] = v;即i的前驱不再是v0而是v;

8、循环(6)(7)两步n-1次即可得到D[]数组,输出D[]数组既是v0到所有顶点的最短路径长度;

(3)源代码:

image

image

image

image

image

image

(4)运行截图:

image

image

image

总结

以上就是关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的全部内容了,希望本文的内容对大家的学习或者工作带来一定的帮助,如果有疑问大家可以留言交流。

阅读原文...

微信扫一扫,分享到朋友圈

C++用Dijkstra(迪杰斯特拉)算法求最短路径,秒懂详解!
0
简书

AI/数据产品经理需要了解的算法——商品推荐算法

上一篇

AVRoutePickerView

下一篇

评论已经被关闭。

插入图片

热门分类

往期推荐

C++用Dijkstra(迪杰斯特拉)算法求最短路径,秒懂详解!

长按储存图像,分享给朋友