Abstract. We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source shortest path computations in O(m log α) time, where α = α(m, n) is the very slowly growing inverse-Ackermann function, m the number of edges, and n the number of vertices. As special cases our algorithm implies new bounds on both the all-pairs and single-source shortest paths problems. We solve the all-pairs problem in O(mn log α(m, n)) time and, if the ratio between the maximum and minimum edge lengths is bounded by n (log n) O (1) , we can solve the single-source problem in O(m + n log log n) time. Both these results are theoretical improvements over Dijkstra's algorithm, which was the previous best for real weighted undirected graphs. Our algorithm takes the hierarchy-based approach invented by Thorup.
The fastest APSP algorithm for sparse undirected weighted graphs is by Pettie and Ramachandran REF and runs in O(mn log α(m, n)) time.
A shortest path algorithm for real-weighted undirected graphs
in 13th ACMSIAM Symp. on Discrete Algs
Mathematics Computer Science