最短路径的并行算法综述

《最短路径的并行算法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最短路径的并行算法综述SA02011105陈艾(aiai@mail.ustc.edu.cn)摘要：最短路径问题是图论中的一个典范问题，它被应用于众多领域。最短路径问题可以分成两类：单源最短路径、所有顶点对间的最短路径。本文对最短路径的并行算法进行综述，并介绍目前最短路径问题中的一个热点问题K条最短路径。关键字:最短路径,单源最短路径，所有顶点对间的最短路径，K条最短路径ASummaryonParallelAlgorthmsforShortestPathProblemsSA02011105CHENAiAbstract:Theshortest

2、pathproblemplaysanimportantroleingraphtheory.Itisappliedtonumerousarea.Itiscomposedoftwoparts:singlesourceshortestpathsandallpairsshortestpaths.Thispaperpresentsasummaryonparallelalgorithmsfortheshortestpathproblemsincludingintroducingahotissuekshortestpathsinshortestpath

3、problemsatpresent.Keywords:Shortestpaths,Singlesourceshortestpaths，Allpairsshortestpaths,Kshortestpaths1.引言二十世纪屮后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域。最短路径问题最直接的应用当数在地理信息领域，女恥GIS网络分析、城市规划、电子导航等。在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子。在网络通信领域，信息包传递的路径

4、选择问题也与最短路径问题息息相关。举个例子，OPSF开放路由选择协议，每个OPSF路由器都维护一个描述自治系统拓扑结构的数据库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统范围内到每个冃标的最短路径。在图彖分割问题中，最短路径也有直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如，to、two.tOOo为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的权代表相邻的可能行大小。这样图中的最短路径，就是对句子的最好解释。由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些

5、经典的算法。近些年来，对最短路径研究的热度依然不减，并11时间复杂度降得越来越低。总的来讲，最短问题可以分成两类：单源最短路径和所有顶点对间的最短路径。木文就从上述两类来分别介绍最短路径的并行算法，并介绍最短路径问题中的一个热点问题K条最短路径问题。本文的其它部分组织如下：第2节介绍单源最短路径问题的并行算法；第3节介绍所有顶点对间的最短路径问题的并行算法；第4节介绍K条最短路径问题；最后在第5节总结最短路径的并行算法，并谈谈自己的想法。2.单源最短路径问题单源最短路径问题是指从一个给定顶点S到其它所有顶点i之间的距离dist(i)为最短

6、的路径，其+seV称为源点，iWV且iHs。假定图G(V,E)是一个有向网络，其加权邻接矩阵为W,且边上权值w(i,j)>0,i,jeV,V={1,2,…，n}o2.1.单处理机上的单源最短路径算法在单处理机上，人们研究最短路径问题已取得许多成果，设计了几十种算法，其屮Dijkstra算法是解决这个问题的最有效算法在串行情况下，该算法的时间复杂度为O(m+nlogn)。其基本思想是:假定有一个待搜索顶点表VL,初始化时做:dist(s)_O；dist(i)Y(iHs)；VL-Vo算法执行吋，每次从VL(工①)中选取这样一个顶点u,它的di

7、st(u)值最小。将选出的U作为搜索顶点，若〈u,v>eE,而且dist(u)+w(u,v)

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