所有结点对间的最短路径.ppt

《所有结点对间的最短路径.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、所有结点对间的最短路径给定一个带权图G=(V,E,)，所有结点对间的最短路径问题就是寻找所有ij的vi与vj之间的最短路径对一个具有n个结点的图，所有结点对间的最短路径的长度可以用一个n×n的矩阵D来表示，其中dk,j表示结点vk与结点vj之间最短路径的长度串行Dijkstra算法的复杂性为(n3)2021/7/301基于源结点划分的并行Dijkstra算法适用条件：结点数n不小于进程数p每个进程分配到n/p个结点，并分别求解从这些结点中每一个出发的单源最短路径问题如果邻接矩阵在每个进程上都有副本，则无任何通信开

2、销，并行执行时间为(n3/p)，并行效率为(1)2021/7/302基于源结点并行计算的Dijkstra算法适用条件：结点数n小于进程数pp个进程分为n组，每组p/n个进程，每个单源最短路径问题由一组进程进行求解不妨假设p为n的倍数，则每个单源最短路径问题在p/n个进程上并行求解，所以并行执行时间为Tp=(n2/(p/n))+(nlog(p/n))源结点并行计算方法可以有效利用到(n2/logn)个进程，且等效率函数为(p1.5log1.5p)2021/7/303Floyd算法对任何两个结点vi与vj，如果

3、记所有中间结点都属于{v1,v2,…,vk}的最短路径为pi,j,k，且记其长度为di,j,k，则di,j＝di,j,n且2021/7/304Floyd算法(续)Floyd_All_Pairs_SP(A,n)for(i:=1;i<=n;i++){for(j:=1;j<=n;j++)di,j,0:=ai,j;}for(k:=1;k<=n;k++){for(i:=1;i<=n;i++)for(j:=1;j<=n;j++)di,j,k:=min(di,j,k-1,di,k,k-1+dk,j,k-1);}2021/7/305F

4、loyd算法(续)二维块调度下的Floyd算法2021/7/306Floyd算法(续)二维块调度下的Floyd算法2021/7/307Floyd算法(续)在二维块划分下，Floyd算法一共需要n步每一步的通信时间为(n/p1/2logp)每一步的并行计算时间为(n2/p)并行执行时间为Tp=(n3/p)+(n2/p1/2logp))在直到O(n2/log2n)个进程上算法仍然是渐进最优的，且等效率函数为W=(p1.5log3p)2021/7/308Floyd算法(续)二维块划分下的流水线模式并行算法当拥有第k

5、行元素的进程Pi,j完成第k-1次迭代之后，就将Dk-1中的相应元素传给Pi-1,j与Pi+1,j当拥有第k列元素的进程Pi,j完成第k-1次迭代之后，就将Dk-1中的相应元素传给Pi,j-1与Pi,j+1当一个进程接收到相应的元素之后，就将其继续沿与接收数据时源进程所在方向相反的方向往前传送，直到到达边界位置2021/7/309Floyd算法(续)二维块调度2021/7/3010Floyd算法(续)二维块划分下的流水线模式并行算法第一行的n/p1/2个元素从P0,j出发往下传，第一列的n/p1/2个元素从Pi,0往右

6、传。在p1/2步后，这些元素到达边界，所用的时间为(n)后续每次迭代对应的元素每隔(n2/p)时间收到，从而进程右下角的进程在(n3/p)＋(n)时间内完成了其上的整个执行过程第n行的n/p1/2个元素从最下层进程往上传，第n列的n/p1/2个元素从最右边进程往左传。在p1/2步后，这些元素到达边界，所用的时间为(n)2021/7/3011