Parallel algorithm for shortest paths

An algorithm for finding a shortest path between each pair of nodes of a positive arc weighted graph on a shared memory model of a single instruction-stream multiple data-stream computer is proposed. The time complexity of the algorithm is of O(log d . log n), where d and n denote the diameter and the number of nodes of the graph, respectively. At most, O(n3) processors are required to achieve this time bound.