An O(n(n2/p+logp)) parallel algorithm to compute the all pairs shortest paths and the transitive closure

Multiprocessors with shared memory structured as a complete binary tree are considered for use with a parallel algorithm to compute the all pairs shortest paths and the reflexive transitive closure in a weighted directed graph. The time complexity of the parallel algorithm is O(n(n²/p+logp)), where n is the number of vertices in the graph and p(¸•n²) is the number of processors used. The Ada language is used to implement the algorithm.