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

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