基于Dijkstra算法的校園導航系統的設計與實現*

王特起，謝亞琴

（南京信息工程大學 電子與信息工程學院，江蘇 南京 210044）

0 引 言

隨著衛星導航定位系統的廣泛應用，人們對導航精度的要求也日益提高。導航系統的思想是把一些常見地理位置抽象為“點”，然后把位置與位置之間的路徑定義為邊，進而把大區域抽象為一個“圖”[1]，然后利用圖論中的最短路徑理論和相關算法就能計算出兩位置點的最短路徑。但這些點往往會被同等處理，如幾平方米的酒店與幾平方公里的大學都抽象為一點，無法代表實際規模。這樣若要定位某一小的具體位置時，依靠現有的導航系統（百度地圖、高德地圖）則存在較大誤差。

為了解決上述的較大區域內部任意兩個位置之間的最短路徑規劃問題，本文以校園區域為例，針對校園內位置點的最短路徑進行求解，首先利用Matlab軟件實現對校園內各點最短路徑的求解、經緯度坐標查詢、路徑顯示，重新計算可替代的最短路由以及設計用戶界面，然后結合現有求解區域最短路徑常用的A-star算法，將此系統計算的最短路徑的精度和效率與A-star算法的結果進行對比分析。

1 最優路徑算法

1.1 計算任意兩點距離

設一個點P的緯度和經度分別為αp，δp，另一個點Q的緯度和經度分別為αq，δq，以0度經線為基準，東經為正值，西經為負值，北緯取（90-當前緯度），南緯取（90+當前緯度），則經過上述處理過的兩點為由球面計算公式可以推導出P點與Q點之間的距離可以表示為：

其中，R為地球的平均半徑,取值為6 370 km。

1.2 權值矩陣寫入優化

在圖論中，每個地點可以近似表示為網絡中的一個節點，將位置、位置標號以及相鄰位置標號寫在矩陣的一行，利用稀疏矩陣進行數據的存取，節約存儲空間。

從存儲空間讀取區域內各點信息，根據每個點的鄰接點構建鄰接矩陣，如果兩個節點相鄰，則在鄰接矩陣中置1，反之置0；再利用式（1）求得距離，將該距離賦給鄰接矩陣中為1的值，就得到最短路徑算法中的權值矩陣。計算中將得到的矩陣保留在云端空間，方便隨時直接調用，節約算法時間。

1.3 最短路徑算法

要求解指定節點Vs到圖中其它任意一個節點Vj的最短路徑，Dijkstra算法[3]（以下簡稱D算法）的具體思想如下：

首先，將上述權值矩陣轉化為帶權圖G，且G=(V,E)，其中，E表示所有節點組成的集合，E表示所有邊組成的集合。節點集V可以分為兩組：置定節點集Gp和未置定節點集V-Gp。Gp表示指定點Vs到這些節點的路徑為最短，初始時，Dp={Vs}未置定節點集則表示指定點Vs到這些節點的距離是暫時的。

其次，計算指定點Vs到未置定節點集V-Gp中所有其它節點之間的距離，并找出距離Vs最短的那個節點Vj，并將節點Vj劃歸到Gp中，此時，Gp={Vs-Vj}。在計算各未置定節點的最短徑時，是將Gp中的節點作為轉接點，如計算Vs到Vj的徑長為Wj（Wj表示從Vs到Vj僅經過Gp中的節點作為轉接點所求得的該次的最短路徑長度）時，若該次計算的徑長小于Wi（Wi表示上一次劃分到Gp中的節點Vi到Vs的最短路徑），則更新徑長，否則徑長不變。

最后，當V-Gp最終成為空集，同時Gp=V，即求得Vs到所有其他節點的最短路徑。算法實現流程如下圖1所示。

2 校園導航系統的設計與實現

采用GUI設計圖形用戶界面，初始登錄界面如圖2所示。利用gplot函數[4]（參數分別為鄰接矩陣和坐標）可以繪出校園路徑圖。將求出的最短路徑，利用plot命令進行畫圖（參數為經度和緯度），并將最短路徑用紅線標出(如圖3所示)，從而在坐標系中可以直觀地看出起終點的最短路徑。將地點名稱，距離標在圖中，并顯示D算法得到的最短路徑的標號、對應的地點、最短距離以及算法運行時間。

關于坐標位置查詢，我們讀取坐標信息存于矩陣中，結合輸入標號，我們可以顯示坐標信息（即經緯度）。在計算最短可替代路由時，先輸入不可通行的節點標號，將不可通行的點在權值矩陣置無窮，再次執行Dijkstra算法，即可獲得可替代的最短路徑、最短距離和算法時間，并用紅線加粗線標出最短路徑，綠色虛線標注不可通行的路徑（如圖4所示）。

