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
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-99-13.ps.gz