Efficient Parallel Shortest Path Algorithms for Banded Matrices

We present efficient parallel shortest path algorithms for an n x n banded matrix of bandwidth b. Our algorithm computes all pair shortest distances within the band in time O(nb^{2}/p + l(b)logblog(n/b)) on the PRAM using p processors, where l(b) is logb on the EREW PRAM, loglogb on the CRCW PRAM, and a constant on the randomized CRCW PRAM. It computes all pair shortest distances in time O(n^{2}b/p+l(B)logblog(n/b)) using p processors.