A Shortest Path Algorithm for Banded Matrices by a Mesh Connection without Processor Penalty

Aohan MEI  Yoshihide IGARASHI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.3   pp.389-394
Publication Date: 1995/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms, Data Structures and Computational Complexity
parallel algorithms,  shortest paths,  banded matrices,  mesh connection,  systolic model,  semisystolic model,  

Full Text: PDF>>
Buy this Article

We give an efficient shortest path algorithm on a mesh-connected processor array for nn banded matrices with bandwidth b. We use a b/2b/2 semisystolic processor array. The input data is supplied to the processor array from the host computer. The output from the processor array can be also supplied to itself through the host computer. This algorithm computes all pair shortest distances within the band in 7n4b/21 steps.