校園導(dǎo)航系統(tǒng)最短路徑的實現(xiàn)

楊偉龍，李步德，謝俊鵬

（韶關(guān)學(xué)院檔案館，廣東韶關(guān)512005）

隨著高校的發(fā)展，校園面積不斷擴(kuò)大，為適應(yīng)數(shù)字化校園建設(shè)的要求，各高校開發(fā)設(shè)計了校園導(dǎo)航系統(tǒng).查詢最短路徑的實現(xiàn)是校園導(dǎo)航系統(tǒng)主要功能之一，闡述了基于Flash技術(shù)開發(fā)平臺，運用迪杰斯特拉（Dijkstra）算法實現(xiàn)校園導(dǎo)航系統(tǒng)最短路徑的功能.

高校；導(dǎo)航系統(tǒng)；最短路徑；迪杰斯特拉算法

隨著國內(nèi)高校的發(fā)展，校園面積不斷擴(kuò)大.校園內(nèi)教學(xué)樓、辦公樓、學(xué)生公寓、運動場館、商業(yè)網(wǎng)點、綠化景點等林林總總、錯綜復(fù)雜，即使在學(xué)校工作、生活幾年的老師或?qū)W生也未必清楚了解，對于外來辦事的人員更會帶來諸多不便.許多高校專門設(shè)計了校園電子地圖導(dǎo)航系統(tǒng)，為師生和校外人士辦事辦公提供便利.為適應(yīng)數(shù)字化校園建設(shè)的要求，韶關(guān)學(xué)院也自主開發(fā)了一款校園導(dǎo)航系統(tǒng)，系統(tǒng)在用3ds max構(gòu)建了本校電子地圖的基礎(chǔ)上，采用了Flash開發(fā)及Action Script 3.0語言，結(jié)合PHP+MySQL進(jìn)行設(shè)計，實現(xiàn)了基于Flash技術(shù)平臺的校園虛擬地圖導(dǎo)航系統(tǒng)［1］.

最短路徑的實現(xiàn)是校園導(dǎo)航系統(tǒng)主要功能之一，用戶設(shè)定起點和終點，系統(tǒng)自動計算，并將兩點間最短的路徑連接起來，用明顯顏色的線段標(biāo)示出來，見圖1.

圖1 校園導(dǎo)航系統(tǒng)最短路徑實現(xiàn)

1 運用迪杰斯特拉算法實現(xiàn)最短路徑

在本導(dǎo)航系統(tǒng)中最短路徑的實現(xiàn)是基于迪杰斯特拉（Dijkstra）算法，該算法的基本思想：令G=(V，E)為一個帶權(quán)有向圖，把圖中所有頂點的集合V分成兩組，第一組為已求最短路徑的頂點集合S（初始狀態(tài)時只有源點在s里面，以后每找到一條最短路徑，就將其對應(yīng)頂點加入集合S里面，直到全部頂點都加入到S里面）；第二組是未確定最短路徑的頂點集合U.在向集合添加點的過程中，總是保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度［2］.

圖2是應(yīng)用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程，通過計算，源點到最后一個頂點的路徑為：1->4->3->5，所以源點到最后一個頂點的最短路徑長度：60［3］.

2 校園導(dǎo)航系統(tǒng)實現(xiàn)最短路徑的方法

2.1程序設(shè)計思想

實現(xiàn)校園地圖上任意兩點間最短路徑的尋找并向用戶呈現(xiàn)出來，設(shè)計思路是關(guān)鍵.由于校園線路可直接抽象為無向圖，對于無向圖的最短路徑尋找，普遍采用的是迪杰斯特拉算法［4］，其最短路徑實現(xiàn)的步驟見圖3.

圖2 最短路徑的計算

圖3 最短路徑的實現(xiàn)步驟

2.2具體實現(xiàn)過程

迪杰斯特拉算法的基本思想是通過計算一個節(jié)點到其他所有節(jié)點的距離，也就是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止，經(jīng)計算對比得出最短路徑.因此，首先是定義節(jié)點，羅列從起點到終點經(jīng)過的所有節(jié)點個數(shù).

（1）節(jié)點數(shù)據(jù)結(jié)構(gòu)類型

#define MAX_V 30//最大頂點個數(shù)

typedefstruct

{

char*vexs［MAX_V］;//頂點向量

intarcs［MAX_V］［MAX_V］;//鄰接矩陣

intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)

}MGraph;

（2）創(chuàng)建導(dǎo)航圖函數(shù)

int CreateUDN(MGraph&G)

函數(shù)描述：主要將每個節(jié)點進(jìn)行命名、每個頂點到其他所有定點的路徑值用鄰接矩陣進(jìn)行存儲.例：

G.vexs［1］=“學(xué)術(shù)交流中心”;

