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

算法介绍

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

算法思想

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

把顶点集合 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 的路径权值之和

应用举例

（1）题目：编写一个校园导游程序，为来访的客人提供各种信息查询服务。

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

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

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

要求：1. 设计一个主界面；

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

3. 有一定的实用性。

（2）设计思路：

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

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

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

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）源代码：

（4）运行截图：

总结

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