改進(jìn)的Dijkstra算法在多點(diǎn)最優(yōu)路徑組合中的應(yīng)用
——以大學(xué)生出游App為例

唐彬文,卓雨嘉,陳小青

集美大學(xué)誠(chéng)毅學(xué)院,福建廈門361021

改進(jìn)的Dijkstra算法在多點(diǎn)最優(yōu)路徑組合中的應(yīng)用
——以大學(xué)生出游App為例

唐彬文,卓雨嘉,陳小青

集美大學(xué)誠(chéng)毅學(xué)院,福建廈門361021

隨著我國(guó)經(jīng)濟(jì)發(fā)展和社會(huì)進(jìn)步，人們滿足了日益豐富的物質(zhì)生活的同時(shí)更多追求精神上愉悅，因此，旅游業(yè)方興未艾。面對(duì)如火如荼的旅游在線平臺(tái)的發(fā)展，如何為游客提供多點(diǎn)組合的最優(yōu)觀光路徑，成為當(dāng)下迫切的需求。本文擯棄傳統(tǒng)的點(diǎn)對(duì)點(diǎn)導(dǎo)航模式，利用改進(jìn)的Dijkstra算法設(shè)計(jì)和開發(fā)了一個(gè)具有旅游線路推薦功能的大學(xué)生出游App，充分利用現(xiàn)有的移動(dòng)平臺(tái)載體，為游客方便快捷地規(guī)劃合理的游覽線路。

Dijkstra算法;旅游;App

Dijkstra方法是目前公認(rèn)最好的最短路徑計(jì)算方法，是由Dijkstra于1959年提出的。Dijkstra算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑[1]。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法的基本思想是源點(diǎn)V0出發(fā)，逐步向外擴(kuò)張，尋找最短路徑直至終點(diǎn)Vn的過程。經(jīng)典的Dijkstra算法只能分別計(jì)算出源點(diǎn)（出發(fā)點(diǎn)）到各個(gè)點(diǎn)的最短路徑。但是現(xiàn)實(shí)的旅游線路需求不是點(diǎn)對(duì)點(diǎn)的，經(jīng)常是多點(diǎn)的集合。那么針對(duì)多點(diǎn)最優(yōu)路徑組合，經(jīng)典的Dijkstra算法是無(wú)法計(jì)算的。本項(xiàng)目運(yùn)用面向?qū)ο蟮某绦蛟O(shè)計(jì)思想，前端設(shè)計(jì)采用Html5風(fēng)格設(shè)計(jì)，后臺(tái)開發(fā)采用php+mysql+apache組合，最后使用Cordova進(jìn)行App的封裝。App核心模塊功能旅游線路推薦模塊是通過改進(jìn)Dijkstra算法，經(jīng)過多次循環(huán)嵌套、迭代和數(shù)組遍歷等方法推算出多點(diǎn)的最優(yōu)路徑組合。

1 算法思想

1.1 前提假設(shè)

（1）所有節(jié)點(diǎn)組成的集合圖是賦權(quán)無(wú)向圖。即Vn-1到Vn之間的距離與Vn到Vn-1之間的距離相等；

（2）V0為源點(diǎn)（出發(fā)點(diǎn)）；

（3）所有路徑的組合必須回到源點(diǎn)，形成回路；

（4）為了便于輸出結(jié)果的解讀，算例使用的節(jié)點(diǎn)個(gè)數(shù)為5，包括源點(diǎn)V0。

1.2 算法邏輯

（1）經(jīng)典Dijkstra算法的引入；

（2）改進(jìn)算法，分別計(jì)算出包括源點(diǎn)在內(nèi)的所有點(diǎn)之間的最短路徑；

（3）將最短路徑值和最短路徑經(jīng)過的點(diǎn)集分別存入多維數(shù)組Djz和Ejz；

（4）根據(jù)游客選擇的景點(diǎn)（包括源點(diǎn)）構(gòu)成一個(gè)點(diǎn)集Vx，Vx?Vn。(n為景點(diǎn)總數(shù)，n包括源點(diǎn))；

（5）使用循環(huán)迭代判斷Vi-1→Vi之間的路徑是否包括第三點(diǎn)j(i?x;j?x)，如果有則從Vx中剔除；

（6）最終得到的點(diǎn)集Vm就為最優(yōu)路徑組合(m?x)；

（7）m個(gè)節(jié)點(diǎn)依次排列形成組合（V0→V1→V2→?→Vm），按照點(diǎn)對(duì)點(diǎn)組合分別從Djz和Ejz獲取值，組成最優(yōu)路徑值和最優(yōu)路徑組合點(diǎn)集。

2 算法實(shí)現(xiàn)

2.1 算法案例

