最短路径的并行算法综述SA02011105 陈艾(aiai@)摘要：最短路径问题是图论中的一个典范问题，它被应用于众多领域。

最短路径问题可以分成两类：单源最短路径、所有顶点对间的最短路径。

本文对最短路径的并行算法进行综述，并介绍目前最短路径问题中的一个热点问题K条最短路径。

关键字：最短路径，单源最短路径，所有顶点对间的最短路径，K条最短路径A Summary on Parallel Algorthms for Shortest Path ProblemsSA02011105 CHEN AiAbstract:The shortest path problem plays an important role in graph theory .It is applied to numerous area . It is composed of two parts: single source shortest paths and all pairs shortest paths. This paper presents a summary on parallel algorithms for the shortest path problems including introducing a hot issue k shortest paths in shortest path problems at present.Keywords:Shortest paths，Single source shortest paths，All pairs shortest paths，K shortest paths1. 引言二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域。

最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等。

在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子。

在网络通信领域，信息包传递的路径选择问题也与最短路径问题息息相关。

举个例子，OPSF开放路由选择协议，每1SA02011105 陈艾个OPSF路由器都维护一个描述自治系统拓扑结构的数据库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统范围内到每个目标的最短路径。

在图象分割问题中，最短路径也有直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如，to、two、too。

为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的权代表相邻的可能行大小。

这样图中的最短路径，就是对句子的最好解释。

由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些经典的算法。

近些年来，对最短路径研究的热度依然不减，并且时间复杂度降得越来越低。

总的来讲，最短问题可以分成两类：单源最短路径和所有顶点对间的最短路径。

本文就从上述两类来分别介绍最短路径的并行算法，并介绍最短路径问题中的一个热点问题K条最短路径问题。

本文的其它部分组织如下：第2节介绍单源最短路径问题的并行算法；第3节介绍所有顶点对间的最短路径问题的并行算法；第4节介绍K条最短路径问题；最后在第5节总结最短路径的并行算法，并谈谈自己的想法。

2. 单源最短路径问题单源最短路径问题是指从一个给定顶点S到其它所有顶点i之间的距离dist(i)为最短的路径，其中s∈V称为源点，i∈V且i≠s。

假定图G(V,E)是一个有向网络，其加权邻接矩阵为W，且边上权值w（i，j)>0，i，j∈V，V={1，2，…，n}。

2.1. 单处理机上的单源最短路径算法在单处理机上，人们研究最短路径问题已取得许多成果，设计了几十种算法，其中Dijkstra 算法是解决这个问题的最有效算法之一。

在串行情况下，该算法的时间复杂度为O(m+nlogn)。

其基本思想是：假定有一个待搜索顶点表VL，初始化时做：dist(s)←0；dist(i)←∞(i≠s)；VL←V。

算法执行时，每次从VL（≠Φ）中选取这样一个顶点u，它的dist(u)值最小。

将选出的u作为搜索顶点，若<u，v>∈E，而且dist(u)+w(u,v)<dist(v)，则更新dist(v)为dist(u)+w(u,v)，直到VL=Φ时算法终止。

算法描述如下：算法1 DIJKSTRA ALGORITHM(SISD)2SA02011105 陈艾输入：加权邻接矩阵W，约定i，j之间无边连接时w(i,j)=∞，且w(i,i)=∞；输出：dist(1:n)，其中，dist(i)表示顶点s到顶点i的最短路径（1≤i≤n）。

begin/*初始化*/（1） dist(s)←0；（2） for i←1 to n doif i≠s then dist(i)←∞ endifendfor；（3） VL←V；（4） For i←1 to n do /*找最短距离*/（5） Find a vertex u∈VL,such that dist(u) is minimal；（6） For each(<u，v>∈E) ∧ (v∈VL) doIf dist(u)+w(u,v)<dist(v) then dist(v)←dist(u)+w(u,v) endifendfor；(7)VL←VL-{u}EndforEnd.除了Dijkstra算法外，Moore算法解决单源最短路径问题也是较有效的。

在Moore算法中，设源点为s∈V,从s到其它各顶点的最短路径长度用一个一维数组dist存储。

首先置dist(s)=0，dist(v)←∞，v≠s，v∈V。

Moore算法同Dijkstra算法不同之处是：将Dijkstra 算法中的待搜索顶点表替换成待搜索队列。

算法开始执行时，队列仅含源点s。

