呂瓊藝

（廈門(mén)海洋職業(yè)技術(shù)學(xué)院，廈門(mén) 361000）

[政治與社會(huì)經(jīng)濟(jì)研究]

基于改進(jìn)的Dijkstra算法的旅游規(guī)劃線路研究與實(shí)踐
——以鼓浪嶼景區(qū)為例

呂瓊藝

（廈門(mén)海洋職業(yè)技術(shù)學(xué)院，廈門(mén) 361000）

在智慧旅游應(yīng)用中，地圖應(yīng)用或路線規(guī)劃是智慧旅游APP中最重要的需求，而在智慧旅游APP路線規(guī)劃問(wèn)題中，最短路徑問(wèn)題又是其最基本和最關(guān)鍵的問(wèn)題。本文針對(duì)鼓浪嶼景區(qū)特點(diǎn)，對(duì)Dijkstra算法進(jìn)行改進(jìn)優(yōu)化，研究其在鼓浪嶼旅游線路規(guī)劃中的應(yīng)用，為景區(qū)APP旅游交互平臺(tái)的設(shè)計(jì)與開(kāi)發(fā)提供參考。

旅游APP；Dijkstra算法；鼓浪嶼旅游；路線規(guī)劃

廈門(mén)作為國(guó)內(nèi)最佳旅游城市、最佳自助游目的地城市，游客量與日俱增，屢創(chuàng)新高。以2016年春節(jié)假期為例，廈門(mén)接納游客數(shù)量超過(guò)190萬(wàn)人次，同比增長(zhǎng)5.51%。而自駕游與個(gè)人游數(shù)量增長(zhǎng)速度更是迅猛，以自駕游為例，根據(jù)廈鼓碼頭自駕游服務(wù)中心數(shù)據(jù)分析顯示，春節(jié)長(zhǎng)假期間，僅廈鼓碼頭每天就有數(shù)百輛自駕游車(chē)輛進(jìn)出，游客人數(shù)多達(dá)四五千人次。面對(duì)如此龐大的游客量，作為廈門(mén)的標(biāo)志性景區(qū)——鼓浪嶼顯然難以應(yīng)對(duì)，其景區(qū)面積大、景點(diǎn)多、人流量大等特點(diǎn)導(dǎo)致游客無(wú)法獲得應(yīng)有的旅游氣氛，降低旅游體驗(yàn)質(zhì)量，多數(shù)人還沒(méi)游遍就急著搭船返程。廈門(mén)市旅游質(zhì)監(jiān)所提供數(shù)據(jù)顯示，2016年春節(jié)旅游投訴量同比大幅增加，其中鼓浪嶼成為投訴熱點(diǎn)，占70%?；诖?，為提升游客的旅游效率、旅游質(zhì)量及旅游心情，設(shè)計(jì)一款基于最短路徑算法的APP智能旅游平臺(tái)十分有必要。

1 最短路徑算法概述

用于解決最短路徑問(wèn)題的算法被稱作“最短路徑算法”，其本質(zhì)是路徑搜索，基本意思是在路線拓?fù)鋱D中找出地點(diǎn)作為結(jié)點(diǎn)并編號(hào)算出全部結(jié)點(diǎn)之間的最短路徑，然后尋找線路拓?fù)渲袃蓚€(gè)目標(biāo)結(jié)點(diǎn)之間的最短路徑。該算法的基本過(guò)程就是用起始結(jié)點(diǎn)作作中間點(diǎn)，一層一層向周?chē)?jì)算，直到目標(biāo)結(jié)點(diǎn)結(jié)束。整個(gè)過(guò)程需要對(duì)線路拓?fù)鋱D中的所有地點(diǎn)結(jié)點(diǎn)遍歷計(jì)算。目前應(yīng)用比較成熟的最短路徑算法有迪杰斯特拉（Dijkstra）算法、A-Star算法、貝爾曼-福特算法（Bellman-Ford）算法和弗洛伊德（Floyd）算法等。而在實(shí)現(xiàn)智慧旅游線路中，主要運(yùn)用的最短路徑算法為Dijkstra算法。

2 Dijkstra最短路徑算法思想

Dijkstra算法思想為：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖（Graph），其中V表示圖中的頂點(diǎn)（Vertex），E表示頂點(diǎn)組成的邊（Edge），在圖G中，所有的V節(jié)點(diǎn)組成一個(gè)集合，在集合V中有兩類節(jié)點(diǎn)，第一類節(jié)點(diǎn)已求知的最短路徑節(jié)點(diǎn)集合P，第二類為未求知的最短路徑節(jié)點(diǎn)集合T。在第一類節(jié)點(diǎn)集合中設(shè)定一個(gè)源點(diǎn)v1，源點(diǎn)v1出發(fā)求出E最小的第二個(gè)節(jié)點(diǎn)V2，將其放入集合P中，求出第三個(gè)節(jié)點(diǎn)V3，使得其距離集合P中所有的節(jié)點(diǎn)的E最小，并將V3放入集合P中，經(jīng)此類推，直到求出最后一個(gè)節(jié)點(diǎn)Vn，從而求出完整集合P。

