基于Dijkstra算法的北京景點(diǎn)旅游路徑規(guī)劃研究

葉小芹

（合肥城市學(xué)院機(jī)械與電氣工程學(xué)院，安徽合肥 230000）

0 引言

北京作為中國的首都和歷史古都，景點(diǎn)非常豐富，很多景點(diǎn)都具有特定的地質(zhì)地貌、生態(tài)環(huán)境，尤其是悠久的歷史、燦爛的文化吸引了很多游客，是中國的優(yōu)秀旅游城市。每年去北京旅游的游客不計(jì)其數(shù)，以2022 年春節(jié)假期為例，北京景區(qū)累計(jì)接納游客約758.3萬人次，受新冠疫情影響，雖比2021年同比減少了2.9%，但比2020年增長3.6倍。面對如此巨大的游客數(shù)量，針對北京景點(diǎn)多、面積大、人流量大的特點(diǎn)，為了給游客更加舒適的體驗(yàn)，論文基于北京的幾個著名景點(diǎn)，借助Dijkstra算法進(jìn)行了旅游路線規(guī)劃研究，能為智能旅游App的設(shè)計(jì)打下良好的基礎(chǔ)。

1 Dijkstra算法介紹

在城市交通問題中，如果想找到城市A 和城市B之間一條中轉(zhuǎn)次數(shù)最少的路線，即從頂點(diǎn)A 到頂點(diǎn)B所含的邊的數(shù)目最少的路徑，只需要從頂點(diǎn)A出發(fā)對該圖進(jìn)行廣度優(yōu)先搜索遍歷[1]，一旦遇到頂點(diǎn)B 就可以停止，這是最簡單的圖的最短路徑問題。但在很多情況下，還需要解決的問題是要找到城市之間的最短線路或者城市之間最節(jié)省的交通費(fèi)用等問題，此時路徑長度的度量就不再是路徑上的數(shù)目，而是路徑上的權(quán)值，即它所代表的相關(guān)信息，例如兩個城市之間的距離或者途經(jīng)所需的時間或者交通費(fèi)用等，這類問題設(shè)計(jì)的都是最短路徑問題。

例如從西安出發(fā)準(zhǔn)備去北京、上海、蘭州，該如何找到最佳的出行方案呢？也就是找到從西安出發(fā)到達(dá)三個目的城市的帶權(quán)路徑長度最短的那個路徑方案。

最短路徑問題一般分為兩種情況：單源最短路徑問題和每一對頂點(diǎn)之間的最短路徑問題，常用的解決這兩種問題的算法分別是迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)[2]，而解決旅游線路問題，主要是單源最短路徑，主要應(yīng)用Dijkstra算法。

2 Dijkstra算法思想

Dijkstra 算法是一種按照路徑長度遞增的次序，分別產(chǎn)生到各頂點(diǎn)最短路徑的一種貪心算法，該算法把帶權(quán)圖中的所有頂點(diǎn)分成兩個集合，S 和V-S，S 中存放已經(jīng)找到最短路徑的頂點(diǎn)，V-S中存放當(dāng)前還沒有找到最短路徑的頂點(diǎn)[3]，算法將按照最短路徑長度遞增的順序逐個將V-S 集合中元素加入S 集合中，直到所有的頂點(diǎn)都進(jìn)入了S集合為止，其實(shí)這里用到一個很重要的定理，下一條最短路徑或者弧即v0 到vi，或者中間經(jīng)過S集合中的某個頂點(diǎn)，而后到達(dá)vi 的路徑。這條定理可以用反證法來證明，假設(shè)下一條最短路徑上有一個頂點(diǎn)vj是不在S集合中，即此路即為v0到vj再到vi，顯然從v0到vj長度是小于v0到vj再到vi的長度，故下一條最短路徑應(yīng)該為v0 到vj，這就與題設(shè)的下一條最短路徑v0到vj再到vi是相矛盾的，所以下一條最短路徑上不可能有不在S 中的頂點(diǎn)vj，其中第一條最短路徑是從源點(diǎn)v0 到各點(diǎn)路徑長度集合中長度最短的那一條。

3 Dijkstra算法具體步驟

Dijkstra算法具體步驟如下：

第一步，對于網(wǎng)P=（V，E），將P 中的頂點(diǎn)分為兩組，S和V-S，其中S為已求出的最短路徑的終點(diǎn)集合，初始時僅包含S1，V-S代表尚未求出的最短路徑的頂點(diǎn)集合，S 中各頂點(diǎn)之間的距離記為d，在頂點(diǎn)集合S中，如果存在弧＜S1,Si＞,則S1到Si之間的距離d＜S1,Si＞即其上的權(quán)值，否則記為無窮大[4]。

