基于Dijkstra算法的旅游路線規劃研究

吳昕宇　羅雪穎

摘要：考慮游客不會在游覽路線上往返、游覽路線不會重復，基于此，本文采用Dijkstra算法解決這個問題。首先，運用圖論知識，將8個景點（包括景石）看成一個賦權無向圖，各景點為圖的頂點，兩景點之間步行最短路線為圖相應兩頂點問的邊，距離為圖兩頂點問邊的權值，得到賦權圖。然后，用Dijkstra算法即可求解最短路線。

關鍵詞：Dijkstra算法圖論知識最短路線

引言

在物質生活條件得到極大發展的今天，人們越來越追求精神文明的建設，越來越多的人愛上旅行而背上背包去旅行。這就致使旅游資源供不應求，一到假期便游人如織，在這樣的情況下，規劃游客的最優路線，規劃游客的觀光時間，最大限度地利用旅游資源便十分重要。

2010年，江蘇省啟動潘安湖土地整理項目，在一片廢墟上建成了一個6500畝湖面的國家級水利風景區。2016年，賈汪被列為“國家全域旅游示范區”首批創建單位。本文選取潘安湖景區的部分景點，完成徐州潘安湖風景區游覽最短路線設計問題。

1模型建立

從景石出發步行游覽①游客服務中心，②陽光草坪，③森林小劇場，④兒童科普體驗區，⑤兒童戲水場，⑥濕地博物館，⑦濕地商業街。建立數學模型，找出所有景點至少觀光1次的距離最短的路線，計算該路線的長度。

本問題要求設計從景石出發，經過①②③④⑤⑥各景點，最終到達⑦濕地商業街，① ⑥所有景點至少觀光1次的距離最短的路線。在實際旅游觀光中，游客在各景點的旅游路線不會重復，而且游客不會在旅游路線上往返，基于此，本文將采用Dijkstra算法來解決此問題。

2.1無向圖定義

一個無向圖G是由一個非空有限集合V（G）和V（G）中某些元素的無序對集合E（G）構成的二元組，記為G=（v（G），E（G））。其中，V（G）={v1，v2，L，v，）稱為圖G的頂點集或節點集，V（G）中的每一個元素

邊上賦權的無向圖稱為賦權無向圖或無向網絡，題目所給出的各景點之間步行最短距離即為無向圖邊上權值。

以各景點為圖G的頂點，兩景點之間步行最短路線為圖G相應兩頂點間的邊，得到圖G。對G的每一邊e，賦以一個實數w（e），即景點之間步行最短距離，稱為e的權，得到賦權圖G。G的子圖的權是指子圖的各邊的權和。

問題便演化為求賦權圖G中指定的兩個頂點uo，vo間的具有最小權的軌。這條軌叫做uo，vo間的距離，記作d（uo，vo）。

2模型求解

本文采用Dijkstra算法編程求解。Dijkstra算法也稱為雙標號法。所謂雙標號，也就是對圖中的點vf賦予兩個標號（，（u），1）：第一個標號（p（v1）表示從起點V1到V1的最短路的長度，第二個標號λ3表示在v1到v1的最短路上V1前面一個鄰點的下標，即用來表示路徑，從而可對終點到始點進行反向追蹤，找到U1到vn的最短路。Dijkstra算法適用于每條邊的權數都大于或等于零的情況。下面是Dijkstra算法的內容：

按距離uo從近到遠為順序，依次求uo到G各頂點的最短路線距離，直至。

3模型分析

本文建立的最短路線尋求模型可以推廣應用于交通運輸、車輛路徑規劃、飛機航線安排、城市規劃、經濟管理、物流貨物配送、通訊與網絡技術、計算機科學、信息技術與災害應急調度等領域。如交通查詢系統中需要給用戶提供多條可供選擇的最短路徑。

參考文獻

[1]史峰，王輝等.MATLAB智能算法30個案例分析[D].北京航空航天大學出版社，178-197.

[2]劉雪塵，基于博弈論的多模式動態路徑規劃技術研究[D]，吉林大學，2017.