Shortest Path and Closure Algorithms
for Banded Matrices.
T. I. Dix and
C. N. Yee.
Department of Computer Science, Monash University, Australia 3168.
Partially supported by Australian Research Grant A48830856.
Shortest Paths 1
Abstract. A fast algorithm is given for the allpairs shortest paths problem for banded matrices having
bandwidth b. It solves the negativecycle problem and calculates all path lengths within the band in O(nb 2 )
time and calculates all other path lengths in O(n 2 b) time.
Keywords: shortest path, negative cycle, closure, banded matrix, algorithm.
Preprint to Inf. Proc. Lett., 40, pp317322, 30 Dec 1991, and TR 89/133 Dept. of Computer Science[*],
Monash University, Australia, 1989.
TR 89/133 & preprint to Inf. Proc. Lett. 40, pp.317322 1991
Shortest Paths 2