3 最短路徑算法Dijkstra的具體步驟

（1）初始時(shí)，P只包含源點(diǎn)，即P＝{v}，T=V-P={其余結(jié)點(diǎn)}，V中頂點(diǎn)間的距離值d用

（2）從T中選取一個(gè)距離v最小且有關(guān)聯(lián)的頂點(diǎn)k，將k加入到P中，則d

（3）以頂點(diǎn)k作為新的基點(diǎn)，調(diào)整頂點(diǎn)集合V中各節(jié)點(diǎn)間孤的權(quán)值；此時(shí)，如果源點(diǎn)v0經(jīng)過(guò)頂點(diǎn)k到達(dá)頂點(diǎn)u的距離短于不經(jīng)過(guò)頂點(diǎn)k的距離，就調(diào)整頂點(diǎn)u的孤權(quán)值，即d

（4）以此類推，重復(fù)上述第（2）點(diǎn)和第（3）點(diǎn)的工作，直到集合P容納了全部頂點(diǎn)。

4 最短路徑算法Dijkstra在鼓浪嶼旅游線路規(guī)劃中的應(yīng)用

在對(duì)基于Dijkstra算法的智能旅游系統(tǒng)進(jìn)行設(shè)計(jì)時(shí)，采用圖的結(jié)構(gòu)來(lái)表示鼓浪嶼景區(qū)中實(shí)際的路徑結(jié)構(gòu)，圖1以圖的結(jié)構(gòu)描述了鼓浪嶼景區(qū)部分景點(diǎn)的旅游線路圖，其中S1～S7分別表示鼓浪嶼景區(qū)的部分景點(diǎn)代碼，具體可參見(jiàn)表1，而鼓浪嶼景區(qū)景點(diǎn)間的距離信息可參見(jiàn)表2。

圖1 鼓浪嶼部分景點(diǎn)旅游線路圖

表1 鼓浪嶼景區(qū)部分景點(diǎn)代碼

表2 鼓浪嶼部份景點(diǎn)的距離矩陣 （m）

以圖1中的鼓浪嶼部分景點(diǎn)旅游線路圖為例，使用Dijkstra算法尋求從廈門(mén)海底世界S1出發(fā)到游客中心S7的最短路徑圖，其具體過(guò)程如表3所示。

表3 Dijkstra算法過(guò)程應(yīng)用實(shí)例

在圖2中的符號(hào)P、D(x)、p(x)分別代表以下含義：

P：結(jié)點(diǎn)子集，如果從源結(jié)點(diǎn)到目的結(jié)點(diǎn)x的最低費(fèi)用路徑已確知，x在P中；

D(x)：隨著算法進(jìn)行本次迭代，從源結(jié)點(diǎn)到目的結(jié)點(diǎn)x的最低費(fèi)用路徑的費(fèi)用；

p(x)：從源結(jié)點(diǎn)到目的結(jié)點(diǎn)x沿著當(dāng)前最低費(fèi)用路徑的前一結(jié)點(diǎn) （x的鄰居）。

當(dāng)Dijkstra算法結(jié)束時(shí)，對(duì)于每個(gè)結(jié)點(diǎn)都能得到從源結(jié)點(diǎn)沿著它的最低費(fèi)用路徑的前一結(jié)點(diǎn)。對(duì)于每個(gè)前一結(jié)點(diǎn)又有它的前一結(jié)點(diǎn)。按照此方式可以構(gòu)建從源結(jié)點(diǎn)到所有結(jié)點(diǎn)的目的路徑。從廈門(mén)海底世界S1出發(fā)到所有目的結(jié)點(diǎn)的最短路徑算法結(jié)果圖可參見(jiàn)圖2。在圖3中可以得到從廈門(mén)海底世界S1-游客中心S7的最短路徑算法結(jié)果圖，其最短路徑以黑色粗線標(biāo)出，即S1-S7的最短路徑為S1-S4-S6-S7。

圖2 從廈門(mén)海底世界-游客中心的最短路徑算法結(jié)果圖 （以加粗部分標(biāo)明）

5 Dijkstra算法的改進(jìn)

在對(duì)Dijkstra算法進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，一般是從數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)優(yōu)化、搜索效率的提升優(yōu)化、網(wǎng)絡(luò)結(jié)構(gòu)或圖結(jié)構(gòu)規(guī)模的控制優(yōu)化等方面的融合優(yōu)化來(lái)進(jìn)行考慮[1]-[3]。當(dāng)然在使用Dijkstra算法或其優(yōu)化算法時(shí)也必須結(jié)合實(shí)際情況客觀分析，對(duì)當(dāng)前因素有取舍地進(jìn)行選擇，從而找出滿足要求的最短路徑。

