董妍汝

(山西大學(xué)商務(wù)學(xué)院信息學(xué)院，山西 太原 030031)

基于最短路徑的旅游咨詢網(wǎng)站的設(shè)計與應(yīng)用

董妍汝

(山西大學(xué)商務(wù)學(xué)院信息學(xué)院，山西 太原 030031)

為了滿足旅行者和旅行社對旅游景點最短路徑查詢的需求，采用Dijkstra算法實現(xiàn)了四種基本查詢方式，滿足用戶對旅游景點間的最優(yōu)路徑查找，并設(shè)計了基于最短路徑的旅游咨詢網(wǎng)站。文中首先對所采用的算法進行了簡單介紹，然后以山西省的旅游景點為例對網(wǎng)站的查詢功能進行了詳細闡述，最后對采用Dijkstra算法后的路徑選擇性能進行分析。

最短路徑；Dijkstra算法； 旅游咨詢

隨著生活節(jié)奏的加速和能源的緊缺，無論是對與旅行者還是旅行社而言，旅游路線都是其關(guān)注的重中之重。對于旅行者而言，希望在旅行中能夠以最小的時間成本和金錢成本滿足最大化的消費需求；對旅行社而言，期望滿足客戶的同時盡可能地降低成本，從而提高其效益[1]。因此，本文采用最短路徑算法設(shè)計并實現(xiàn)旅游咨詢網(wǎng)站，將旅游景點之間的路線進行定量的分析，使旅行者和旅行社得到相對合適的旅游路線，從而合理的安排旅游行程，滿足各自的需求。

1 最短路徑算法

考慮到為用戶提供最優(yōu)路徑能節(jié)省用戶的旅行時間和經(jīng)費，也能夠間接地節(jié)省能源，本文采用經(jīng)典的Dijkstra算法獲取景點間的最短路徑[2]。Dijkstra算法是貪婪法應(yīng)用的一個例子，主要用來解決單個源點到其它頂點的最短路徑。

Dijkstra算法按照路徑“長度”遞增的次序產(chǎn)生最短路徑[3]。該算法將圖G(V,E)中的頂點分成兩個集合VA、VB，如果源點S到某一個頂點的最短路徑已經(jīng)確定，則該頂點屬于VA，反之，則屬于VB。初始時，VA中只有源點S，其余的頂點均在VB中，算法結(jié)束時，源點可以直接或間接到達的頂點均屬于VA，源點不能到達的頂點留在VB中。

2 基于最短路徑算法的旅游咨詢網(wǎng)站設(shè)計

本文以山西省的旅游景點為例，設(shè)計基于最短路徑算法的旅游咨詢網(wǎng)站，分別從以下三個方面對該網(wǎng)站進行介紹。

2.1 網(wǎng)站功能的設(shè)計

該網(wǎng)站主要功能是為用戶提供山西省各地區(qū)風(fēng)景名勝詳細介紹的同時，為網(wǎng)站用戶提供最短路徑查詢，主要包括以下查詢方式：

1) 用戶輸入起點，可以顯示起點到山西各旅游景點的最短旅游線路，供用戶對比選擇。

2) 用戶輸入起點、終點，可以顯示這兩地之間的最短旅游線路。

3) 用戶輸入起點、意向旅游的若干景點，可以為用戶提供一條包含這些景點的最短旅游線路。

4) 用戶輸入起點、意向旅游的景點、終點，為用戶規(guī)劃一條從起點到終點并途經(jīng)用戶意向旅游景點的最短路線。

以上查詢方式不僅實現(xiàn)了任意兩個旅游景點間的最短旅游路線查詢，對多個特定旅游景點間的最短路徑也可進行查詢，實現(xiàn)了路徑的智能查詢[4]。

2.2 旅游景點最短路徑的算法

以云岡石窟，懸空寺，應(yīng)縣木塔，五臺山，晉祠，平遙古城這六個旅游景點為例進行各種最短路徑的規(guī)劃。為方便起見，依次用V0，V1，V2，V3，V4，V5表示這六個旅游景點，即云岡石窟V0，懸空寺V1，應(yīng)縣木塔V2，五臺山V3，晉祠V4，平遙古城V5。根據(jù)這六個景點的分布圖，已知這些景點之間的距離(該距離按照二級公路來計算)，構(gòu)造出如圖1所示的帶權(quán)無向圖。

1) 單個旅游景點到其它景點間的最短路徑查詢

圖1 帶權(quán)無向圖

當用戶想了解云岡石窟到其它五個景點的最短旅游線路時，用戶可以進入網(wǎng)站的查詢頁面，在“起點”中輸入云岡石窟，單擊查詢，可以得到以下查詢結(jié)果：從V0到各個結(jié)點的最短路徑為：V0-V1；V0-V2；V0-V2-V3；V0-V4；V0-V4-V5。即從云岡石窟出發(fā)到五臺山，經(jīng)過應(yīng)縣木塔的路徑是最短的；同理，從云岡石窟出發(fā)到平遙古城，經(jīng)過晉祠的路徑是最短的。

