基于改进的Dijkstra算法的旅游规划线路研究与实践——以鼓浪屿景区为例

吕琼艺

（厦门海洋职业技术学院，厦门 361000）

[政治与社会经济研究]

基于改进的Dijkstra算法的旅游规划线路研究与实践
——以鼓浪屿景区为例

吕琼艺

（厦门海洋职业技术学院，厦门 361000）

在智慧旅游应用中，地图应用或路线规划是智慧旅游APP中最重要的需求，而在智慧旅游APP路线规划问题中，最短路径问题又是其最基本和最关键的问题。本文针对鼓浪屿景区特点，对Dijkstra算法进行改进优化，研究其在鼓浪屿旅游线路规划中的应用，为景区APP旅游交互平台的设计与开发提供参考。

旅游APP；Dijkstra算法；鼓浪屿旅游；路线规划

厦门作为国内最佳旅游城市、最佳自助游目的地城市，游客量与日俱增，屡创新高。以2016年春节假期为例，厦门接纳游客数量超过190万人次，同比增长5.51%。而自驾游与个人游数量增长速度更是迅猛，以自驾游为例，根据厦鼓码头自驾游服务中心数据分析显示，春节长假期间，仅厦鼓码头每天就有数百辆自驾游车辆进出，游客人数多达四五千人次。面对如此庞大的游客量，作为厦门的标志性景区——鼓浪屿显然难以应对，其景区面积大、景点多、人流量大等特点导致游客无法获得应有的旅游气氛，降低旅游体验质量，多数人还没游遍就急着搭船返程。厦门市旅游质监所提供数据显示，2016年春节旅游投诉量同比大幅增加，其中鼓浪屿成为投诉热点，占70%。基于此，为提升游客的旅游效率、旅游质量及旅游心情，设计一款基于最短路径算法的APP智能旅游平台十分有必要。

1 最短路径算法概述

用于解决最短路径问题的算法被称作“最短路径算法”，其本质是路径搜索，基本意思是在路线拓扑图中找出地点作为结点并编号算出全部结点之间的最短路径，然后寻找线路拓扑中两个目标结点之间的最短路径。该算法的基本过程就是用起始结点作作中间点，一层一层向周围计算，直到目标结点结束。整个过程需要对线路拓扑图中的所有地点结点遍历计算。目前应用比较成熟的最短路径算法有迪杰斯特拉（Dijkstra）算法、A-Star算法、贝尔曼-福特算法（Bellman-Ford）算法和弗洛伊德（Floyd）算法等。而在实现智慧旅游线路中，主要运用的最短路径算法为Dijkstra算法。

2 Dijkstra最短路径算法思想

Dijkstra算法思想为：设G=(V,E)是一个带权有向图（Graph），其中V表示图中的顶点（Vertex），E表示顶点组成的边（Edge），在图G中，所有的V节点组成一个集合，在集合V中有两类节点，第一类节点已求知的最短路径节点集合P，第二类为未求知的最短路径节点集合T。在第一类节点集合中设定一个源点v1，源点v1出发求出E最小的第二个节点V2，将其放入集合P中，求出第三个节点V3，使得其距离集合P中所有的节点的E最小，并将V3放入集合P中，经此类推，直到求出最后一个节点Vn，从而求出完整集合P。

3 最短路径算法Dijkstra的具体步骤

（1）初始时，P只包含源点，即P＝{v}，T=V-P={其余结点}，V中顶点间的距离值d用

（2）从T中选取一个距离v最小且有关联的顶点k，将k加入到P中，则d

（3）以顶点k作为新的基点，调整顶点集合V中各节点间孤的权值；此时，如果源点v0经过顶点k到达顶点u的距离短于不经过顶点k的距离，就调整顶点u的孤权值，即d

（4）以此类推，重复上述第（2）点和第（3）点的工作，直到集合P容纳了全部顶点。

4 最短路径算法Dijkstra在鼓浪屿旅游线路规划中的应用

在对基于Dijkstra算法的智能旅游系统进行设计时，采用图的结构来表示鼓浪屿景区中实际的路径结构，图1以图的结构描述了鼓浪屿景区部分景点的旅游线路图，其中S1～S7分别表示鼓浪屿景区的部分景点代码，具体可参见表1，而鼓浪屿景区景点间的距离信息可参见表2。

图1 鼓浪屿部分景点旅游线路图

表1 鼓浪屿景区部分景点代码

表2 鼓浪屿部份景点的距离矩阵 （m）

以图1中的鼓浪屿部分景点旅游线路图为例，使用Dijkstra算法寻求从厦门海底世界S1出发到游客中心S7的最短路径图，其具体过程如表3所示。

表3 Dijkstra算法过程应用实例

在图2中的符号P、D(x)、p(x)分别代表以下含义：

P：结点子集，如果从源结点到目的结点x的最低费用路径已确知，x在P中；

