Parallel algorithms for solving aggregated shortest-path problems

We consider the problem of computing in parallel all pairs of shortest paths in a general large-scale directed network of N nodes. A hierarchical network decomposition algorithm is provided that yields for an important subclass of problems log N savings in a computation time over the traditional parallel implementation of Dijkstra's algorithm. Error bounds are provided for the procedure and are illustrated numerically for a problem motivated by intelligent transportation systems.