Parallel calculation of shortest paths in sparse graphs on a systolic array

The applicability of the systolic/wavefront array concept for a particular class of algorithms is evaluated. A representative of this class if Ford´s algorithm (see E.L. Lawler, 1976) for the solution of the single-source-shortest-path problem under consideration of sparsity properties of the graph. Data transportation turns out to be the crucial point of the systolic realization. In the case of Ford´s algorithm two different kinds of data transport problems arise which are solved by broadcasting within a connected region and by use of a two-dimensional systolic sorting procedure. Further, a comparison between the systolic version of Ford´s algorithm and systolic realizations of Floyd´s method (see E.L. Lawler, 1976), which is the corresponding direct algorithm, are given