D(x)：随着算法进行本次迭代，从源结点到目的结点x的最低费用路径的费用；

p(x)：从源结点到目的结点x沿着当前最低费用路径的前一结点 （x的邻居）。

当Dijkstra算法结束时，对于每个结点都能得到从源结点沿着它的最低费用路径的前一结点。对于每个前一结点又有它的前一结点。按照此方式可以构建从源结点到所有结点的目的路径。从厦门海底世界S1出发到所有目的结点的最短路径算法结果图可参见图2。在图3中可以得到从厦门海底世界S1-游客中心S7的最短路径算法结果图，其最短路径以黑色粗线标出，即S1-S7的最短路径为S1-S4-S6-S7。

图2 从厦门海底世界-游客中心的最短路径算法结果图 （以加粗部分标明）

5 Dijkstra算法的改进

在对Dijkstra算法进行优化设计时，一般是从数据结构的存储优化、搜索效率的提升优化、网络结构或图结构规模的控制优化等方面的融合优化来进行考虑[1]-[3]。当然在使用Dijkstra算法或其优化算法时也必须结合实际情况客观分析，对当前因素有取舍地进行选择，从而找出满足要求的最短路径。

在对鼓浪屿景区的路线进行分析从而设计其最短路径时，结合图1浪屿部分景点旅游线路图可知，图中结点个数并不算多，其网络结构矩阵也不算稀疏，所以为了便于实现，在对Dijkstra算法进行优化或改进时，实际上并不需要对数据结构的存储、网络结构或图结构规模的控制等方面进行特别优化，而只需要在搜索效率的优化上做文章即可满足实用性要求。基于此，本文在对数据存储比原来略高的基础上提出了改进的Dijkstra算法。这种改进方法的基本思想是：假设以S1点作为起始结点，以结点 S7作为目的结点的最短路径已经求出，其路径为为S1，S4，S6，S7；则如需寻找从从结点S4出发到结点S7或到结点S6的最短路径时，就不用再去按照Dijkstra算法去求，可按照已找出的结点S1→结点S7的最短路径直接得出结点S4→结点S7的最短路径为S4，S6，S7；得出结点S4→结点S6的最短路径为S4，S6。也就是可以对先前获取的最短路径成果给予保存，然后在计算从源点到其他顶点的最短路径时，通过已经存储的信息快速得到源点到目的结点之间的最短路径。改进后Dijkstra算法的流程图如图3所示，其中ds为出发结点s到其他结点（如结点t）的距离，将其初始化为0；ps表示从源结点s到某一目的结点t的最短路径中其他结点t点的前一个点；dj表示检验从所+标记的结点k到其他未标记的结点j的距离，而w(k,j)表示从结点k到结点j的路径长度。与经典的Dijkstra算法相比，改进后的算法在计算效率上有所提高。

图3 改进后的Dijkstra算法的流程图

6 结语

最短路径算法在各行各业发展过程中的发挥的作用越来越大，特别是在智慧旅游中的旅游线路规划中，找出高效率的最短路径算法相当重要，值得研究。本文在传统Dijkstra算法的基础上，利用先前通过Dijkstra算法得出的结果，快速算出后续节点的最短路径，并给出了相关的步骤及实现的流程图。改进的算法在一定意义上提高了计算效率。

[1]符顿红.浅谈在计算机上更好的实现Floyd算法[J].电子制作，2013（23）:23-26.

[2]罗理，王锋.基于Dijkstra算法的最短路径改进算法[J].湖北汽车工业学院学报，2007（06）：22-25.

[3]张志敏.手机导航系统中最短路径算法的优化与实现[D].西安：西北大学，2011:12-14.

[4]宣洁，邓谦，刘文才.基于GPS定位的旅游拼车app中路径规划算法的研究[J].城市建设理论研究，2014（10）:10-13.

Research and Practiceof Tourism Planning Line Based on Im proved Dijkstra Algorithm by a Case Study of Gulangyu Scenic Spot

LVQ iong-yi

(Xiamen Ocean VocationalCollege,Xiamen Fujian 361000,China)

The application ofmap or the route planning is themost important requirementof Intelligent Tourism APP.The shortestpath is themostbasic and criticalpoint in the planning route of Intelligent Tourism APP.Thispaper iscarrying outa systematic study and application of theoptim ized Dijkstraalgorithm in the lightof the characteristicsofGulangyu Isletscenic spot,and providesa reference for the design and developmentofAPP tourism interactiveplatform.

tourism APP;Dijkstraalgorithm;Gulangyu tourism;route planning

F590.1

A

1671-1084（2017）02-0032-05

DOI 10.16221/j.cnki.issn1671-1084.2017.02.007

2016-10-27

厦门海洋职业技术学院2014-2015年度院级科研项目（kyzy201402）

吕琼艺，硕士，厦门海洋职业技术学院讲师，研究方向为旅游经济和智慧旅游。