Dijkstra parallelization

Question

I'd like to know what is the best method to parallelize the Dijkstra algorithm.

Thanks.

Answer 1

There's a parallel algorithm for shortest paths from Carla Savage's 1977 Ph.D. thesis that consists of forming a square matrix with 0 on the diagonal entries, the length of the edges on the off-diagonal entries corresponding to edges, and a suitably large number for the remaining off-diagonal entries, and then repeatedly squaring this matrix in the (min,+) algebra.

After $\lceil\log_2 n\rceil$ squaring steps, the numbers in the resulting matrix are the distances between each pair of vertices. Each squaring step is easy to parallelize with logarithmic time and cubic work. So overall this algorithm takes $O(\log^2 n)$ time and $O(n^3\log n)$ work. With a little care (using a slightly more complicated algebra) this can be modified so that it also provides the first step of each shortest path in the same time and work bounds.

However, if you only want single source shortest paths rather than all pairs shortest paths, I don't know of anything that comes close to the total work of the sequential Dijkstra algorithm and that provides much in the way of a parallel speedup.

Answer 2

All-pairs shortest paths by repeated (min,+) matrix squaring is closely related to Floyd-Warshall, but they are not the same. In this respect, it is useful to think of Floyd-Warshall as (min,+) Gaussian elimination. Both approaches lend themselves to coarse-grained parallelisation, as discussed in http://dx.doi.org/10.1007/3-540-48224-5_15

The work required for repeated squaring can be improved from O(n^3 log n) to O(n^3) by the technique of selective path doubling, introduced by Alon, Galil and Margalit, and also discussed in the above paper.