图的最短路径和传递闭包的并行算法

A PARALLEL ALGORITHM FOR COMPUTING THE SHORTEST PATHS AND THE TRANSITIVE CLOSURES

1.图的最短路径 给定一赋权有向图G=(V,E),假设G中没有带负权圈的顶点,Floyd给出了一个计算G的所有顶点对v_i,v_j之间最短路径算法。在该算法中,用带权邻接矩阵cosT表示图,并规定cosT(i,j)=∞若(i,j)不属于E和cosT(i,j)=0,i,j=0,…,n-1,该算法的设计思想是按下面的递推规则依次产生矩阵序列A^0,…,A^(n-1),其中A^(n-1)即是G的所有顶点对之间最短路径的长度。