北京東方首選教育企業(yè)集團（管理顧問有限公司）

引言隨著計算機技術以及地理信息科學的發(fā)展,GIS(地理信息系統(tǒng))[1]的空間分析功能得到越來越廣泛的應用。網(wǎng)絡分析作為空間分析的方法之一,在許多領域中發(fā)揮著重要的作用,而網(wǎng)絡分析中最基本最關鍵的問題就是最短路徑問題,人們在繼D ijkstra算法之后,又進行了大量的研究工作,提出了大量求解最短路徑的算法[2-8]。并且有不少學者提出了適用于GIS的最短路徑算法[9-10]。然而這些研究都是針對固定拓撲和固定權值的網(wǎng)絡,沒有考慮拓撲結構隨時間變化、權值是時間函數(shù)等的時變情況。GIS網(wǎng)絡是一種時變網(wǎng)絡,網(wǎng)絡的拓撲結構、各邊的權值都隨時間變化而變化。許多學者都認識到以固定拓撲為基礎的網(wǎng)絡理論不能適應于GIS網(wǎng)絡。目前已有不少學者開始研究時變拓撲網(wǎng)絡中的最短路徑問題[11]。1傳統(tǒng)的D ijkstra算法1.1算法原理網(wǎng)絡圖中的結點分為未標記結點、臨時標記結點和永久標記結點三種類型。初始化時所有的結點都置為未標記結點,在搜索過程中凡是與最短路徑中的結點相連通的結點都是臨時標記結點,把從臨時標記結點中搜索距源點路徑長度最短的結點作為永久標記結點。