資源描述：
《一種基于Dijkstra并行線程算法的研究與實現(xiàn)-論文.pdf》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。
1、第37卷第9期測繪與空間地理信息V01．37．No．92014年9月GEOMATICS＆SPATIALlNFoRMATloNTECHNoLoGySep．，2014一種基于Dijkstra并行線程算法的研究與實現(xiàn)李平，李永樹(西南交通大學地球科學與環(huán)境工程學院，四川成都610031)摘要：針對傳統(tǒng)Dijkstra算法運行效率的問題，提出了一種基于傳統(tǒng)Dijkstra并行線程的算法，該算法動態(tài)地將交通網(wǎng)絡進行子網(wǎng)分割。通過實驗測試了不同網(wǎng)絡節(jié)點數(shù)量和弧段數(shù)量下傳統(tǒng)Dijkstra算法和本文算法運行時間，實驗結果表明本文算法能夠縮減網(wǎng)
2、絡節(jié)點搜索空間，降低算法的時間復雜度，提高算法的運行效率。關鍵詞：Dijkstra算法；GIS；多線程；子網(wǎng)；時間復雜度；運行效率中圖分類號：P208文獻標識碼：B文章編號：1672—5867(2014)o9—0050一o4ResearchandImplementationofOneParallelThreadAlgorithmBasedonDijkstraLIPing，LIYong—shu(EarthScienceandEnvironmentalEngineeringAcademyofSouthwestJiaotongUniv
3、ersity，Chengdu610031，China)Abstract：AimingattheproblemofoperatingeficiencyoftraditionalDijkstraalgorithm，thepapercomesupwithonealgorithmofparallelthreadbasedontraditionalDijkstra．Thealgorithmdivisestrafficnetworkintosubnetsdynamically．Throughexperiment，theoperatingti
4、meoftraditionalDijkstraalgorithmistestedunderdifferentnumberofnetworkjunctionsandarCS．Theexperimenthasdemonstratedthatthealgorithmcanlowersearchingspaceofnetworkjunctions，reduceDijkstratimecomplexityandimproveDijkstraoperatingeficiency．Keywords：Dijkstraalgorithm；GIS；
5、muhithreading；subnet；timecomplexity；operatingefficiency度為O(n)，隨著網(wǎng)絡節(jié)點數(shù)增加，算法需要的時間也0引言會成倍增加?？紤]到?jīng)]有充分利用現(xiàn)有的計算機資最短路徑分析是GIS空間分析中最重要的分析應用源，仍有較大的提升空間。本文提出一種新的并行算法之一，其在醫(yī)療救護、火災救援等事故以及人們出行導航思路，在經(jīng)典Dijkstra算法的基礎上，采用雙線程分別從方面已經(jīng)成為不可或缺的分析應用?。隨著城市交通網(wǎng)起點和終點同時按照Dijkstra算法最短路徑的搜索分析，絡的日趨復雜以及
6、用戶體驗的日益提高，最短路徑分析分析過程中采用節(jié)點標記法動態(tài)地將交通網(wǎng)絡進行子網(wǎng)需要在盡可能短的時間分析出結果，加之計算機軟硬件分割，最終將兩個子網(wǎng)的搜索結果進行拼接匯總，獲取最日新月異的進步，使得并行處理分析成為可能。短路徑。目前，對于最短路徑Dijkstra算法研究主要有兩個大1最短路徑算法簡述的方向：一個是對于經(jīng)典串行算法Dijkstra的修改、約束和改進，以達到改進經(jīng)典算法的空間復雜度和時間復雜傳統(tǒng)Dijkstra算法思想，被認為是最完備的算法，得度，提高算法的運行效率的目的；另一個是修改Dijkstra出的結果最短，其
7、特點是以起始點為中心，弧段權重為代算法為并行算法，合理利用計算機資源，提高算法的運行價，向外層層擴展，直至擴展到終點為止。效率，較普遍的做法是，先根據(jù)并行數(shù)進行網(wǎng)絡節(jié)點的平設G=(，E)是一個賦權有向圖，即對于圖中的每均分配，然后進行分析處理，但也不是并行數(shù)越多，效率一條邊e=(，)都賦予了一個權值WD()表示點越高。和vi之間的最短距離。在圖G中指定一個頂點，，確經(jīng)典的Dijkstra算法屬于串行算法，該算法時間復雜定為起點。收稿日期：2014一O1—22基金項目：高等學校博士學科點專項科研基金(20100184110019)
8、資助作者簡介：李平(1986一)，男，四川綿陽人，地圖學與地理信息系統(tǒng)專業(yè)碩士研究生，主要研究方向為地理信息系統(tǒng)及其應用。第9期李平等：一種基于Dijkstra并行線程算法的研究與實現(xiàn)511)開始，先給。標上紅色標號，且D()=0，其余各點D(vi)=+oo(≠
