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 View the MathML source savings in 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.