Parallel Dijkstra & Co.

made towards fast and work-efficient parallel algorithms
for the single source shortest path problem.
The only known O(n \log n + m) work parallel solution
applies Dijktra's algorithm, thus treats nodes one-by-one
and restricts parallelism to edge relaxations. Having running
time O(m/p + n \log n) for p processors, it is only advantageous
on dense graphs. We investigate modifications of Dijkstra's
algorithm that consider many nodes in parallel.

For a conservative approach, we present simple criteria
which divide Dijkstra's sequential algorithm into phases such
that all operations within a phase can be safely done in parallel.
An aggressive variant, a generalization of Dial's algorithm and
the Bellman-Ford algorithm, reveals even more parallelism.