最短路徑的并行算法綜述

《最短路徑的并行算法綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、最短路徑的并行算法綜述SA02011105陳艾(aiai@mail.ustc.edu.cn)摘要：最短路徑問題是圖論中的一個(gè)典范問題，它被應(yīng)用于眾多領(lǐng)域。最短路徑問題可以分成兩類：?jiǎn)卧醋疃搪窂?、所有頂點(diǎn)對(duì)間的最短路徑。本文對(duì)最短路徑的并行算法進(jìn)行綜述，并介紹目前最短路徑問題中的一個(gè)熱點(diǎn)問題K條最短路徑。關(guān)鍵字:最短路徑,單源最短路徑，所有頂點(diǎn)對(duì)間的最短路徑，K條最短路徑ASummaryonParallelAlgorthmsforShortestPathProblemsSA02011105CHENAiAbstract:Theshortest

2、pathproblemplaysanimportantroleingraphtheory.Itisappliedtonumerousarea.Itiscomposedoftwoparts:singlesourceshortestpathsandallpairsshortestpaths.Thispaperpresentsasummaryonparallelalgorithmsfortheshortestpathproblemsincludingintroducingahotissuekshortestpathsinshortestpath

3、problemsatpresent.Keywords:Shortestpaths,Singlesourceshortestpaths，Allpairsshortestpaths,Kshortestpaths1.引言二十世紀(jì)屮后期，隨著計(jì)算機(jī)的出現(xiàn)和發(fā)展，圖論的研究得到廣泛重視，最短路徑問題是圖論中的一個(gè)典范問題，它已經(jīng)被應(yīng)用于眾多領(lǐng)域。最短路徑問題最直接的應(yīng)用當(dāng)數(shù)在地理信息領(lǐng)域，女恥GIS網(wǎng)絡(luò)分析、城市規(guī)劃、電子導(dǎo)航等。在交通咨詢方面，尋找交通路網(wǎng)中兩個(gè)城市間最短的行車路線就是最短路徑問題的一個(gè)典型的例子。在網(wǎng)絡(luò)通信領(lǐng)域，信息包傳遞的路徑

4、選擇問題也與最短路徑問題息息相關(guān)。舉個(gè)例子，OPSF開放路由選擇協(xié)議，每個(gè)OPSF路由器都維護(hù)一個(gè)描述自治系統(tǒng)拓?fù)浣Y(jié)構(gòu)的數(shù)據(jù)庫，通過這個(gè)數(shù)據(jù)庫構(gòu)建最短路徑樹來計(jì)算路由表，從而跟蹤自治系統(tǒng)范圍內(nèi)到每個(gè)冃標(biāo)的最短路徑。在圖彖分割問題中，最短路徑也有直接的應(yīng)用：在語音識(shí)別中，一個(gè)主要的問題就是區(qū)別同音詞，例如，to、two.tOOo為解決這個(gè)問題，我們需要建一個(gè)圖，頂點(diǎn)代表可能的單詞，邊連接相鄰的單詞，邊上的權(quán)代表相鄰的可能行大小。這樣圖中的最短路徑，就是對(duì)句子的最好解釋。由于最短路徑問題的廣泛應(yīng)用，很多學(xué)者都對(duì)此進(jìn)行了深入的研究，也產(chǎn)生了一些

5、經(jīng)典的算法。近些年來，對(duì)最短路徑研究的熱度依然不減，并11時(shí)間復(fù)雜度降得越來越低?？偟膩碇v，最短問題可以分成兩類：?jiǎn)卧醋疃搪窂胶退许旤c(diǎn)對(duì)間的最短路徑。木文就從上述兩類來分別介紹最短路徑的并行算法，并介紹最短路徑問題中的一個(gè)熱點(diǎn)問題K條最短路徑問題。本文的其它部分組織如下：第2節(jié)介紹單源最短路徑問題的并行算法；第3節(jié)介紹所有頂點(diǎn)對(duì)間的最短路徑問題的并行算法；第4節(jié)介紹K條最短路徑問題；最后在第5節(jié)總結(jié)最短路徑的并行算法，并談?wù)勛约旱南敕ā?.單源最短路徑問題單源最短路徑問題是指從一個(gè)給定頂點(diǎn)S到其它所有頂點(diǎn)i之間的距離dist(i)為最短

6、的路徑，其+seV稱為源點(diǎn)，iWV且iHs。假定圖G(V,E)是一個(gè)有向網(wǎng)絡(luò)，其加權(quán)鄰接矩陣為W,且邊上權(quán)值w(i,j)>0,i,jeV,V={1,2,…，n}o2.1.單處理機(jī)上的單源最短路徑算法在單處理機(jī)上，人們研究最短路徑問題已取得許多成果，設(shè)計(jì)了幾十種算法，其屮Dijkstra算法是解決這個(gè)問題的最有效算法在串行情況下，該算法的時(shí)間復(fù)雜度為O(m+nlogn)。其基本思想是:假定有一個(gè)待搜索頂點(diǎn)表VL,初始化時(shí)做:dist(s)_O；dist(i)Y(iHs)；VL-Vo算法執(zhí)行吋，每次從VL(工①)中選取這樣一個(gè)頂點(diǎn)u,它的di

7、st(u)值最小。將選出的U作為搜索頂點(diǎn)，若〈u,v>eE,而且dist(u)+w(u,v)

8、difendfor；(3)VL-V；(4)Fori*-ltondo/*找最短距離*/(5)Findavertexu^VL,suchthatdist(u)isminimal；(6)Foreach