基于Dijkstra算法的北京景点旅游路径规划研究

摘要：在如今的旅游行业中，提前规划好路线非常重要，即设计有效的最短路径十分关键，而Dijkstra 算法是解决最短路径问题的最优选择。文章针对北京景点的特征，基于Dijkstra 算法，研究其在北京景点路线规划中的应用，并且进一步对算法进行改进，不仅能节约成本，而且耗时最少，为旅游行业的进一步发展奠定基础。

关键词：旅游；Dijkstra 算法；最短路径；规划

中图分类号：TP311.5 文献标识码：A文章编号：1009-3044（2023）17-0036-03

0 引言

北京作为中国的首都和历史古都，景点非常丰富，很多景点都具有特定的地质地貌、生态环境，尤其是悠久的历史、灿烂的文化吸引了很多游客，是中国的优秀旅游城市。每年去北京旅游的游客不计其数，以2022年春节假期为例，北京景区累计接纳游客约758.3万人次，受新冠疫情影响，虽比2021年同比减少了2.9%，但比2020年增长3.6倍。面对如此巨大的游客数量，针对北京景点多、面积大、人流量大的特点，为了给游客更加舒适的体验，论文基于北京的几个著名景点，借助Dijkstra算法进行了旅游路线规划研究，能为智能旅游App的设计打下良好的基础。

1 Dijkstra 算法介绍

在城市交通问题中，如果想找到城市A和城市B之间一条中转次数最少的路线，即从顶点A到顶点B所含的边的数目最少的路径，只需要从顶点A出发对该图进行广度优先搜索遍历[1]，一旦遇到顶点B就可以停止，这是最简单的图的最短路径问题。但在很多情况下，还需要解决的问题是要找到城市之间的最短线路或者城市之间最节省的交通费用等问题，此时路径长度的度量就不再是路径上的数目，而是路径上的权值，即它所代表的相关信息，例如两个城市之间的距离或者途经所需的时间或者交通费用等，这类问题设计的都是最短路径问题。

例如从西安出发准备去北京、上海、兰州，该如何找到最佳的出行方案呢？也就是找到从西安出发到达三个目的城市的带权路径长度最短的那个路径方案。

最短路径问题一般分为两种情况：单源最短路径问题和每一对顶点之间的最短路径问题，常用的解决这两种问题的算法分别是迪杰斯特拉算法（Dijkstra）和弗洛伊德算法（Floyd）[2]，而解决旅游线路问题，主要是单源最短路径，主要应用Dijkstra算法。

2 Dijkstra 算法思想

Dijkstra算法是一种按照路径长度递增的次序，分别产生到各顶点最短路径的一种贪心算法，该算法把带权图中的所有顶点分成两个集合，S和V-S，S中存放已经找到最短路径的顶点，V-S中存放当前还没有找到最短路径的顶点[3]，算法将按照最短路径长度递增的顺序逐个将V-S集合中元素加入S集合中，直到所有的顶点都进入了S集合为止，其实这里用到一个很重要的定理，下一条最短路径或者弧即v0到vi，或者中间经过S集合中的某个顶点，而后到达vi的路径。这条定理可以用反证法来证明，假设下一条最短路径上有一个顶点vj是不在S集合中，即此路即为v0到vj再到vi，显然从v0到vj长度是小于v0到vj再到vi的长度，故下一条最短路径应该为v0到vj，这就与题设的下一条最短路径v0到vj再到vi是相矛盾的，所以下一条最短路径上不可能有不在S中的顶点vj，其中第一条最短路径是从源点v0到各点路径长度集合中长度最短的那一条。

3 Dijkstra 算法具体步骤

Dijkstra算法具体步骤如下：

第一步，对于网P=（V，E），将P中的顶点分为两组，S和V-S，其中S为已求出的最短路径的终点集合，初始时仅包含S1，V-S代表尚未求出的最短路径的顶点集合，S中各顶点之间的距离记为d，在顶点集合S中，如果存在弧，则S1到Si之间的距离d即其上的权值，否则记为无穷大[4]。

第二步，从V-S中选取一个最小距离，将其关联的顶点K 加入S 中，且d为S1 到k 的最短距离[5]。

第三步，以K作为新的基点，对S中各结点之间弧的权值进行调整，此时，如果源点S1经过顶点K到达顶点M的距离小于S1直达M的距离，那么就调整顶点M的弧权值，即d= d+ d。

第四步，依次类推，反复执行以上第二步和第三步，直到集合S中容纳了全部顶点[6]。

4 Dijkstra 算法在北京景点旅游线路规划中的应用

在基于Dijkstra算法对旅游线路进行规划时，通常采用图形结构来表示北京景点中的实际路径结构，本文选取了北京的7个著名景点作为研究对象，这些景点的旅游线路图如图1所示，其中每个景点均用代码表示，具体代码对照表如表1所示。

每个景点之间路线是互通的，各景点之间的距离信息如表2所示，以公里为单位。

以图1中的北京景点旅游线路图为例，运用Dijk⁃stra算法求得从天安门广场S1出发到其余各顶点的最短路径，具体过程如表3所示。