算法通過實(shí)測(cè)30多個(gè)算例，能夠滿足20個(gè)節(jié)點(diǎn)以內(nèi)的最優(yōu)組合計(jì)算。本項(xiàng)目為周邊游項(xiàng)目（短期旅游項(xiàng)目），為了良好的用戶體驗(yàn)和論文闡述清晰，便以廈門地區(qū)四個(gè)主要景點(diǎn)的實(shí)際距離賦權(quán)為算例。圖1是以四個(gè)景點(diǎn)構(gòu)建的賦權(quán)無(wú)向圖。并將節(jié)點(diǎn)之間的距離存入初始矩陣。2.2構(gòu)建類計(jì)算最短路徑和最短路徑經(jīng)過的點(diǎn)集

圖1 賦權(quán)無(wú)向圖Fig.1 Undirected weighted graph

圖2 初始矩陣Fig.2 The initial matrix

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

2.2.2 初始算法解釋

2.2.3 最優(yōu)點(diǎn)集算法解釋

①用數(shù)組$V存放包括源點(diǎn)在內(nèi)的所有節(jié)點(diǎn)；

②數(shù)組遍歷距離源點(diǎn)最近的節(jié)點(diǎn)X，并從數(shù)組$V中，去除該節(jié)點(diǎn);

③比較其他點(diǎn)Y與源點(diǎn)的距離$d[Y]是否大于$d[X]（X與源點(diǎn)距離）+$G[X][Y](節(jié)點(diǎn)X與Y的距離)，是則用該距離存入最短路徑數(shù)組$d,同時(shí)更新最短路徑組合覆蓋原有的二維數(shù)組$E[$value]，并將該節(jié)點(diǎn)的編號(hào)添加在$E[$value]的尾部。

④循環(huán)以上操作則可以得出：

$d=Array([0]=>0[1]=>5[2]=>3[3]=>1[4]=>6)

$E=Array([0]=>Array([0]=>0)[1]=>Array([0]=>0[1]=>2)[2]=>Array([0]=>0)[3]=> Array([0]=>0)[4]=>Array([0]=>0[1]=>2[2]=>1))

例如：V0到V4的最短距離為：$d[4]=6；經(jīng)過的路徑為$E[4]=V0→V2→V1。

2.2.4 節(jié)點(diǎn)間最短路徑值和最短路徑經(jīng)過節(jié)點(diǎn)集的計(jì)算

多源點(diǎn)算法解釋：分別以0～4，五個(gè)節(jié)點(diǎn)為源點(diǎn)求出與其他點(diǎn)的最短距離存入二維數(shù)組$Djz，和最短路徑節(jié)點(diǎn)集存入三維數(shù)組$Ejz。

2.2.5 結(jié)果輸出及解釋

$Djz為：

以上值轉(zhuǎn)化為多點(diǎn)最優(yōu)矩陣為：

圖3 最優(yōu)矩陣Fig.3 Optimal matrix

三維數(shù)組$Ejz為：

輸出結(jié)果解釋：例如$Ejz[0][1]=(0,2),表示到達(dá)V1的最短路徑點(diǎn)集為(V0,V2)。

2.3 多點(diǎn)最優(yōu)組合計(jì)算

2.3.1 最短距離算法

算法解釋：三維數(shù)組$Ejz[x][y][i]，x與y表示兩個(gè)節(jié)點(diǎn)，第三維i表示它們之間最短路徑經(jīng)過的節(jié)點(diǎn)集。用循環(huán)計(jì)算出兩點(diǎn)之間的最短路徑$sum。

2.3.2 交叉節(jié)點(diǎn)剔除算法

2.3.3 算法解釋

(1)根據(jù)游客提交的景點(diǎn)組合作為節(jié)點(diǎn)存入數(shù)組$Vs，$Vs=(0,a,b,c,d),0為源點(diǎn)，a,b,c,d為景點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)（0為源點(diǎn)為必選項(xiàng)，其余節(jié)點(diǎn)可任意組合）；

(2)將$Vs付給$Os，因?yàn)?Vs將進(jìn)行刪除重復(fù)節(jié)點(diǎn)操作，需要一個(gè)完整的初始值做重復(fù)的遍歷；故定義$Us數(shù)組存放經(jīng)過刪除操作的$Vs數(shù)組；

(3)通過三層嵌套的數(shù)組迭代，剔除路徑交叉時(shí)的重復(fù)節(jié)點(diǎn)。依次剔除$Vs中兩個(gè)節(jié)點(diǎn)的x,y，并獲取對(duì)應(yīng)三維數(shù)組$Ejz[x][y]的值，遍歷剩余節(jié)點(diǎn)數(shù)組$Us，判斷是否有節(jié)點(diǎn)與$Ejz[x][y]中的節(jié)點(diǎn)重復(fù)，有將其從$Vs中刪除。

(4)以上代碼段若$Vs=Array(0,1,2,3,4)，輸出結(jié)果為Array([0]=>0[1]=>3[2]=>4)，

