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

Thanks.
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.