運用第二部分中描述的Dijkstra算法，可以求得從結(jié)點V0(即云岡石窟)到各個結(jié)點的最短路徑。如表1所示，表中展示了每次尋找當前不屬于S集合的，并且具有最短路徑的頂點的過程。其中，粗黑色方框中表示的就是從結(jié)點V0到各個結(jié)點的最短路徑以及該路徑的長度。

表1 從V0到各終點的dist值和最短路徑示意

該查詢功能是Dijkstra算法的直接應(yīng)用。通過上述的例子可以知道，運用該算法即可求得從某一旅游景點到其余各景點的最短路徑，從而可在一定程度上節(jié)省游客的旅行經(jīng)費和時間。

2) 兩個旅游景點間的最短路徑查詢

當用戶想查從懸空寺(V1)去晉祠(V4)的最短旅游路徑時，可在查詢頁面的“起點”輸入懸空寺，“終點”輸入晉祠，單擊查詢，可得到查詢結(jié)果：懸空寺—五臺山—晉祠。

第二種查詢方式的實現(xiàn)與第一種查詢方式相同，以用戶輸入的“起點”懸空寺(V1)為源點，執(zhí)行Dijkstra算法，算出懸空寺(V1)到各旅游景點的最短路徑，只是在顯示結(jié)果時只提供給用戶懸空寺(V1)到晉祠(V4)的最短路徑。

3) 多個旅游景點之間的最短路徑查詢

如果用戶從懸空寺(V1)出發(fā)，希望得到一條經(jīng)過云岡石窟(V0)、應(yīng)縣木塔(V2)、晉祠(V4)的最短旅游線路，可在查詢頁面的“起點”中輸入懸空寺，“途經(jīng)”輸入云岡石窟、應(yīng)縣木塔、晉祠，單擊查詢，得到查詢結(jié)果：懸空寺—云岡石窟—應(yīng)縣木塔—五臺山—晉祠。

第三種查詢方式是求多點之間的最短路徑，即全局最優(yōu)解。Dijkstra算法只能用于求兩點之間的最短路徑，不能解決這個問題，在此，采用Dijkstra算法尋求局部最短路徑，從而形成全局較優(yōu)路徑。

首先以用戶輸入的“起點”為源點，尋找該源點到“途經(jīng)”地各景點的最短路徑，找出離“起點”最近的景點。繼續(xù)以此景點為源點，尋找該源點到剩余“途經(jīng)”地各景點的最近景點，直到所有的“途經(jīng)”景點都尋找完畢。為了使查詢的結(jié)果能接近全局最優(yōu)解，將剛才的查找過程再逆序執(zhí)行遍，即以最后一次找到的景點為源點，用戶輸入的“起點”為終點，尋找全局最優(yōu)路徑。這兩次查找的路徑有可能是不一樣的，其中最短的路徑就是最終提供給用戶的查詢結(jié)果。具體步驟及流程圖如圖2。

圖2 多景點最短路線查詢流程圖

定義集合VA中存放已經(jīng)找到最小路徑的頂點，初始值為源點S，集合VB中存放所有頂點，集合VC中存放用戶“途經(jīng)”的頂點。dist[i]表示到頂點Vi的最短路徑。D表示最終的最短路徑。

第一步：以用戶輸入的“起點”為源點S；

第二步：調(diào)用Dijkstra算法在集合VB中尋找S到集合VC所有頂點的最短路徑，并找到其中的最小值dist[j]。

dist[j]=min{dist[i]|( Vi∈VB)}

D1=D1+ dist[j]

第三步：將頂點j從集合VB、VC中刪除，放入集合VA。

第四步：判斷VC是否為空，如果為空，則表示正向查找完畢，結(jié)果為D1，繼續(xù)執(zhí)行第五步。否則返回第二步。

第五步：以最后經(jīng)過的頂點為源點，開始逆向查詢。查詢的結(jié)果為D2。

第六步：如果D1

4) 確定起點和終點的多景點最短路徑查詢

如果用戶想了解從懸空寺(V1)出發(fā)，終點到云岡石窟(V0)，途經(jīng)應(yīng)縣木塔(V2)，晉祠(V4)的最短旅游路徑，可在查詢頁面的“起點”中輸入懸空寺，“終點”輸入云岡石窟，“途經(jīng)”輸入應(yīng)縣木塔，晉祠，單擊查詢，可以得到查詢結(jié)果：V1-V3-V4-V3-V2-V0。

這種查詢方式與第三種查詢方式類似，都是用Dijkstra算法尋求局部最短路徑，從而形成全局較優(yōu)路徑。查詢時，以用戶輸入的“起點”為源點，進行一次正向查詢，再以用戶輸入的“終點”為源點，進行一次逆向查詢。比較兩次查詢結(jié)果中路徑的長度，如果正向查詢的結(jié)果小，則輸出該線路，如果逆向查詢的結(jié)果小，則逆序輸出路徑中的頂點。

