I/O-Efficient Undirected Shortest Paths with Unbounded Weights

Authors: 

Ulrich Meyer
Norbert Zeh

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2

Abstract: 

We present an algorithm for computing single-source shortest paths in undirected graphs with non-negative edge weights in O(sqrt(nm / B) log n + MST(n, m)) I/Os, where n is the number of vertices, m is the number of edges, B is the disk block size, and MST(n, m) is the I/O-cost of computing a minimum spanning tree. Our algorithm is based on our previous algorithm for graphs with bounded edge weights. Our contribution is the removal of the algorithm's dependence on the edge weights.

Tech Report Number: 
CS-2006-04
Report Date: 
June 15, 2006
AttachmentSize
PDF icon CS-2006-04.pdf706.5 KB