Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

Thanks.

share|improve this question
    
Try a literature search for parallel shortest path. You could start with e.g. "A Randomized Parallel Algorithm for Single-Source Shortest Paths" by Philip N. Klein and Sairam Subramanian in J. of Algorithms and papers citing it. –  Warren Schudy Dec 23 '10 at 20:12
    
thanks for the link. I'll take a look at that paper. –  jutky Dec 26 '10 at 22:12
add comment

2 Answers

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.

share|improve this answer
    
Thanks for the idea. But I use a slight variation of the single source shortest path Dijkstra. –  jutky Dec 9 '10 at 22:55
    
Is what you are describing above the same as what was based on an idea of Steve Hedetniemi as described here?: highered.mcgraw-hill.com/sites/dl/free/0072880082/299355/… and also here: deepblue.lib.umich.edu/handle/2027.42/59763 –  Joseph Malkevitch Dec 10 '10 at 3:04
    
The matrix algebra part is the same, but the references you give don't seem to have the squaring trick for getting high powers of the matrix much more quickly than multiplying together n copies of the matrix. So they end up doing O(n^4) work, instead of closer to O(n^3) in Savage's version, and they're not as parallel. –  David Eppstein Dec 10 '10 at 3:20
    
Savage's algorithm is the natural parallelization of the Kleene-Roy-Floyd-Warshall algorithm: en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm –  JɛffE Dec 10 '10 at 4:36
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.