bdist(i= false endif endor /*以下是算法主循环,对应源程序中 FindMin Wayo函数* (3)for i=l to N-l do /*各处理器找出自己负责范围内未搜索节点中最小的dst* (31)for每个顶点 j par_ do index=min(j bdistO=FALSE) num=dist(index) endfor *以下各处理器协作对p-1个 index求最小* caninum=p for j=l to log(p-1)p if calum mod2=0then∥本次循环参加比较的数据个数为偶数 (i)calum =calum/2 (ii)序号大于caum的处理器将 index和num发送给序号比自己小 calum的处理器 (i)l序号小于 calum的处理器(不包含0号)在自己原有的和收到 的两个num之间,比较并保留较小者,同时记录对应的 index 本次循环参加比较的数据个数为奇数 (i)calum=(calum+1)/2 (i)序号大于 canon的处理器将 index和num发送给序号比自己小 calum的处理器 (i)序号小于 cannon的处理器(不包含0号)在自己原有的和收到 的两个num之间,比较并保留较小者,同时记录对应的ind endif endor (3.3)处理器1广播通知其它处理器自己的num和 index /*以下并行更新* 34)for每个顶点 j par_ do if bdist(=FALSE then dist()=min( dist(), num+wG, index)) endif endfor (3.5)顶点 index对应处理器将对应的 bdist( index)更改为TRUE MPI源程序请参见所附光盘。 14最小生成树 一个无向连通图G的生成树是指满足如下条件的G的子图T:①T和G顶点数相同 ②T有足够的边使得所有顶点连通,同时不出现回路。如果对G的每条边指定一个权值, 那么,边权总和最小的生成树称为最小代价生成树,记为MCST( Minimum Cost Spanningbdist(i) = FALSE endif endfor /* 以下是算法主循环，对应源程序中 FindMinWay()函数 */ (3) for i=1 to N-1 do /* 各处理器找出自己负责范围内未搜索节点中最小的 dist */ (3.1) for 每个顶点 j par_do index = min{ j | bdist(j)=FALSE } num = dist(index) endfor /* 以下各处理器协作对 p-1 个 index 求最小 */ (3.2) calnum = p-1 for j=1 to ㏒(p-1) par_do if calnum mod 2=0 then //本次循环参加比较的数据个数为偶数 (ⅰ) calnum = calnum/2 (ⅱ) 序号大于 calnum 的处理器将 index 和 num 发送给序号比自己小 calnum 的处理器 (ⅲ) 序号小于 calnum 的处理器（不包含 0 号）在自己原有的和收到 的两个 num 之间，比较并保留较小者，同时记录对应的 index else //本次循环参加比较的数据个数为奇数 (ⅰ) calnum = (calnum+1)/2 (ⅱ) 序号大于 calnum 的处理器将 index 和 num 发送给序号比自己小 calnum 的处理器 (ⅲ) 序号小于 calnum 的处理器（不包含 0 号）在自己原有的和收到 的两个 num 之间，比较并保留较小者，同时记录对应的 index endif endfor (3.3) 处理器 1 广播通知其它处理器自己的 num 和 index /* 以下并行更新 */ (3.4) for 每个顶点 j par_do if bdist(j)=FALSE then dist(j) = min{ dist(j), num+w(j,index) } endif endfor (3.5) 顶点 index 对应处理器将对应的 bdist(index)更改为 TRUE endfor End MPI 源程序请参见所附光盘。 1.4 最小生成树 一个无向连通图 G 的生成树是指满足如下条件的 G 的子图 T：①T 和 G 顶点数相同； ②T 有足够的边使得所有顶点连通，同时不出现回路。如果对 G 的每条边指定一个权值， 那么，边权总和最小的生成树称为最小代价生成树，记为 MCST（Minimum Cost Spanning