An Efficient Parallel Algorithm for the All Pairs Shortest Path Problem using Processor Arrays with Reconfigurable Bus Systems

Technical Report B-13-99
July 29, 1999

Rajeev Wankar
Elfriede Fehr

Freie UniversitŠät Berlin, Institut fźür Informatik
* School of Computer Science, DAVV Indore, India


The all pairs shortest path problem is a class of the algebraic path problem. Many parallel algorithms for the solution of this problem appear in the literature. One of the efficient parallel algorithms on W-RAM model is given by Kucera. Though efficient, algorithms written for the W-RAM model of parallel computation are too idealistic to be implemented on the current hardware. In this report we present an efficient parallel algorithm for the solution of this problem using a relatively new model of parallel computing, Processor Arrays with Reconfigurable Bus Systems. The parallel time complexity of this algorithm is O(log2 n) and processors complexity is n2 x n x n.

Get the report in postscript or in PDF format here


File: pub/reports/