ALCOMFT-TR-03-61

Ulrich Meyer and Norbert Zeh
I/O Efficient Undirected Shortest Paths
MPI. Work packages 1 and 4. October 2003.

Abstract: We present an I/O-efficient algorithm for the single-source shortest path problem on undirected graphs G=(V,E). Our algorithm performs \O(\sqrt{(VE/B)log₂(W/w)}+\sort(V+E)loglog(VB/E)) I/Os\footnote\sort(N)=Theta((N/B)log_M/B(N/B)) is the I/O-complexity of sorting N data items., where w \in R^+ and W \in R^+ are the minimal and maximal edge weights in G, respectively. For uniform random edge weights in (0,1], the expected I/O-complexity of our algorithm is \O(\sqrt{VE/B}+((V+E)/B)log₂B+\sort(V+E)).

Postscript file: ALCOMFT-TR-03-61.ps.gz (96 kb).