第二步，從V-S 中選取一個最小距離，將其關(guān)聯(lián)的頂點(diǎn)K 加入S 中，且d＜S1,K＞為S1 到k的最短距離[5]。

第三步，以K作為新的基點(diǎn)，對S中各結(jié)點(diǎn)之間弧的權(quán)值進(jìn)行調(diào)整，此時，如果源點(diǎn)S1 經(jīng)過頂點(diǎn)K 到達(dá)頂點(diǎn)M 的距離小于S1 直達(dá)M 的距離，那么就調(diào)整頂點(diǎn)M的弧權(quán)值，即d＜S1,M＞=d＜S1,K＞+d＜K,M＞。

第四步，依次類推，反復(fù)執(zhí)行以上第二步和第三步，直到集合S中容納了全部頂點(diǎn)[6]。

以圖1中的北京景點(diǎn)旅游線路圖為例，運(yùn)用Dijkstra 算法求得從天安門廣場S1 出發(fā)到其余各頂點(diǎn)的最短路徑，具體過程如表3所示。

圖1 北京部分景點(diǎn)旅游線路圖

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

4 Dijkstra 算法在北京景點(diǎn)旅游線路規(guī)劃中的應(yīng)用

在基于Dijkstra 算法對旅游線路進(jìn)行規(guī)劃時，通常采用圖形結(jié)構(gòu)來表示北京景點(diǎn)中的實(shí)際路徑結(jié)構(gòu)，本文選取了北京的7個著名景點(diǎn)作為研究對象，這些景點(diǎn)的旅游線路圖如圖1所示，其中每個景點(diǎn)均用代碼表示，具體代碼對照表如表1所示。

表1 北京部分景點(diǎn)代碼

每個景點(diǎn)之間路線是互通的，各景點(diǎn)之間的距離信息如表2所示，以公里為單位。

表2 北京部分景點(diǎn)的距離矩陣

為了更好地記錄整個求解過程，設(shè)置表格來記錄，列代表每一次的求解過程，即每一條最短路徑的產(chǎn)生，行代表單源點(diǎn)到達(dá)目標(biāo)點(diǎn)，矩陣中的元素值來代表單源點(diǎn)到達(dá)目標(biāo)點(diǎn)的路徑長度，為了更好地記錄這個路徑，同時記錄了路徑上的頂點(diǎn)，比如在這個無向網(wǎng)中，以S1作為出發(fā)點(diǎn)，如果采用鄰接矩陣進(jìn)行存儲，那么掃描S1所在的行，就可以知道S1直接相鄰的頂點(diǎn)有哪些[7]，可以看到，有S2到S7，路徑長度分別為5、20、7、79、48、10，顯然第一次可以選擇的就是5這條最短路徑，對應(yīng)的目標(biāo)點(diǎn)就是S2，即第一條最短路徑是從出發(fā)點(diǎn)S1 到S2，路徑長度為5，這條路徑就是S1到S2的最短路徑；接下來通過更新迭代來尋找第二條最短路徑，根據(jù)剛剛介紹的基本思想，第二條最短路徑要么來源于和S1直連的那些頂點(diǎn)，一條邊，要么來自剛剛已經(jīng)找到的從S1經(jīng)過已求得的最短路徑頂點(diǎn)S2，再到達(dá)目標(biāo)點(diǎn)的兩條邊來組成，所以要來考查一下頂點(diǎn)S2,它可以鄰接哪些頂點(diǎn)，掃描S2所在的行，除了S1，與S2 直連的頂點(diǎn)有頂點(diǎn)S3 到S7，其中S1 通過S2 中轉(zhuǎn)到達(dá)S5 的路徑長度是5+71=76，比S1 直達(dá)S5的路徑長度短，所以要更新替換，替換路徑為S1借助于S2 到S5，路徑長度為76，其他的不變，第二條最短路徑就是在20、7、76、48、10 這幾個中進(jìn)行選擇，肯定選擇7，所以找到第二條最短路徑是從S1到S4,路徑長度為7,這條路徑就是S1 到S4 的最短路徑；繼續(xù)找第三條最短路徑，它或者還是從源點(diǎn)到某一個目標(biāo)點(diǎn)直達(dá)的，或者是從源點(diǎn)經(jīng)過已求得的最短路徑的頂點(diǎn)S4再到達(dá)某個目標(biāo)點(diǎn)的，因此要來考查頂點(diǎn)S4，除去S1和S2，發(fā)現(xiàn)S4 直連出去的頂點(diǎn)有S3、S5、S6、S7，之前出發(fā)點(diǎn)S1 到S5 是經(jīng)過S2 中轉(zhuǎn)的，路徑長度為76，現(xiàn)在經(jīng)過S4 中轉(zhuǎn)，路徑長度只需要7+60=67，所以更新替換，另外之前出發(fā)點(diǎn)S1到S6是直達(dá)的48，現(xiàn)在經(jīng)過S4 中轉(zhuǎn)只需要7+40=47，所以也更新替換，此時可以選擇的路徑長度有20、67、47、10，所以選擇10 這條，至此找到了第三條最短路徑，從S1出發(fā)到S7，路徑長度為10,這條路徑就是S1到S7的最短路徑；接下來找第四條最短路徑，考查頂點(diǎn)S7，發(fā)現(xiàn)沒有通過S7中轉(zhuǎn)可以縮短路徑的頂點(diǎn)，此時路徑長度就在20、67、47中選擇了，所以選擇20這一條，即找到第4條最短路徑，S1 到S3，路徑長度為20，這條路徑就是S1 到S3 的最短路徑；接下來同理，第五條最短路徑是S1經(jīng)過S4中轉(zhuǎn)，再到S6，路徑長度47，最后一條，第六條最短路徑是S1經(jīng)過S4中轉(zhuǎn)再到S5，路徑長度是67，至此求得了出發(fā)點(diǎn)S1到其余6個頂點(diǎn)的帶權(quán)最短路徑長度了。