2.1 導航系統操作說明

首先，當點擊最短路由計算按鈕后，出現進度條，完成計算后，界面會顯示最短路徑的標號、地點、最短距離、算法運行時間以及最短路徑在圖中的顯示；其次，當點擊坐標位置查詢按鈕后，會將相應地點的經緯度顯示在文本框中；第三，輸入不可相互通行的節點標號，點擊替代最短路由計算按鈕后，界面將顯示最短路徑，以及不可通行的路徑。最后，將程序打包，生成可執行文件。所用地點及其對應標號表如表1所示。

圖1 D算法的實現流程圖

圖2 系統初始界面圖

圖3 最短路徑計算界面圖

圖4 替代路徑計算界面圖

表1 地點名稱與標號對應

校園導航系統實現流程如圖5所示。

2.2 圖形用戶界面設計

針對南京信息工程大學的校園地圖，利用Matlab軟件中的GUI功能，設計了如圖3所示的友好用戶界面，用戶可以自由選擇起點和終點。

點擊最短路由計算按鈕，及點擊坐標位置查詢按鈕后（例：1.東門，35.小南門的經緯度信息），結果如圖3所示。

圖5 校園導航系統實現流程圖

界面顯示：

1.東門到35.小南門的最短路徑為：

標號顯示：1-＞2-＞3-＞14-＞15-＞18-＞22-＞21-＞30-＞31-＞33-＞34-＞35。

標號對應的地點名稱顯示：東門—雷丁—群英橋—氣象樓—文德樓—訓練館—尚賢樓—老氣象門—門診部—大禮堂—農業銀行—郵局—小南門。

1.東 門 的 經 緯 度 為（32.2111° N，118.7328°E）。

35.小南門的經緯度為（32.2064°N，118.7222°E）。

點擊替代最短路由計算按鈕（14.氣象樓與3.群英橋因某種原因不能通行，輸入兩節點標號，點擊按鈕），結果如圖4所示。

界面顯示：

不允許通行的節點標號為3，14。

1.東門到35.小南門的最短路徑為：

標號顯示：1-＞5-＞6-＞7-＞8-＞12-＞13-＞15-＞18-＞22-＞21-＞30-＞31-＞33-＞34-＞35。

標號對應的地點名稱顯示：東門—足球場—體育館—財務處—創業園—東苑籃球場—暉園—文德樓—訓練館—尚賢樓—老氣象門—門診部—大禮堂—農業銀行—郵局—小南門。

不可通行路徑：3.群英橋-＞14.氣象樓，不能通行（虛線標識）

2.3 算法仿真結果與分析

目前經常采用A-star算法[5]來計算區域內最短路徑，因為此算法更適用于單點到單點的尋徑，而在校園區域應用中，常出現突發情況，這時候我們需要使用單點到多點的尋徑方式，會大大節省算法的計算時間。

為此我們采用不同地點組合，進行最短路徑計算，經過統計，與A-star算法的執行時間以及不同地點組合下最短路徑的長度進行比較，仿真結果表明，D算法可以有效提高執行效率。不同地點組合下最短路徑的長度的比較圖如圖6所示。其中標號與名稱對應關系如表1所示。

再以相同的最短路徑作為標準，比較算法的執行時間，仿真算法表明，計算相同距離，D算法的效率高于A-star算法。在起點與終點間距離不同的情況下，算法執行時間的比較圖如圖7所示。

相比于A-star算法，在復雜情況的區域內，采用D算法能夠在保證精度的前提下，提高算法的最短路徑求解時間，且對于不同組合下，D算法求解的路徑長度更短。

圖6 最短路徑的比較圖

圖7 不同距離下算法執行時間比較圖

3 結 語

本文以Dijkstra算法為基礎，針對區域內位置點的最短路徑求解，改進區域內位置信息的讀取方法，實現校園內位置的最短路徑顯示，提供校園基本設施位置查詢，如學校內部農業銀行的位置、具體教學樓位置、手機營業廳等，并且當某些道路因某種原因無法通行時，重新計算可替代的最短路由。校園內路徑導航系統有很好的應用前景，既可以為用戶帶來方便，也為學校向更智能化的發展提供技術支持，同時仿真結果表明，該算法與常用的A-star算法相比，計算路徑更短，執行效率更快，呈現出的最短結果更加直觀，有效滿足校園用戶導航的需求。