校園導航系統最短路徑的實現

校園導航系統最短路徑的實現

楊偉龍，李步德，謝俊鵬

（韶關學院檔案館，廣東韶關512005）

隨著高校的發展，校園面積不斷擴大，為適應數字化校園建設的要求，各高校開發設計了校園導航系統.查詢最短路徑的實現是校園導航系統主要功能之一，闡述了基于Flash技術開發平臺，運用迪杰斯特拉（Dijkstra）算法實現校園導航系統最短路徑的功能.

高校；導航系統；最短路徑；迪杰斯特拉算法

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

最短路徑的實現是校園導航系統主要功能之一，用戶設定起點和終點，系統自動計算，并將兩點間最短的路徑連接起來，用明顯顏色的線段標示出來，見圖1.

圖1 校園導航系統最短路徑實現

1 運用迪杰斯特拉算法實現最短路徑

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

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

2 校園導航系統實現最短路徑的方法

2.1程序設計思想

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

圖2 最短路徑的計算

圖3 最短路徑的實現步驟

2.2具體實現過程

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

（1）節點數據結構類型

#define MAX_V 30//最大頂點個數

typedefstruct

{

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

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

intvexnum,arcnum;//圖的當前頂點數和弧數

}MGraph;

（2）創建導航圖函數

int CreateUDN(MGraph&G)

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

G.vexs［1］=“學術交流中心”;

作用：使1號定點命名為“學術交流中心”;

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

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

2.3后臺數據編輯

在整個系統中，后臺部分可以對點和路線進行編輯，使得最短路徑有效而準確.

編輯點和路線是利用flash技術編寫的編輯器進行設置的，見圖4.

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

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

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

圖5 編輯點和線

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

3 功能測試

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

圖6 設置起點和終點

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

圖7 起點與終點的連線

利用迪杰斯特拉算法結合Flash技術設計的校園導航系統最短路徑模塊，結構簡單，容易實現，并且給后臺管理提高了極大的便利.該功能的實現提高了校園導航系統的實用性.

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

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

［3］聶萍.校園智能電子導航系統分析與設計［D］.昆明:云南大學，2012.

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

［5］李元臣，李維群.基于Dijkstra算法的網絡最短路徑分析［J］.微計算機應用，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

（責任編輯：歐愷）

2014-02-24

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