基于Dijkstra算法的校園導(dǎo)航系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)*

王特起，謝亞琴

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

0 引 言

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

為了解決上述的較大區(qū)域內(nèi)部任意兩個(gè)位置之間的最短路徑規(guī)劃問題，本文以校園區(qū)域?yàn)槔槍?duì)校園內(nèi)位置點(diǎn)的最短路徑進(jìn)行求解，首先利用Matlab軟件實(shí)現(xiàn)對(duì)校園內(nèi)各點(diǎn)最短路徑的求解、經(jīng)緯度坐標(biāo)查詢、路徑顯示，重新計(jì)算可替代的最短路由以及設(shè)計(jì)用戶界面，然后結(jié)合現(xiàn)有求解區(qū)域最短路徑常用的A-star算法，將此系統(tǒng)計(jì)算的最短路徑的精度和效率與A-star算法的結(jié)果進(jìn)行對(duì)比分析。

1 最優(yōu)路徑算法

1.1 計(jì)算任意兩點(diǎn)距離

設(shè)一個(gè)點(diǎn)P的緯度和經(jīng)度分別為αp，δp，另一個(gè)點(diǎn)Q的緯度和經(jīng)度分別為αq，δq，以0度經(jīng)線為基準(zhǔn)，東經(jīng)為正值，西經(jīng)為負(fù)值，北緯取（90-當(dāng)前緯度），南緯取（90+當(dāng)前緯度），則經(jīng)過上述處理過的兩點(diǎn)為由球面計(jì)算公式可以推導(dǎo)出P點(diǎn)與Q點(diǎn)之間的距離可以表示為：

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

1.2 權(quán)值矩陣寫入優(yōu)化

在圖論中，每個(gè)地點(diǎn)可以近似表示為網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，將位置、位置標(biāo)號(hào)以及相鄰位置標(biāo)號(hào)寫在矩陣的一行，利用稀疏矩陣進(jìn)行數(shù)據(jù)的存取，節(jié)約存儲(chǔ)空間。

從存儲(chǔ)空間讀取區(qū)域內(nèi)各點(diǎn)信息，根據(jù)每個(gè)點(diǎn)的鄰接點(diǎn)構(gòu)建鄰接矩陣，如果兩個(gè)節(jié)點(diǎn)相鄰，則在鄰接矩陣中置1，反之置0；再利用式（1）求得距離，將該距離賦給鄰接矩陣中為1的值，就得到最短路徑算法中的權(quán)值矩陣。計(jì)算中將得到的矩陣保留在云端空間，方便隨時(shí)直接調(diào)用，節(jié)約算法時(shí)間。

1.3 最短路徑算法

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

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

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

最后，當(dāng)V-Gp最終成為空集，同時(shí)Gp=V，即求得Vs到所有其他節(jié)點(diǎn)的最短路徑。算法實(shí)現(xiàn)流程如下圖1所示。

2 校園導(dǎo)航系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

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

關(guān)于坐標(biāo)位置查詢，我們讀取坐標(biāo)信息存于矩陣中，結(jié)合輸入標(biāo)號(hào)，我們可以顯示坐標(biāo)信息（即經(jīng)緯度）。在計(jì)算最短可替代路由時(shí)，先輸入不可通行的節(jié)點(diǎn)標(biāo)號(hào)，將不可通行的點(diǎn)在權(quán)值矩陣置無窮，再次執(zhí)行Dijkstra算法，即可獲得可替代的最短路徑、最短距離和算法時(shí)間，并用紅線加粗線標(biāo)出最短路徑，綠色虛線標(biāo)注不可通行的路徑（如圖4所示）。

2.1 導(dǎo)航系統(tǒng)操作說明

首先，當(dāng)點(diǎn)擊最短路由計(jì)算按鈕后，出現(xiàn)進(jìn)度條，完成計(jì)算后，界面會(huì)顯示最短路徑的標(biāo)號(hào)、地點(diǎn)、最短距離、算法運(yùn)行時(shí)間以及最短路徑在圖中的顯示；其次，當(dāng)點(diǎn)擊坐標(biāo)位置查詢按鈕后，會(huì)將相應(yīng)地點(diǎn)的經(jīng)緯度顯示在文本框中；第三，輸入不可相互通行的節(jié)點(diǎn)標(biāo)號(hào)，點(diǎn)擊替代最短路由計(jì)算按鈕后，界面將顯示最短路徑，以及不可通行的路徑。最后，將程序打包，生成可執(zhí)行文件。所用地點(diǎn)及其對(duì)應(yīng)標(biāo)號(hào)表如表1所示。

