Computing Undirected Shortest Paths with Comparisons and Additions
Seth Pettie, Vijaya Ramachandran · 2001
We study undirected shortest paths problems in a natural model of computation, namely one which gives us two numerical operations: comparisons and additions. This is the model assumed by such standards as Dijkstra's algorithm, the Bellman-Ford algorithm, and the Floyd-Warshall algorithm, and is the usual model for proving lower bounds on shortest path problems. We present an algorithm for undirected single source shortest paths (SSSP) with arbitrary real edge weights which performs O(SSSP (m;n)+m log(m;n)+n log log r) comparisons and additions. Here SSSP is the comparison-addition complexity of the problem, r the ratio of the maximum-to-minimum edge length, and Tarjan's inverse-Ackermann function. By the usual convention, m and n are the number of edges and vertices respectively. Our algorithm is implementable on a pointer machine with time complexity O(m(m;n) + n log log r). This represents an improvement over Dijkstra's algorithm so long as r < 2 n o(1) For the undirected all pairs shortest paths (APSP) problem we present an algorithm that runs in time O(mn(m;n)) time while performing O(mn log(m;n)) comparisons and additions. This time bound improves on the best results known for this problem when the input graph is sparse, i.e., when m = o(n logn). Our algorithmsmake extensive use of the graph's minimum spanning tree in order to compute SSSP quickly, and our approach is based on a renement of Thorup's component hierarchy data structure, which was developed under the more powerful RAM model.