hide
Free keywords:
-
Abstract:
We show how to compute single-source shortest paths in undirected graphs with
non-negative edge lengths in 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. For sparse graphs, the new algorithm
performs I/Os. This result removes our previous algorithm’s dependence on the
edge lengths in the graph.
