基于Dijkstra算法的北京景點旅游路徑規劃研究

葉小芹

（合肥城市學院機械與電氣工程學院，安徽合肥 230000）

0 引言

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

1 Dijkstra算法介紹

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

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

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

2 Dijkstra算法思想

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

3 Dijkstra算法具體步驟

Dijkstra算法具體步驟如下：

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

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

第三步，以K作為新的基點，對S中各結點之間弧的權值進行調整，此時，如果源點S1 經過頂點K 到達頂點M 的距離小于S1 直達M 的距離，那么就調整頂點M的弧權值，即d＜S1,M＞=d＜S1,K＞+d＜K,M＞。

第四步，依次類推，反復執行以上第二步和第三步，直到集合S中容納了全部頂點[6]。

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

圖1 北京部分景點旅游線路圖

表3 Dijkstra算法應用實例

4 Dijkstra 算法在北京景點旅游線路規劃中的應用

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

表1 北京部分景點代碼

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

表2 北京部分景點的距離矩陣

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

5 Dijkstra算法改進

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

圖2 改進后的Dijkstra算法流程圖

6 結束語

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