Fast parallel algorithm for all-pairs shortest path problem and its VLSI implementation
S. Dey, Pradip K. Srimani · IEE Proceedings E Computers and Digital Techniques · 1989
We present a new parallel algorithm to solve the all-pairs shortest path problem in a given graph which is considerably faster than the most recently published algorithm [7] for the same problem. Next we propose a suitable VLSI systolic architecture to map our algorithm and evaluate the performance of the proposed architecture in terms of execution time and inter-processor communication time. We show that our implementation has O(log2n) execution time (compare-exchange time) and O(n log n) communication time compared to O(n log n) and O(n2) in [7].