作用：使1號定點命名為“學(xué)術(shù)交流中心”;

G.arcs［1］［0］=G.arcs［0］［1］=550;

作用：使1號節(jié)點到2號節(jié)點的路徑賦值為550，因為是無向圖，所以2號節(jié)點到1號節(jié)點的路徑長度也應(yīng)賦值為550，其他節(jié)點間的長度計算以此類推［5］.

2.3后臺數(shù)據(jù)編輯

在整個系統(tǒng)中，后臺部分可以對點和路線進(jìn)行編輯，使得最短路徑有效而準(zhǔn)確.

編輯點和路線是利用flash技術(shù)編寫的編輯器進(jìn)行設(shè)置的，見圖4.

圖4 校園地圖上編輯點和路線的界面

可以根據(jù)需要添加若干頂點，點擊右上方的“開始加點”按鈕，然后在相應(yīng)的位置左鍵點擊一下，就會出現(xiàn)圖5的紅點，加點完成后點擊結(jié)束.如果要刪除不需要的頂點，可以左鍵點擊一下該頂點，然后點擊右上方的“刪除頂點”按鈕，該頂點與之相關(guān)的連線就會刪除.

在點的基礎(chǔ)上可以進(jìn)行路線的編輯.左鍵點擊需要連線的頂點不放，拖動鼠標(biāo)，便會看到的黑線（見圖5）.黑線會跟隨鼠標(biāo)變化，當(dāng)接近另一頂點時，黑線會自動吸附在上面，松開左鍵便可完成連線，不松開繼續(xù)拖動就可以選擇其他點連線.

圖5 編輯點和線

保存編輯的內(nèi)容，點擊右上方的“保存編輯”按鈕，然后點擊頁面最上方的“提交”按鈕，將數(shù)據(jù)提交至服務(wù)器，從而完成對路線的編輯.

3 功能測試

在韶關(guān)學(xué)院校園導(dǎo)航系統(tǒng)中，選取的校園景點有：信工樓，理工樓、音樂樓、美術(shù)樓、行政樓、南區(qū)一號教學(xué)樓、科技樓、圖書館、道平廣場、紫荊苑、學(xué)術(shù)交流中心等.先通過搜索功能找到起點的位置，也可直接點擊作為起點的建筑，并點擊“設(shè)為起點”，同理，找到終點位置，點擊“設(shè)為終點”，見圖6.

圖6 設(shè)置起點和終點

繼續(xù)點擊“開始尋路”，通過系統(tǒng)最短路徑計算，一條藍(lán)色粗線將起點和終點連接起來，為使用者提供了到目的地的路線.圖7是以信工樓為起點道平廣場為終點的最短路徑.

圖7 起點與終點的連線

利用迪杰斯特拉算法結(jié)合Flash技術(shù)設(shè)計的校園導(dǎo)航系統(tǒng)最短路徑模塊，結(jié)構(gòu)簡單，容易實現(xiàn)，并且給后臺管理提高了極大的便利.該功能的實現(xiàn)提高了校園導(dǎo)航系統(tǒng)的實用性.

［1］彼得斯.Flash ActionScript3.0動畫高級教程［M］.蘇金國，荊濤，譯.北京:人民郵電出版社，2010.

［2］劉茂華，王巖，周海壯.D算法最短路徑在數(shù)字校園中的應(yīng)用研究［J］.測繪通報，2012(S1):624-625.

［3］聶萍.校園智能電子導(dǎo)航系統(tǒng)分析與設(shè)計［D］.昆明:云南大學(xué)，2012.

［4］王櫻，徐雨明.校園道路網(wǎng)最短路徑的分析與實現(xiàn)［J］.衡陽師范學(xué)院學(xué)報，2004，25(6):77-79.

［5］李元臣，李維群.基于Dijkstra算法的網(wǎng)絡(luò)最短路徑分析［J］.微計算機(jī)應(yīng)用，2004，25(3):3-4.

On how to achieve the shortest path campus navigation system

YANG Wei-long,LI Bu-de,XIE Jun-peng
(Archives,Shaoguan University,Shaoguan 512005,Guangdong,China)

With the development of colleges and universities,campus area is expanding.To meet the requirements of digital campus construction,it is necessary to develop and design the university campus navigation system.Query shortest path to achieve campus navigation system is one of the main functions,and this paper describes the development platform based on Flash technology,and makes the use of Dijkstra algorithm to achieve the shortest path campus navigation system functions.

university；navigation system；shortestpath；Dijkstra algorithm

TP311.5

A

1007-5348（2014）04-0020-04

（責(zé)任編輯：歐愷）

2014-02-24

楊偉龍（1971-），男，廣東韶關(guān)人，韶關(guān)學(xué)院檔案館館員，主要從事檔案信息化管理方面的研究.