Shortest path and closure algorithms for banded matrices (Q1183497): Difference between revisions

The proposed algorithm is a modification/extension of Floyd's: it finds all shortest paths in a \(n\times n\) distance matrix, viewed as a (weighted finite) directed (simple) graph, and has improved order \(O(nb^ 2)\) for time complexity, compared to Floyd's \(O(n^ 2)\); \(b\) is the bandwidth. (Also described in a report of Monash University 1989.) Applications mentioned as possible are to other closure problems in OR, with linear inequalities, other all-pair shortest path problems in networks. Negative distances are permitted, whereby a negative cycle is detected in \(O(nb^ 2)\) time. Description of Floyd's is placed at the front. The idea is to preprocess the matrix for finding the limiting elements of the band and restrict Floyd's, so that it stays between these limits. For achieving the smaller order, the input must be in ``compressed'' format, e.g. as adjacency lists of the underlying graph. The actual execution uses the same ``elementary'' operations as Floyd's, mainly \(f_{ik}=\min(x,y+z)\), but about five times as much of the latter ones, so it may be faster at least for \(b<n/\sqrt 5\).