Description
A classic problem in algorithmic graph theory is to find shortest paths, and a common variant is the all-pairs shortest path problem (APSP). We consider non-negatively weighted APSP. Due to its simplicity and efficiency, the Floyd-Warshall algorithm is frequently used to solve APSP in practice.
We propose a combination of the Floyd-Warshall algorithm with a hourglass-like tree structure, which reduces the number of path combinations that have to be examined. Only those path combinations that provably cannot change the values in the shortest path matrix are omitted. The resulting algorithm is simple to implement and uses no fancy data structures.
In empirical tests, the new algorithm is faster than the Floyd-Warshall algorithm for random complete graphs on $256-4096$ nodes by factors of $3.5 - 4.8$x. When we inspect the number of path combinations examined compared to the Floyd-Warshall algorithm, they are reduced by a factor of $12 - 90$x. All code was written in \textit{C}.
We show that the worst-case complexity of the new algorithm does not change. In light of this, we focus our theoretical analysis on the average-case complexity, and show why it might be substantially lower than Floyd-Warshall's (this is a work in progress).
Primary authors
Prof.
Andrej Brodnik
(University of Primorska)
Mr
Marko Grgurovič
(University of Primorska)
