# I/O-Efficient Undirected Shortest Paths with Unbounded Weights

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

Attachment | Size |
---|---|

CS-2006-04.pdf | 706.5 KB |