Solving the Nearly Symmetric All-Pairs Shortest-Path Problem

Gerald G. Brown () and W. Matthew Carlyle ()
Additional contact information
Gerald G. Brown: Naval Postgraduate School, Monterey, California 93943
W. Matthew Carlyle: Naval Postgraduate School, Monterey, California 93943

INFORMS Journal on Computing, 2020, vol. 32, issue 2, 279-288

Abstract: We introduce a simple modification to the repeated shortest-path algorithm for the all-pairs shortest-path problem that adds a cumulative distance label update at each iteration based on the shortest-path tree from the prior iteration. We have implemented and tested our update using several shortest-path algorithms on a range of test networks of varying size, degree, and “skewness” (i.e., asymmetry) of costs on antisymmetric arcs, and we find that it provides a significant speedup to any such algorithm, except for cases either in which the underlying graph is extremely sparsely connected (or even disconnected) or when the arc costs are highly nonsymmetric. An added charm is that our best-modified method preserves the polynomial worst case runtime of its label-correcting antecedent. As with other repeated shortest-path algorithms, it is significantly faster than the Floyd–Warshall algorithm on sparsely connected networks and even some fairly densely connected networks.

Keywords: all-pairs shortest paths; repeated shortest-path algorithm; label-correcting algorithms; two-queue; symmetric costs (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0873 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:2:p:279-288

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().