An algebraic decomposed algorithm for all pairs shortest paths

Publication date 7 November 2014

Published in Pacific Journal of Optimization (Search for Journal in Brave)

Full work available at URL http://www.yokohamapublishers.jp/online2/oppjo/vol10/p561.html

algebraic method all pairs LU decomposition shortest path

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

Cited in

(1)

Analysis of Dehn's algorithm by critical pairs

This page was built for publication: An algebraic decomposed algorithm for all pairs shortest paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2928417)