Computing shortest paths with comparisons and additions
Seth Pettie, Vijaya Ramachandran · 2002
We present an undirected all-pairs shortest paths (APSP) algorithm which runs on a pointer machine in time O(mnot(m, n)) while making O(ran log a(m, n)) compar-isons and additions, where m and n are the number of edges and vertices, respectively, and a(ra, n) is Tarjan's inverse-Ackermann function. This improves upon all previous com-parison & addition-based APSP algorithms when the graph is sparse, i.e., when m = o(n log n). At the heart of our APSP algorithm is a new single-source shortest paths algorithm which runs in time O(ma(m,n) + nloglogr) on a pointer machine, where r is the ratio of the maximum-to-minimum edge length. So long as r < 2 '~°(a) this algorithm is faster than any implemen-tation of Dijkstra's classical algorithm in the comparison-addition model. For directed graphs we give an O(ra + nlogr)-time comparison & addition-based SSSP algorithm on a pointer machine. Similar algorithms assuming integer weights or the RAM model were given earlier.