Parallel runtime of algorithm Parallel Algorithm Based on Dijsktra's Algorithm For p greater than n , can get further improvements by partitioning p processors into n partitions, each with processors. Then parallelize each single source shortest path algorithm using processors using previous algorithm. On a p -processor mesh, assume mesh is partitioned into n submeshes of size . Parallel runtime of algorithm is Floyd's Algorithm for All-Pairs Shortest Paths Vertices are Consider subset of vertices for some . For any pair of vertices , consider all paths from to whose intermediate vertices belong to the set .
Complexity is for runtime and for memory.
Floyd's Algorithm Parallel Version of Floyd's Algorithm Assign task of computing matrix for each value of k to a set of processors. If p processors are available, partition matrix into p parts. Each processor computes values for its partition. Partitioning the Distance Matrix Communication Patterns in Parallel Algorithm Parallel Version of Floyd's Algorithm Analysis of Parallel Algorithm Assume hypercube connection with cut-thorugh routing with p processors. Map a mesh on virtual hypercube.