Solving the Nearly Symmetric All-Pairs Shortest-Path Problem
Gerald G. Brown, W. Matthew Carlyle
INFORMS Journal on Computing · 2020 · Volume 32 · Issue 2
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
Enable JavaScript for citation tools and additional paper interactions.