基于改進的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）

呂瓊藝，碩士，廈門海洋職業技術學院講師，研究方向為旅游經濟和智慧旅游。