在對(duì)鼓浪嶼景區(qū)的路線進(jìn)行分析從而設(shè)計(jì)其最短路徑時(shí)，結(jié)合圖1浪嶼部分景點(diǎn)旅游線路圖可知，圖中結(jié)點(diǎn)個(gè)數(shù)并不算多，其網(wǎng)絡(luò)結(jié)構(gòu)矩陣也不算稀疏，所以為了便于實(shí)現(xiàn)，在對(duì)Dijkstra算法進(jìn)行優(yōu)化或改進(jìn)時(shí)，實(shí)際上并不需要對(duì)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)、網(wǎng)絡(luò)結(jié)構(gòu)或圖結(jié)構(gòu)規(guī)模的控制等方面進(jìn)行特別優(yōu)化，而只需要在搜索效率的優(yōu)化上做文章即可滿足實(shí)用性要求?；诖耍疚脑趯?duì)數(shù)據(jù)存儲(chǔ)比原來(lái)略高的基礎(chǔ)上提出了改進(jìn)的Dijkstra算法。這種改進(jìn)方法的基本思想是：假設(shè)以S1點(diǎn)作為起始結(jié)點(diǎn)，以結(jié)點(diǎn) S7作為目的結(jié)點(diǎn)的最短路徑已經(jīng)求出，其路徑為為S1，S4，S6，S7；則如需尋找從從結(jié)點(diǎn)S4出發(fā)到結(jié)點(diǎn)S7或到結(jié)點(diǎn)S6的最短路徑時(shí)，就不用再去按照Dijkstra算法去求，可按照已找出的結(jié)點(diǎn)S1→結(jié)點(diǎn)S7的最短路徑直接得出結(jié)點(diǎn)S4→結(jié)點(diǎn)S7的最短路徑為S4，S6，S7；得出結(jié)點(diǎn)S4→結(jié)點(diǎn)S6的最短路徑為S4，S6。也就是可以對(duì)先前獲取的最短路徑成果給予保存，然后在計(jì)算從源點(diǎn)到其他頂點(diǎn)的最短路徑時(shí)，通過(guò)已經(jīng)存儲(chǔ)的信息快速得到源點(diǎn)到目的結(jié)點(diǎn)之間的最短路徑。改進(jìn)后Dijkstra算法的流程圖如圖3所示，其中ds為出發(fā)結(jié)點(diǎn)s到其他結(jié)點(diǎn)（如結(jié)點(diǎn)t）的距離，將其初始化為0；ps表示從源結(jié)點(diǎn)s到某一目的結(jié)點(diǎn)t的最短路徑中其他結(jié)點(diǎn)t點(diǎn)的前一個(gè)點(diǎn)；dj表示檢驗(yàn)從所+標(biāo)記的結(jié)點(diǎn)k到其他未標(biāo)記的結(jié)點(diǎn)j的距離，而w(k,j)表示從結(jié)點(diǎn)k到結(jié)點(diǎn)j的路徑長(zhǎng)度。與經(jīng)典的Dijkstra算法相比，改進(jìn)后的算法在計(jì)算效率上有所提高。

圖3 改進(jìn)后的Dijkstra算法的流程圖

6 結(jié)語(yǔ)

最短路徑算法在各行各業(yè)發(fā)展過(guò)程中的發(fā)揮的作用越來(lái)越大，特別是在智慧旅游中的旅游線路規(guī)劃中，找出高效率的最短路徑算法相當(dāng)重要，值得研究。本文在傳統(tǒng)Dijkstra算法的基礎(chǔ)上，利用先前通過(guò)Dijkstra算法得出的結(jié)果，快速算出后續(xù)節(jié)點(diǎn)的最短路徑，并給出了相關(guān)的步驟及實(shí)現(xiàn)的流程圖。改進(jìn)的算法在一定意義上提高了計(jì)算效率。

[1]符頓紅.淺談在計(jì)算機(jī)上更好的實(shí)現(xiàn)Floyd算法[J].電子制作，2013（23）:23-26.

[2]羅理，王鋒.基于Dijkstra算法的最短路徑改進(jìn)算法[J].湖北汽車(chē)工業(yè)學(xué)院學(xué)報(bào)，2007（06）：22-25.

[3]張志敏.手機(jī)導(dǎo)航系統(tǒng)中最短路徑算法的優(yōu)化與實(shí)現(xiàn)[D].西安：西北大學(xué)，2011:12-14.

[4]宣潔，鄧謙，劉文才.基于GPS定位的旅游拼車(chē)app中路徑規(guī)劃算法的研究[J].城市建設(shè)理論研究，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

廈門(mén)海洋職業(yè)技術(shù)學(xué)院2014-2015年度院級(jí)科研項(xiàng)目（kyzy201402）

呂瓊藝，碩士，廈門(mén)海洋職業(yè)技術(shù)學(xué)院講師，研究方向?yàn)槁糜谓?jīng)濟(jì)和智慧旅游。