endfor (2.3)for每个i:0≤i≤N- I par do endfor (2. 4) for i=l to log n do /*以下对应源程序中 CC to CO函数* for每个j:0≤j≤N-1 par do C()=C(C() endfor /*以下对应源程序中 cd to d)函数* (2.5)for每个i:0≤i≤N- I par do D()=min{C(),D(C()} endion endfor MPⅠI源程序请参见章末附录 13单源最短路径 单源最短路径 Single source shortest path)问题是指求从一个指定顶点s到其它所有顶点 之间的距离,因为是单一顶点到其它顶点的距离,所以称为单源。设图G(VE)是一个有向 加权网络,其中V和E分别为顶点集合和边集合,其边权邻接矩阵为W,边上权值w(ij)> 设dis(i)为最短的路径长度,即距离,其中s∈Ⅴ且i≠s。这里采用著名的 Dijkstra算 法,并将其并行化 131最短路径串行算法 Dijkstra算法( Dijkstra Algorithm)是单源最短路径问题的经典解法之一,基本思想如 下 假定有一个待搜索的顶点表ⅥL,初始化时做:dst(s)←0,dist(i)=∞(i≠s),ⅥL=V 每次从VL(非空集)中选取这样的一个顶点u,它的dsu)最小。将选出的u点作为搜索 顶点,对于其它还在L内的顶点v,若<u>∈E而且dst(u)+w(uv)<dst(v),则更新dis(yv) 为disu)+wuv),同时从VL中将u删除,直到VL成为空集时算法终止 算法154中给出了最短路径问题的 Dijkstra串行算法,其时间复杂度为ON2) 算法154 Dijkstra串行算法 输入:边权邻接矩阵W(约定顶点i,j之间无边连接时w(ij)=∞,且w(i,i)=0) 待计算顶点的标号s 输出:dst(0:N-1),其中dst(表示顶点s到顶点i的最短路径(1≤i≤N procedure Dijkstra Begin 1)dist(s)=0endfor (2.3) for 每个 i : 0 ≤ i ≤ N-1 par_do D(i) = C(i) endfor (2.4) for i=1 to ㏒ N do /* 以下对应源程序中 CC_to_C()函数 */ for 每个 j : 0 ≤ j ≤ N-1 par_do C(j) = C(C(j)) endfor endfor /* 以下对应源程序中 CD_to_D()函数 */ (2.5) for 每个 i : 0 ≤ i ≤ N-1 par_do D(i) = min{ C(i), D(C(i)) } endfor endfor End MPI 源程序请参见章末附录。 1.3 单源最短路径 单源最短路径(Single Source Shortest Path)问题是指求从一个指定顶点s到其它所有顶点 i 之间的距离，因为是单一顶点到其它顶点的距离，所以称为单源。设图 G(V,E)是一个有向 加权网络，其中 V 和 E 分别为顶点集合和边集合，其边权邻接矩阵为 W，边上权值 w(i,j) > 0，i,j∈V，V={0,1,…,N-1}。 设 dist( i )为最短的路径长度，即距离，其中 s∈V 且 i≠s。这里采用著名的 Dijkstra 算 法，并将其并行化。 1.3.1 最短路径串行算法 Dijkstra 算法(Dijkstra Algorithm)是单源最短路径问题的经典解法之一，基本思想如 下。 假定有一个待搜索的顶点表 VL，初始化时做： dist(s)←0，dist(i)=∞(i≠s)，VL=V。 每次从 VL（非空集）中选取这样的一个顶点 u，它的 dist(u)最小。将选出的 u 点作为搜索 顶点，对于其它还在 VL 内的顶点 v，若<u,v>∈E,而且 dist(u)+w(u,v)<dist(v)，则更新 dist(v) 为 dist(u)+w(u,v)，同时从 VL 中将 u 删除，直到 VL 成为空集时算法终止。 算法 15.4 中给出了最短路径问题的 Dijkstra 串行算法，其时间复杂度为 O(N2 )。 算法 15.4Dijkstra 串行算法 输入：边权邻接矩阵 W（约定顶点 i，j 之间无边连接时 w(i,j)=∞，且 w(i,i) = 0）、 待计算顶点的标号 s 输出：dist(0 : N-1)，其中 dist(i)表示顶点 s 到顶点 i 的最短路径(1≤i≤N) procedure Dijkstra Begin (1) dist(s) = 0