Abstract:
We present a cache-oblivious algorithm for computing single-source shortest paths in undirected graphs with non-negative edge lengths. The algorithm incurs O(sqrt(nm log w)/B+(m/B) log n +MST (n, m)) memory transfers on a graph with n vertices, m edges, and real edge lengths between 1 and W; B denotes the cache block size, and MST(n, m) denotes the number of memory transfers required to compute a minimum spanning tree of a graph with n vertices and m edges. Our algorithm is the first cache-oblivious shortest-path algorithm incurring less than one memory transfer per vertex if the graph is sparse (m = O(n)) and W = 2^o(B).This paper was authored by Luca Allulli, Peter Lichodzijewski, and Norbert Zeh, and appeared in SODA 2007.