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