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(nlogn) communication time compared to O(nlogn) and O(n2) in [7].