3 基于最短路徑算法的旅游咨詢網(wǎng)站性能

用戶使用景點間最短路徑咨詢的功能后，可以在一定程度上節(jié)省旅行時間和經(jīng)費。例如在前面的例子中，用戶欲獲取從云岡石窟到平遙古城的最短路徑(即頂點V0到V5)。從頂點V0到V5有多條路徑，如V0-V4-V5，V0-V1-V2-V3-V5，V0-V5，V0-V2-V3-V5，V0-V1-V3-V4-V5，分別記為路徑1，路徑2，路徑3，路徑4，路徑5。通過對數(shù)據(jù)庫的查詢與簡單的計算，可知這五條路徑各自的全程長度：路徑1=520公里，路徑2=450公里，路徑3=490公里，路徑4=470公里，路徑5=480公里。

據(jù)調(diào)查，普通小轎車每100公里需要耗油約為10升，旅行客車每100公里需要耗油約為22升。若按油價為6.5元/升來計算，可以得到普通小轎車和旅行客車分別行駛這五條路徑所需的汽油費用。同理，假定在高速公路上汽車行駛的速度為80公里/小時，也可以得到普通小轎車和旅行客車分別行駛這五條路徑所需的時間。如表2所示。

表2 行駛五條路徑消耗費用和時間表

由上述分析可知，選擇頂點V0到V5的最短路徑(即V0-V4-V5，路徑2)，即從云岡石窟出發(fā)到平遙古城，經(jīng)過晉祠的路徑(全程450公里)，這要比從頂點V0直接到達V5(即V0-V5，路徑3)，即從云岡石窟直接到平遙古城(全程490公里)少行駛40公里的路程。在采用最短路徑經(jīng)算法后，對于普通小轎車可節(jié)省油費約26元；對于旅行客車來說可節(jié)省油費約57.2元，可節(jié)省時間約30分鐘。從上述數(shù)據(jù)可以看出將最短路徑算法應(yīng)用于旅游咨詢網(wǎng)站中具有一定的可行性。

4 結(jié)束語

本文將最短路徑算法應(yīng)用在旅游咨詢網(wǎng)站中，并對該網(wǎng)站的相關(guān)功能、算法及數(shù)據(jù)庫進行了設(shè)計。同時，以山西省旅游景點為例，對設(shè)計的具有最短路徑咨詢功能的旅游網(wǎng)站進行實驗分析。通過分析可知，將該算法應(yīng)用在旅游咨詢網(wǎng)站中，可以使用戶根據(jù)各自不同的需求對景點間的最短路徑進行咨詢的同時，節(jié)省游客的旅行經(jīng)費和寶貴的時間。

[1] 黃心,吳學(xué)群,袁清冽.蟻群算法在外賣配送路徑規(guī)劃中的應(yīng)用[J].價值工程,2017(5):65-67.

[2] 張靚.基于子集優(yōu)化的Dijkstra算法的交通最短路徑查詢系統(tǒng)的設(shè)計與實現(xiàn)[D].長春：吉林大學(xué),2015.

[3] 王樹西,李安渝.Dijkstra算法中的多鄰接點與多條最短路徑問題[J].計算機科學(xué),2014(6):217-224.

[4] 胡喬楠.基于旅游文記的旅游景點推薦及行程路線規(guī)劃系統(tǒng)[D].杭州：浙江大學(xué),2015.

[5] 喬天斐.基于Android平臺的自助旅游系統(tǒng)研究與實現(xiàn)[D].成都：電子科技大學(xué),2016.

[6] 饒亞玲.基于客流疏導(dǎo)的景區(qū)游覽線路優(yōu)化研究[D].泉州：華僑大學(xué),2015.

[7] 鄭外輝.符合游客口味的旅游路線分析技術(shù)研究與應(yīng)用[D].杭州：浙江大學(xué),2015.

[8] 左為平,劉云芳.Dijkstra算法在最短旅游路徑中的應(yīng)用[J].計算機與信息技術(shù),2011(增刊2):41-42.

The Design and Application of Tourism Consultation Website Based on Shortest Path Algorithm

Dong Yanru

(InformationProjectDepartment,BusinessCollegeofShanxiUniversity,TaiyuanShanxi030031,China)

In this paper, Dijkstra algorithm is used for finding the optimal path among the tourist attractions to satisfy the travelers and travel agencies’ needs. Thus the Tourism Consultation Website based on the shortest path algorithm is designed. Firstly, the paper makes a brief description on the relevant algorithm, then, taking Shanxi tourist spot for example, it expounds the function of design. Finally it analyzes the performance of the path selection after the relevant algorithm is adopted.

shortest path; Dijkstra algorithm; tourism consultation

2016-03-15

董妍汝(1981- )，女，山西運城人，副教授，研究生，研究方向：計算機應(yīng)用。

1674- 4578(2017)02- 0045- 04

TP393

A