以后每次只要待搜索队列非空，则将队头的顶点从队列中移出作为本次搜索的顶点，然后检查u的所有射出边<u，v>∈E。

若dist(u)+w(u,v)<dist(v)，则此时找出了一条从s到v的更短路径，置dist(v)等于dist(u)+w(u,v)。

若v不在搜索队列中，则把v加入到队列的队尾。

如此重复进行，直到整个待搜索队列空时，算法终止。

单处理器上的Moore算法如下：算法2 MOORE ALGORITHM(SISD)3SA02011105 陈艾输入：有向图G(V,E)的加权邻接矩阵W={w ij},i,j∈V；输出：从源s到所有其它顶点i(i≠s)的最短路径dist(i)，i∈V。

begin(1) for i←1 to n do /*初始化*/call INITIALIZE(i)endfor;(2) insert s into the queue; /*插入s到队列中*/(3) while the queue is not empty do(4) call SEARCHendwhileend.Procedure SEARCH;Begin(4.1) dequeue vertex u; /*从队列中删去顶点u*/(4.2) for each edge (u,v)∈E do(4.3) new_dist←dist(u)+w(u,v);(4.4) if new_dist<dist(v) then dist(v)←new_dist endif;(4.5) if v is not in the queue then enqueue vertex v endifendforend.Procedure INITIALIZEBegin(1.1)dist(s)←0(1.2)dist(v)←∞(v≠s,v∈V)(1.3)queue←0end.4SA02011105 陈艾SA02011105 陈艾52.2. 单源最短路径的并行算法Paige 等人[1]基于SIMD_EREW PRAM 上，对Dijkstra 算法进行并行化，其时间复杂度为O(n 2/p+nlogp)，O （p ）个处理器。

具体算法并行化如下：算法的第（2）步的实现为：每个处理器分派⎡⎤p n /个顶点，最后一个处理器分派n-⎡⎤p n /*(p-1)个顶点，每个处理器对所分派的顶点顺序地赋值；第（3）步其实是对数组VL赋值，同第（2）步类似处理；第（5）步实现如下：首先每个处理器检测自己内部⎡⎤p n /个顶点的最小值，然后p 个处理器合作，并行计算p 个最小值中的最小值；第（6）步实现如下：首先将顶点u 广播到所有的处理器中，假定u 是送入处理器i 的B(i)单元中（1≤i ≤p ），则实现广播算法为：算法3 BROADCAST输入：数据u(存放在单元B(1)中)；输出：将u 广播到数组B 的所有单元中去。

Begin(1) B(1)←u ；（2）for i ←0 to ⎡⎤p log -1 do(3) for each j:2i +1≤j ≤2i+1 pardoB(j)←B(j-2j )EndforEndforEnd.然后，每个处理器检查所有边<u ，v>∈E ，其中V ∈vl ，且v 是本处理器的顶点。

Paige 等人还在SIMD-CRCW PRAM 运用了上述算法，在这种计算模型上用p 个处理器对n 个元素进行二元结合运算，仅需O （n/p+loglogp ）时间。

Deo 等人基于MIMD 紧耦合共享存储模型，实现Moore 算法的并行化[2]。

他们主要针对Moore算法的第（3）到第（4）步的while循环并行化。

MIMD紧耦合多处理机上的单源最短路径算法见[2]。

在MIMD机器模型上，Chen曾经给出一个O(dn2)时间、O(n)处理器的单源最短路径问题的分布式算法。

其后，Lakhai改进了Chen的算法，使得在处理器数不变的前提下，时间复杂度降到O(n2)。

近些年来，单源最短路径的算法改进较少。

第3节中，我们将讨论解决所有顶点对间的最短路径问题的算法。

3. 所有顶点对间的最短路径问题所有点对间的最短路径就是计算所有顶点对间的最短路径。

Floyd算法，又称传递闭包方法，是求解所有顶点对间的最短路径问题的一个经典的算法，其实质就是矩阵自乘n次。

下面将介绍单处理机上的所有顶点对间的最短路径问题的Floyd算法，以及一些解决该问题的并行算法。

3.1. 单处理机上的所有顶点对间的最短路径算法设一个有向图G(V,E)，∣V∣=n的加权邻接矩阵为W，且w(i,j)表示边（i,j）的长度，若i和j之间不存在有向边，则w(i,j)为∞，1≤i，j≤n，i，j∈V。

两个矩阵A和B的积C=AB定义为：C(i,j)=min{w(i,k)+w(k,j)∣k=1,2,…n}。