I/O-Efficient Shortest Path Algorithms for Undirected Graphs with Random or Bounded Edge Lengths
We present I/O-efficient single-source shortest path algorithms for undirected graphs. Our main result is an algorithm with I/O complexity O(root nm log L)/ B + MST(n, m)) on graphs with n vertices, m edges, and arbitrary edge lengths between 1 and L; MST(n, m) denotes the I/O complexity of computing a minimum spanning tree; B denotes the disk block size. If the edge lengths are drawn uniformly at random from ( 0, 1], the expected I/O complexity of the algorithm is O(root nm/ B + ( m/ B) log B + MST(n, m)). A simpler algorithm has expected I/O complexity O(root nm log B)/ B + MST(n, m) for uniformly random edge lengths.
shortest path algorithms algorithms theory graph algorithms i/o-efficient algorithms memory hierarchies