5 Dijkstra算法改進(jìn)

在對北京景點(diǎn)的路線進(jìn)行規(guī)劃而設(shè)計(jì)出最短路徑時，結(jié)合北京部分景點(diǎn)的旅游線路圖可以看出，圖中的結(jié)點(diǎn)個數(shù)并不多，為了便于實(shí)現(xiàn)實(shí)際需求，可以對此算法進(jìn)行改進(jìn)，其改進(jìn)的基本思想如下：假設(shè)以S1作為起始點(diǎn)，以S6作為終點(diǎn)的最短路徑已經(jīng)求出，其路徑為S1-S4-S6，則如果需要尋求從結(jié)點(diǎn)S4 出發(fā)到結(jié)點(diǎn)S6的最短路徑時，那么就可以參照已經(jīng)找到的S1 到S6 的最短路徑直接求出S4 到S6 的最短路徑為S4-S6，即不用重新使用Dijkstra算法求。所以在之前求S1到各頂點(diǎn)的最短路徑過程中，要對之前求出的結(jié)果進(jìn)行保存，這樣才能通過已經(jīng)存儲的信息迅速得到從源點(diǎn)到目的點(diǎn)的最短路徑[8]。改進(jìn)后的Dijkstra 算法流程圖如圖2 所示，其中Ds 為始點(diǎn)s 到其他結(jié)點(diǎn)的距離，初始狀態(tài)下為0；Fs表示從源點(diǎn)s到某一目的結(jié)點(diǎn)p的最短路徑中的前一結(jié)點(diǎn)；Di表示檢驗(yàn)從所有已標(biāo)記的結(jié)點(diǎn)e到其他未標(biāo)記的結(jié)點(diǎn)f的距離，w（e，f）表示從結(jié)點(diǎn)e到f的距離值。

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

6 結(jié)束語

論文基于Dijkstra 算法對北京部分景點(diǎn)旅游路線進(jìn)行了規(guī)劃，首先通過Dijkstra 算法得出了從源點(diǎn)到達(dá)各景點(diǎn)的最短路徑，然后又對此算法進(jìn)行改進(jìn)，通過改進(jìn)后的算法，能快速得出后續(xù)結(jié)點(diǎn)的最短路徑，并給出了流程圖，這樣能提升旅游效率。論文建立的最短路徑算法可應(yīng)用于各行各業(yè)，尤其是在旅游行業(yè)中顯得尤為突出，為了便于游客出行，提升旅游質(zhì)量，找出高效率的旅游路線非常重要，這樣才能節(jié)約旅游成本，耗費(fèi)最短時間，使中國旅游行業(yè)高質(zhì)量發(fā)展。