【摘要】：為提升大規(guī)模網(wǎng)絡(luò)全源最短路徑的求解效率,基于重優(yōu)化理論提出了一種快速的精確全源最短路徑求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了異源最短路徑樹間的相關(guān)性和差異性;在已知單源最短路徑樹的基礎(chǔ)上,基于重優(yōu)化理論實(shí)現(xiàn)了異源最短路徑樹間的高效轉(zhuǎn)換,進(jìn)而得出高效求解全源最短路徑的RASP算法;理論證明RASP算法的時(shí)間復(fù)雜度為O(3n~2+2nm).實(shí)驗(yàn)測試表明:無論是在稀疏還是稠密網(wǎng)絡(luò)上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改進(jìn)算法.
[Abstract]:In order to improve the efficiency of solving the all-source shortest path in large-scale networks, a fast and accurate all-source shortest path solution method, RASP (reoptimization-based all-pairs shortest path) algorithm), is proposed based on the theory of re-optimization. This paper analyzes the correlation and difference between the shortest path trees of different sources, and realizes the efficient conversion between the shortest path trees of different sources based on the theory of reoptimization on the basis of the known tree of the shortest path of single source. Then the RASP algorithm for solving all the shortest paths efficiently is obtained, and the time complexity of RASP algorithm is proved to be O (3n~2 2nm). The experimental results show that the RASP algorithm can outperform the Floyd algorithm, the n-order Dijkstra algorithm and its improved algorithm effectively in both sparse and dense networks.
【作者單位】： 北京師范大學(xué)減災(zāi)與應(yīng)急管理研究院;東北大學(xué)資源與土木工程學(xué)院;中南大學(xué)地球科學(xué)與信息物理學(xué)院;中國礦業(yè)大學(xué)(北京)地球科學(xué)與測繪工程學(xué)院;
【基金】：國家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2011AA120302)
【分類號(hào)】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 李鳴鵬;鄒兆年;高宏;趙正理;;不確定圖上期望最短距離的計(jì)算[J];計(jì)算機(jī)研究與發(fā)展;2012年10期

2 邢星星;趙國興;駱祖瑩;方浩;;基于GPU的全源最短路徑算法[J];計(jì)算機(jī)科學(xué);2012年03期

3 陸鋒;最短路徑算法:分類體系與研究進(jìn)展[J];測繪學(xué)報(bào);2001年03期

4 吳京,景寧,陳宏盛;最佳路徑的層次編碼及查詢算法[J];計(jì)算機(jī)學(xué)報(bào);2000年02期

5 嚴(yán)寒冰,劉迎春;基于GIS的城市道路網(wǎng)最短路徑算法探討[J];計(jì)算機(jī)學(xué)報(bào);2000年02期

6 徐業(yè)昌,李樹祥,朱建民,許嵐,曹次華;基于地理信息系統(tǒng)的最短路徑搜索算法[J];中國圖象圖形學(xué)報(bào);1998年01期

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊佳榮;齊倩倩;李海軍;;旅游服務(wù)信息系統(tǒng)的分析與設(shè)計(jì)[J];電子商務(wù);2017年07期

2 江錦成;吳立新;張媛媛;劉善軍;;適用于大規(guī)模網(wǎng)絡(luò)的全源最短路徑重優(yōu)化算法——RASP算法[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年07期

3 馮景澤;顏何生;;彎曲走廊最短路徑算法及在水能計(jì)算中的應(yīng)用[J];人民珠江;2017年06期

4 張翰林;關(guān)愛薇;傅珂;孫廷凱;;Dijkstra最短路徑算法的堆優(yōu)化實(shí)驗(yàn)研究[J];軟件;2017年05期

5 夏帥;王華秀;于幸;徐宇嘉;;基于GPS定位技術(shù)的旅游導(dǎo)航系統(tǒng)的研究[J];電腦知識(shí)與技術(shù);2017年09期

6 邱儒瓊;聶小波;王海俠;;基于WiFi的室內(nèi)位置服務(wù)路徑規(guī)劃研究[J];地理空間信息;2017年04期

7 康文雄;許耀釗;;節(jié)點(diǎn)約束型最短路徑的分層Dijkstra算法[J];華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年01期

8 許自昌;;基于最小生成樹的渠道系統(tǒng)優(yōu)化布局模型[J];農(nóng)業(yè)工程學(xué)報(bào);2017年01期

9 王艷;黃開建;孫茂圣;李開榮;朱俊武;;面向智能導(dǎo)覽的個(gè)性化線路規(guī)劃研究[J];現(xiàn)代電子技術(shù);2016年20期

10 徐小奇;;基于海量出租車軌跡數(shù)據(jù)的智能推薦系統(tǒng)研究[J];電子制作;2016年18期

【二級(jí)參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 盧風(fēng)順;宋君強(qiáng);銀�？�;張理論;;CPU/GPU協(xié)同并行計(jì)算研究綜述[J];計(jì)算機(jī)科學(xué);2011年03期

2 袁野;王國仁;;面向不確定圖的概率可達(dá)查詢[J];計(jì)算機(jī)學(xué)報(bào);2010年08期

3 周益民,孫世新,田玲;一種實(shí)用的所有點(diǎn)對(duì)之間最短路徑并行算法[J];計(jì)算機(jī)應(yīng)用;2005年12期

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 孟祥清;長度遞增法求最短路徑[J];河北能源職業(yè)技術(shù)學(xué)院學(xué)報(bào);2002年04期

2 傅清祥,王朝利,孫劍峰;長廊最短路徑的最優(yōu)算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2002年12期

3 王濤,李偉生;最短路徑子圖[J];北方交通大學(xué)學(xué)報(bào);2004年02期

4 徐鳳生;最短路徑的求解算法[J];計(jì)算機(jī)應(yīng)用;2004年05期

5 王濤,李偉生;低代價(jià)最短路徑樹的快速算法[J];軟件學(xué)報(bào);2004年05期

6 宣士斌;基于分流算法的最短路徑求解算法[J];計(jì)算機(jī)工程與應(yīng)用;2004年20期

7 徐鳳生;李天志;;所有最短路徑的求解算法[J];計(jì)算機(jī)工程與科學(xué);2006年12期

8 白青海;;一種求解交通圖最短路徑的方案[J];內(nèi)蒙古民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

9 章昭輝;;一種基于離散變權(quán)網(wǎng)絡(luò)的動(dòng)態(tài)最短路徑快速算法[J];計(jì)算機(jī)科學(xué);2010年04期

10 原慧琳;汪定偉;;最短路徑的可達(dá)矩陣算法[J];信息與控制;2011年02期

相關(guān)會(huì)議論文 前10條

1 溫粉蓮;唐常杰;喬少杰;許剛;劉威;左R，

本文編號(hào)：2263269