H. Edwin Romeijn, Robert L. Smith
Parallel algorithms for solving aggregated shortest path problems
We consider the problem of finding all pairs of shortest paths within a large scale directed network. We form nested partitions of the original micro-nodes to create a hierarchy of macro-nodes. Combining all pairs of shortest paths within macro-nodes at each level yields a hierarchical decomposition algorithm that reduces computation time by as much as O(N½). Motivated by an IVHS application, bounds on resulting errors are explored accompanied by an empirical test of their magnitude.