校園導(dǎo)航系統(tǒng)中最短路徑算法的研究

摘 要：本項(xiàng)目主要研究了迪杰斯算法在校園虛擬導(dǎo)航中的應(yīng)用，該系統(tǒng)能夠?qū)崿F(xiàn)搜索現(xiàn)有校園地點(diǎn)的信息及求解校內(nèi)任意兩場(chǎng)所問(wèn)的最短路徑。

關(guān)鍵詞：校園導(dǎo)航；迪杰斯算法；最短路徑

中圖分類號(hào)：TP311.5

隨著新技術(shù)、新領(lǐng)域的不斷拓展，新的學(xué)科在不斷涌現(xiàn)，高校里面的各二級(jí)學(xué)院、各部門也相應(yīng)的不斷增加，因此學(xué)校的規(guī)模也在不斷擴(kuò)大，校園面積也在成倍的增長(zhǎng)，教學(xué)區(qū)，辦公區(qū)，生活區(qū)，活動(dòng)區(qū)等在地理位置相對(duì)變得疏遠(yuǎn)，那么跨區(qū)域活動(dòng)在區(qū)間往復(fù)的時(shí)間成本越來(lái)越高，如果中間稍有耽誤，將不能按照預(yù)定時(shí)問(wèn)到達(dá)目的地，給師生的工作學(xué)習(xí)帶來(lái)不便，影響了工作效率。如何使師生在校園內(nèi)可以通過(guò)移動(dòng)和通訊設(shè)備快速查找到相關(guān)建筑的位置和功能呢。要想在最短的時(shí)間內(nèi)到達(dá)所去的地點(diǎn)，就需要獲得從你所在的位置到將去的地點(diǎn)間的最短路徑。如果得到的兩地點(diǎn)間的路徑是最短的，那么同樣的情況下行走所需的時(shí)間就是最少的。

基于開(kāi)發(fā)背景下，本項(xiàng)目主要研究了迪杰斯算法在校園虛擬導(dǎo)航中的應(yīng)用，主要研究了導(dǎo)航中最短路徑的實(shí)現(xiàn)，以韶關(guān)學(xué)院為題材，為大眾用戶提供搜索現(xiàn)有校園地點(diǎn)的信息及求解校內(nèi)任意兩場(chǎng)所問(wèn)的最短路徑。結(jié)果以Flash示意圖形式顯示在屏幕上。系統(tǒng)設(shè)計(jì)采用了迪杰斯特拉算法和圖形函數(shù)，以便用戶更容易理解。

1 迪杰斯算法

Dijkstra（迪杰斯特拉）算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑[1]。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN，CLOSE表的方式，在本系統(tǒng)中均采用永久和臨時(shí)標(biāo)號(hào)的方式。注意該算法要求圖中不存在負(fù)權(quán)邊[2]。如圖1所示.

2 問(wèn)題的描述

2.1 定義校園地圖上帶權(quán)無(wú)向圖

要在獲取校園地圖中任意兩個(gè)地點(diǎn)的最短路徑，需要先將地圖中各個(gè)部門及地點(diǎn)抽向成一個(gè)帶權(quán)無(wú)向圖H，如圖2所示。每個(gè)頂點(diǎn)代表校園內(nèi)的地點(diǎn)或部門，頂點(diǎn)與頂點(diǎn)之間的邊為權(quán)值，代表兩個(gè)部門或地點(diǎn)間的距離。帶權(quán)無(wú)向圖建立后，就可以采用迪杰斯算法，求得任意兩個(gè)頂點(diǎn)間的最小距離，即是系統(tǒng)所要求得的最短路徑[3]。

2.2 帶權(quán)無(wú)向圖在系統(tǒng)中的存儲(chǔ)

當(dāng)用戶激活查詢后，系統(tǒng)根據(jù)用戶輸入的地點(diǎn)，生成帶權(quán)無(wú)向圖，存儲(chǔ)在系統(tǒng)中，進(jìn)行計(jì)算。根據(jù)需求，本系統(tǒng)采用鄰接多重表對(duì)帶權(quán)無(wú)向圖進(jìn)行存儲(chǔ)。在鄰接多重表中，每一個(gè)結(jié)點(diǎn)（部門或地點(diǎn)）用一個(gè)頂點(diǎn)表示，每一條邊也用一個(gè)頂點(diǎn)表示。對(duì)根據(jù)校園地圖的帶權(quán)無(wú)向圖生成的鄰接多重表如圖3所示，由于校園內(nèi)地點(diǎn)和部門較多，此處只是局部的鄰接多重表[4]。

