文档介绍：Floyd 算法,又称传递闭包方法,其实质就是邻接矩阵自乘 n 次,算法的时间复杂度为。下面就是扩充了路径矩阵的 Floyd 串行算法的描述: Floyd 串行算法输入: 顶点数目 n; 图的邻接矩阵 Array; 初始化后的路径矩阵 Path 计算: /*Serialed Floyd Algorithm*/ void Floyd_Proc(unsigned int **Array, unsigned int **Path){ int i,j,k; for (k= 0;k< Nodes; k ++) for (i= 0;i< Nodes; i ++) for (j= 0;j< Nodes; j ++) if( Array[i][j] >( Array[i][k] + Array[k][j]) ) { Array[i][j] = Array[i][k] + Array[k][j]; Path [i][j] = Path[i][k]; } } 输出: 变换后的矩阵 Array 和 Path 并行 Floyd 算法实现为了方便起见,约定处理机数为 p=p×p ,数据规模 n,p 可以整除 n 。如果有 p 台处理机,那么就划分 p 个任务,也保证 p 台处理机所负担的任务数据量相同。下面是二维均匀块分配方法分解任务的 Floyd 并行算法。二维任务划分方法的 Floyd 并行算法输入: 顶点数目 n; 图的邻接矩阵 array; 初始化后的路径矩阵 path 到主机(0 号进程) 计算: (1) 如果是主机(0 号进程), 根据数据规模 n 和处理机数目 p 来划分任务, 按照棋盘式均匀的分解的方法, 发送 array 和 path 的数据块到相应的处理机,各处理机在本地存储为 jobarra y和 jobpath 。(2) for (k= 0;k< n;k ++) 循环开始。(3) 各个处理器计算当前需要广播的第 k行 array 所在的处理机号。如果在本地, 那么从 jobarray 矩阵中选取出相应的一行数据,存储在 temparrayA [] ,并向同一列处理机广播。各个处理器计算当前需要广播的第k列 array 和 path 所在的处理机号。如果在本地, 那么从 jobarray 和 jobpath 矩阵中选取出相应的一列数据,分别存储在 tem parrayB []和 temppath [] ,并向同一行处理机广播。(4) 各个处理器执行并行计算: for (i= 0;i <;i ++) for (j= 0;j <;j ++) if( jobarray[i][j] >( temparrayB[i] + temparrayA[j] )) { jobarray[i][j] = temparrayB[i] + temparrayA [j]; path[i][j] = temppath[i]; } (5) 跳(2) 直至 k 的循环结束转(6) ; (6) 各个处理器返回运算结果 jobarray 和 jobpath 两个矩阵到主机(0 号进程) ,主机在将其归并到本地的 array 和 path 矩阵。释放空间。输出: 变换后的矩阵 array 和 path 并行 Floyd 算法复杂度分析在上述算法中,第(4) 步是用来更新矩阵 array 和 p