圖1 D算法的實(shí)現(xiàn)流程圖

圖2 系統(tǒng)初始界面圖

圖3 最短路徑計(jì)算界面圖

圖4 替代路徑計(jì)算界面圖

表1 地點(diǎn)名稱與標(biāo)號(hào)對(duì)應(yīng)

校園導(dǎo)航系統(tǒng)實(shí)現(xiàn)流程如圖5所示。

2.2 圖形用戶界面設(shè)計(jì)

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

點(diǎn)擊最短路由計(jì)算按鈕，及點(diǎn)擊坐標(biāo)位置查詢按鈕后（例：1.東門，35.小南門的經(jīng)緯度信息），結(jié)果如圖3所示。

圖5 校園導(dǎo)航系統(tǒng)實(shí)現(xiàn)流程圖

界面顯示：

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

標(biāo)號(hào)顯示：1-＞2-＞3-＞14-＞15-＞18-＞22-＞21-＞30-＞31-＞33-＞34-＞35。

標(biāo)號(hào)對(duì)應(yīng)的地點(diǎn)名稱顯示：東門—雷丁—群英橋—?dú)庀髽恰牡聵恰?xùn)練館—尚賢樓—老氣象門—門診部—大禮堂—農(nóng)業(yè)銀行—郵局—小南門。

1.東 門 的 經(jīng) 緯 度 為（32.2111° N，118.7328°E）。

35.小南門的經(jīng)緯度為（32.2064°N，118.7222°E）。

點(diǎn)擊替代最短路由計(jì)算按鈕（14.氣象樓與3.群英橋因某種原因不能通行，輸入兩節(jié)點(diǎn)標(biāo)號(hào)，點(diǎn)擊按鈕），結(jié)果如圖4所示。

界面顯示：

不允許通行的節(jié)點(diǎn)標(biāo)號(hào)為3，14。

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

標(biāo)號(hào)顯示：1-＞5-＞6-＞7-＞8-＞12-＞13-＞15-＞18-＞22-＞21-＞30-＞31-＞33-＞34-＞35。

標(biāo)號(hào)對(duì)應(yīng)的地點(diǎn)名稱顯示：東門—足球場(chǎng)—體育館—財(cái)務(wù)處—?jiǎng)?chuàng)業(yè)園—東苑籃球場(chǎng)—暉園—文德樓—訓(xùn)練館—尚賢樓—老氣象門—門診部—大禮堂—農(nóng)業(yè)銀行—郵局—小南門。

不可通行路徑：3.群英橋-＞14.氣象樓，不能通行（虛線標(biāo)識(shí)）

2.3 算法仿真結(jié)果與分析

目前經(jīng)常采用A-star算法[5]來計(jì)算區(qū)域內(nèi)最短路徑，因?yàn)榇怂惴ǜm用于單點(diǎn)到單點(diǎn)的尋徑，而在校園區(qū)域應(yīng)用中，常出現(xiàn)突發(fā)情況，這時(shí)候我們需要使用單點(diǎn)到多點(diǎn)的尋徑方式，會(huì)大大節(jié)省算法的計(jì)算時(shí)間。

為此我們采用不同地點(diǎn)組合，進(jìn)行最短路徑計(jì)算，經(jīng)過統(tǒng)計(jì)，與A-star算法的執(zhí)行時(shí)間以及不同地點(diǎn)組合下最短路徑的長度進(jìn)行比較，仿真結(jié)果表明，D算法可以有效提高執(zhí)行效率。不同地點(diǎn)組合下最短路徑的長度的比較圖如圖6所示。其中標(biāo)號(hào)與名稱對(duì)應(yīng)關(guān)系如表1所示。

再以相同的最短路徑作為標(biāo)準(zhǔn)，比較算法的執(zhí)行時(shí)間，仿真算法表明，計(jì)算相同距離，D算法的效率高于A-star算法。在起點(diǎn)與終點(diǎn)間距離不同的情況下，算法執(zhí)行時(shí)間的比較圖如圖7所示。

相比于A-star算法，在復(fù)雜情況的區(qū)域內(nèi)，采用D算法能夠在保證精度的前提下，提高算法的最短路徑求解時(shí)間，且對(duì)于不同組合下，D算法求解的路徑長度更短。

圖6 最短路徑的比較圖

圖7 不同距離下算法執(zhí)行時(shí)間比較圖

3 結(jié) 語

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