3 概要設(shè)計(jì)

3.1 程序設(shè)計(jì)思想

實(shí)現(xiàn)任意兩地間最短路徑的尋找，并向用戶呈現(xiàn)結(jié)構(gòu)。由于校園線路可直接抽象為無(wú)向圖。所以，對(duì)于無(wú)向圖的最短路徑尋找，采用迪杰斯算法最適合不過(guò)。程序流程圖如圖4所示：

3.2 具體實(shí)現(xiàn)過(guò)程

在系統(tǒng)中定義兩個(gè)數(shù)據(jù)類型，一個(gè)是Graph，用于描述圖的結(jié)構(gòu)。另一個(gè)是Vertex，用于描述頂點(diǎn)，指在地圖上的某一位置。Graph是一個(gè)圖類。包含一個(gè)頂點(diǎn)數(shù)組verteices，用于存放圖中的所有頂點(diǎn)。使用時(shí)，只需要傳入Grapha對(duì)象，代表起點(diǎn)和重點(diǎn)的頂點(diǎn)坐標(biāo)V0、Vt[5]。

具體實(shí)現(xiàn)步驟如下：

采用循環(huán)重復(fù)上述步驟2、3，直到S中包含所有頂點(diǎn)，即W=Vi為止。

3.3 實(shí)例演示

目前此校園虛擬地圖導(dǎo)航系統(tǒng)已成功在韶關(guān)學(xué)院校園中應(yīng)用。系統(tǒng)主要的模塊包括3D虛擬地圖瀏覽、單位搜索、尋路和全景展示等等。其中關(guān)鍵的技術(shù)采用Flash平臺(tái)技術(shù)，來(lái)實(shí)現(xiàn)系統(tǒng)中各種交互效果，以及制作、圖片等美術(shù)資源。在系統(tǒng)實(shí)現(xiàn)中，采用多種算法來(lái)優(yōu)化系統(tǒng)的執(zhí)行效率，可以在地圖中搜索任意兩個(gè)地點(diǎn)間的最短距離。

例如要在系統(tǒng)中搜索從道平廣場(chǎng)到學(xué)術(shù)樓的最短路徑，輸入地點(diǎn)為道平廣場(chǎng)，終點(diǎn)為學(xué)術(shù)樓，系統(tǒng)經(jīng)運(yùn)算，求得最短路徑。根據(jù)系統(tǒng)求得的最短路徑，在地圖上用紅色箭頭標(biāo)顯示。具體實(shí)現(xiàn)效果圖如圖5所示：

4 結(jié)束語(yǔ)

本文在研究虛擬地圖數(shù)據(jù)組織和表示方法的基礎(chǔ)上，以FLASH作為開(kāi)發(fā)平臺(tái)作了一個(gè)校園地圖，驗(yàn)證了在虛擬地圖上求最短路徑的可行性，但是本系統(tǒng)在取得一定成果的同時(shí)，也存在一些不足需要進(jìn)一步改進(jìn)，如：只實(shí)現(xiàn)了簡(jiǎn)單的屬性查詢功能，是不能提供復(fù)雜的空間查詢功能。如何解決這些不足還有待于進(jìn)一步加以研究。

參考文獻(xiàn)：

[1]盧開(kāi)澄.計(jì)算機(jī)算法導(dǎo)引——設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，1996：566-569.

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1997：255-260.

[3]李元臣，李維群.基于Dijkstra算法的網(wǎng)絡(luò)最短路徑分析[J].微計(jì)算機(jī)應(yīng)用，2004（03）：3-4.

[4]雋志才，倪安寧，賈洪飛.兩種策略下的最短路徑并行算法研究與實(shí)現(xiàn)[J].系統(tǒng)工程理論方法應(yīng)用，2006（02）：125-127.

[5]王櫻，徐雨明.校園道路網(wǎng)最短路徑的分析與實(shí)現(xiàn)[J].衡陽(yáng)師范學(xué)院學(xué)報(bào)，2004（06）：77-79.

[6]齊治昌.軟件工程[M].北京：高等教育出版社，2004：388-389.

作者簡(jiǎn)介：李步德（1964-），男，廣東韶關(guān)人，副研究館員，本科。

作者單位：韶關(guān)學(xué)院 檔案館，廣東韶關(guān) 512005