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

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