为了更好地记录整个求解过程，设置表格来记录，列代表每一次的求解过程，即每一条最短路径的产生，行代表单源点到达目标点，矩阵中的元素值来代表单源点到达目标点的路径长度，为了更好地记录这个路径，同时记录了路径上的顶点，比如在这个无向网中，以S1作为出发点，如果采用邻接矩阵进行存储，那么扫描S1所在的行，就可以知道S1直接相邻的顶点有哪些[7]，可以看到，有S2到S7，路径长度分别为5、20、7、79、48、10，显然第一次可以选择的就是5这条最短路径，对应的目标点就是S2，即第一条最短路径是从出发点S1到S2，路径长度为5，这条路径就是S1到S2的最短路径；接下来通过更新迭代来寻找第二条最短路径，根据刚刚介绍的基本思想，第二条最短路径要么来源于和S1直连的那些顶点，一条边，要么来自刚刚已经找到的从S1经过已求得的最短路径顶点S2，再到达目标点的两条边来组成，所以要来考查一下顶点S2，它可以邻接哪些顶点，扫描S2所在的行，除了S1，与S2直连的顶点有顶点S3到S7，其中S1通过S2中转到达S5的路径长度是5+71=76，比S1直达S5的路径长度短，所以要更新替换，替换路径为S1借助于S2到S5，路径长度为76，其他的不变，第二条最短路径就是在20、7、76、48、10这几个中进行选择，肯定选择7，所以找到第二条最短路径是从S1到S4，路径长度为7， 这条路径就是S1到S4的最短路径；继续找第三条最短路径，它或者还是从源点到某一个目标点直达的，或者是从源点经过已求得的最短路径的顶点S4再到达某个目标点的，因此要来考查顶点S4，除去S1和S2，发现S4直连出去的顶点有S3、S5、S6、S7，之前出发点S1到S5是经过S2中转的，路径长度为76，现在经过S4中转，路径长度只需要7+60=67，所以更新替换，另外之前出发点S1到S6是直达的48，现在经过S4中转只需要7+40=47，所以也更新替换，此时可以选择的路径长度有20、67、47、10，所以选择10这条，至此找到了第三条最短路径，从S1出发到S7，路径长度为10， 这条路径就是S1到S7的最短路径；接下来找第四条最短路径，考查顶点S7，发现没有通过S7中转可以缩短路径的顶点，此时路径长度就在20、67、47中选择了，所以选择20这一条，即找到第4条最短路径，S1到S3，路径长度为20，这条路径就是S1到S3的最短路径；接下来同理，第五条最短路径是S1经过S4中转，再到S6，路径长度47，最后一条，第六条最短路径是S1经过S4中转再到S5，路径长度是67，至此求得了出发点S1到其余6个顶点的带权最短路径长度了。

5 Dijkstra 算法改进

在对北京景点的路线进行规划而设计出最短路径时，结合北京部分景点的旅游线路图可以看出，图中的结点个数并不多，为了便于实现实际需求，可以对此算法进行改进，其改进的基本思想如下：假设以S1作为起始点，以S6作为终点的最短路径已经求出，其路径为S1-S4-S6，则如果需要寻求从结点S4出发到结点S6的最短路径时，那么就可以参照已经找到的S1到S6的最短路径直接求出S4到S6的最短路径为S4-S6，即不用重新使用Dijkstra算法求。所以在之前求S1到各顶点的最短路径过程中，要对之前求出的结果进行保存，这样才能通过已经存储的信息迅速得到从源点到目的点的最短路径[8]。改进后的Dijkstra算法流程图如图2所示，其中Ds为始点s到其他结点的距离，初始状态下为0；Fs表示从源点s到某一目的结点p的最短路径中的前一结点；Di表示检验从所有已标记的结点e到其他未标记的结点f的距离，w（e，f）表示从结点e到f的距离值。

6 结束语

论文基于Dijkstra算法对北京部分景点旅游路线进行了规划，首先通过Dijkstra算法得出了从源点到达各景点的最短路径，然后又对此算法进行改进，通过改进后的算法，能快速得出后续结点的最短路径，并给出了流程图，这样能提升旅游效率。论文建立的最短路径算法可应用于各行各业，尤其是在旅游行业中显得尤为突出，为了便于游客出行，提升旅游质量，找出高效率的旅游路线非常重要，这样才能节约旅游成本，耗费最短时间，使中国旅游行业高质量发展。

参考文献：

[1] 吴昕宇，罗雪颖.基于Dijkstra算法的旅游路线规划研究[J].数码世界，2019（7）：20-24.

[2] 刘洋洋.基于改进Dijkstra算法的自驾游最优路径规划研究[J].科学技术创新，2020（17）：75-77.

[3] 刘小玲.基于Dijkstras算法的主题公园游览路径规划研究[J].数字技术与应用，2018，36（9）：96-97.

[4] 樊守伟，严艳，张少杰，等.Dijkstra算法与旅游路径优化[J].西安邮电大学学报，2014，19（1）：121-124.

[5] 晋民杰，黄智，韩智强，等.基于Dijkstra算法的城市公共自行车调配优化分析[J].太原科技大学学报，2017，38（6）：467-471.

[6] 冷思佳.基于Dijkstra算法的优化策略研究[J].中国科技纵横，2019（6）：34-35.

[7] 黄杜鹃，张天圆.基于Dijkstra算法的智能快递柜乡镇选址研究[J].辽宁工业大学学报（自然科学版），2020，40（4）：259-263.

[8] 张淑敏，王元芬.基于Dijkstra算法最短路问题C语言实现[J].计算机与数字工程，2016，44（8）：1399-1401，1406.

【通联编辑：谢媛媛】