(2)for i-0 to N-1 do ifi≠ s then dist(i)=∞ (4)for=0 to N-l do (4.1)从ⅥL中找一个顶点u,使得dist(u)最小 (4.2)for(每个顶点veVL)and(<uv>∈E)d if dist(u)+w(u, v)<dist(v) then dist( v)=dist(u)+w(u, v) endif 5)VL=VL-ful endfor 132最短路径并行算法 在上一小节串行算法的基础上,这里将其并行化。思路如下 (1)上述算法的(1)(2)两步中,每个处理器分派n=N/p个节点进行初始化 (2)第(4.1)步可以并行化为:首先每个处理器分派n个节点分别求局部最小值,然后 再p个处理器合作求全局最小值,最后再将这一最小值广播出去。p个处理器合作方法如下: 当p为偶数时,后p/2个处理器将自己的局部最小值分别发送到对应的前p/2个处理器中, 由前p/2个处理器比较出2个局部最小值中相对较小者并保留。当p为奇数时,设p=2h+1, 则后h个处理器的值分别发送到前h个处理器中,比较并保留小值。一次这样的循环过后 p个最小值减少了一半,两次后,变为1/4,如此一层一层的比较,lgP次循环后,就可以 得出唯一的全局最小值 (3)第(4.2)步可以每个处理器分配n个顶点,然后独立进行更新dst的操作。 根据以上思路,最短路径的并行算法见算法15.5,使用了p个处理器,其时间复杂度 为O(N2/p+Ngp)。这里的实现算法和对应的源程序中,处理器0只进行输入输出工作,不 参与任何其它计算;因此实际参加运算的处理器为p1个,所以有n=Np-1);另外,布尔 数组bdst用来标记各顶点是否已从ⅥL中取出 算法155 Dijkstra并行算法 输入:边权邻接矩阵W(约定顶点i,j之间无边连接时w(ij)=∞,且w(i)=0)、 待计算顶点的标号s 输出:dis(0:N-1),其中ds(表示顶点s到顶点i的最短路径(1≤i≤N edure Dijkstra-parallel Begin /*以下对应源程序中 ReadMatrixO函数* (1)处理器0读入边权邻接矩阵W /*以下初始化dst和 bdist数组,对应源程序中IntO函数* 2)for每个顶点 i par do if i=s then bdist(i= true dist(i)=w(i, s)(2) for i=0 to N-1 do if i≠s then dist(i) = ∞ endfor (3) VL = V (4) for i=0 to N-1 do (4.1) 从 VL 中找一个顶点 u，使得 dist(u)最小 (4.2) for (每个顶点 v∈VL) and (<u,v>∈E) do if dist(u)+w(u,v)<dist(v) then dist(v) = dist(u)+w(u,v) endif endfor (5) VL = VL-{u} endfor End 1.3.2 最短路径并行算法 在上一小节串行算法的基础上，这里将其并行化。思路如下： ⑴ 上述算法的(1)(2)两步中，每个处理器分派 n=N/p 个节点进行初始化。 ⑵ 第(4.1)步可以并行化为：首先每个处理器分派 n 个节点分别求局部最小值，然后 再 p 个处理器合作求全局最小值，最后再将这一最小值广播出去。p 个处理器合作方法如下： 当 p 为偶数时，后 p/2 个处理器将自己的局部最小值分别发送到对应的前 p/2 个处理器中， 由前 p/2 个处理器比较出 2 个局部最小值中相对较小者并保留。当 p 为奇数时，设 p=2h+1, 则后 h 个处理器的值分别发送到前 h 个处理器中，比较并保留小值。一次这样的循环过后， p 个最小值减少了一半，两次后，变为 1/4，如此一层一层的比较，㏒ P 次循环后，就可以 得出唯一的全局最小值。 ⑶ 第(4.2)步可以每个处理器分配 n 个顶点，然后独立进行更新 dist 的操作。 根据以上思路，最短路径的并行算法见算法 15.5，使用了 p 个处理器，其时间复杂度 为 O(N2 /p+N ㏒ p)。这里的实现算法和对应的源程序中，处理器 0 只进行输入输出工作，不 参与任何其它计算；因此实际参加运算的处理器为 p-1 个，所以有 n=N/(p-1)；另外，布尔 数组 bdist 用来标记各顶点是否已从 VL 中取出。 算法 15.5 Dijkstra 并行算法 输入：边权邻接矩阵 W（约定顶点 i，j 之间无边连接时 w(i,j)=∞，且 w(i,i) = 0）、 待计算顶点的标号 s 输出：dist(0 : N-1)，其中 dist(i)表示顶点 s 到顶点 i 的最短路径(1≤i≤N) procedure Dijkstra-parallel Begin /* 以下对应源程序中 ReadMatrix()函数 */ (1) 处理器 0 读入边权邻接矩阵 W /* 以下初始化 dist 和 bdist 数组，对应源程序中 Init()函数 */ (2) for 每个顶点 i par_do if i=s then dist(i) = 0 bdist(i) = TRUE else dist(i) = w(i,s)