即$newVs=Array(0,3,4)。

2.3.4 多點(diǎn)最優(yōu)路徑組合算法

2.3.5 算法解釋

(1)方法best()用于計(jì)算最優(yōu)的距離和路徑，假設(shè)從源點(diǎn)V0出發(fā)并回到源點(diǎn)V0；

(2)調(diào)用三維數(shù)組$Ejz，用for循環(huán)分別將$new Vs中的V0→V1，V1→V2，?Vn-2→Vn-1的節(jié)點(diǎn)距離和節(jié)點(diǎn)路徑累加存入總距離$sum all和節(jié)點(diǎn)集合二維數(shù)組$programme；

(3)調(diào)用三維數(shù)組$Ejz，將Vn-1→V0兩節(jié)點(diǎn)的最短距離和最短路徑節(jié)點(diǎn)集合分別加入總距離$sum all和節(jié)點(diǎn)集合二維數(shù)組$programme。

2.4 多點(diǎn)最優(yōu)路徑組合計(jì)算結(jié)果

(1)Array(0,1,2,3,4)為選中所有的景點(diǎn)，得出最短路徑為13；

(2)最優(yōu)路徑節(jié)點(diǎn)集合為：V0→V3→V2→V1→V4→V1→V2→V0

(3)因?yàn)楣?jié)點(diǎn)V2屬于重復(fù)節(jié)點(diǎn)，故(0,1,3)和(0,1,2,3)兩種組合得到結(jié)果是一樣的。

3 結(jié)束語(yǔ)

通過利用PHP+MYSQL+APACHE技術(shù)設(shè)計(jì)和開發(fā)出了一個(gè)以大學(xué)生及其家人團(tuán)體為目標(biāo)客戶群的App，希望以此App構(gòu)建的平臺(tái)能給那些計(jì)劃旅行，對(duì)旅游線路組合信息檢索具有需求的學(xué)生或家長(zhǎng)用戶提供幫助。程序內(nèi)核是通過改進(jìn)Dijkstra算法構(gòu)建多點(diǎn)最優(yōu)路徑組合模型，并具體實(shí)現(xiàn)其應(yīng)用功能。經(jīng)過實(shí)測(cè)，能夠滿足20個(gè)節(jié)點(diǎn)以內(nèi)的多點(diǎn)賦權(quán)無(wú)向圖的優(yōu)化組合運(yùn)算。不僅在技術(shù)上取得突破，而且有效彌補(bǔ)了App應(yīng)用在該領(lǐng)域的空缺。

[1]Hofner P,Moller B.Dijkstra,FloydandWarshallmeetKleene[J].FormalAspectsof Computing,2012,24(4-6):459-476

[2]Chang JR,Jheng YH,Chang CH,et al.An Efficient Algorithm for Vehicle Guidance Combining Dijkstra and A* Algorithm with Fuzzy Inference Theory[J].Journal of Internet Technology,2015,16(2):189-200

[3]Payette S.Hopper and Dijkstra:Crisis,Revolution,and the Future of Programming[J].IEEE Annals of the History of Computing,2014,36(4):64-73

[4]Daylight EG,Wirth N,Hoare T,et al.The Dawn of Software Engineering:From Turing to Dijkstra[J].IEEE Annals of the History of Computing,2014,36(1):71-73

[5]王樹西,吳政學(xué).改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2012,39(5):223-228

[6]潘若愚,褚偉,楊善林.基于Dijkstra-PD-ACO算法的大城市公交線路優(yōu)化與評(píng)價(jià)方法研究[J].中國(guó)管理科學(xué),2015,23(9):106-115

The Application of Improved Dijkstra Algorithm in the Selection for Optimal Multi-point Traveling Routes－Taking the travelingApp for college students as a case

TANG Bin-wen,ZHUO Yu-jia,CHEN Xiao-qing
Chengyi College/Jimei University,Xiamen 361021,China

Along with the economical development and social progress in our country,people not only meet the increasingly rich material life but also pursuit the more spiritual pleasure,therefore,tourism industry is in the ascendant.In the face of the flourishing tourism online platform development,it is pressing how to provide visitors with more combination of the optimal traveling routes.Away from the traditional pattern of point-to-point navigation,this paper used the improved Dijkstra algorithm to design and develop an App with the recommending function for college students to fully use the existing mobile platform carriers to provide reasonable routes for tourists conveniently and quickly.

Dijkstra algorithm;traveling;App

U284.37

A

1000-2324(2016)06-0927-05

2016-02-10

2016-03-05

福建省2015年省級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目:大學(xué)生出游網(wǎng)絡(luò)服務(wù)平臺(tái)(201513471030)

唐彬文(1982-),男,碩士,講師,研究方向:管理信息系統(tǒng)和電子商務(wù).E-mail:tom414@jmu.edu.cn