An algebraic decomposed algorithm for all pairs shortest paths (Q2928417)

Proposed is an algebraic all pairs shortest path algorithm based on LU (lower/upper triangular matrix) decomposition of the arc-lengths matrix (measure matrix). This contrasts a recently prevailing approach to shortest path algorithms which achieve their convergence through graphical operations.NEWLINENEWLINENEWLINEThe new algorithm identifies negative cycles of the graph in fewer iterations than the Floyd-Warshall algorithm does and its efficiency is no worse than those of the Floyd-Warshall algorithm on a complete graph. Some computational experiments were performed on 18 network families randomly created by two network generators SPGRID and SPRAND [\textit{B. V. Cherkassky} et al., Math. Program. 73, No. 2 (A), 129--174 (1996; Zbl 0853.90111)] as well. Results of the experiments indicate that the numerical performance of the new algorithm is better than those of the Floyd-Warshall algorithm in 12 out of 18 cases.