More Parallelism in Dijkstra's Single-Source Shortest Path Algorithm

Michael Kainer, Jesper Larsson Träff

Dijkstra's algorithm for the Single-Source Shortest Path (SSSP) problem is notoriously hard to parallelize in $o(n)$ depth, $n$ being the number of vertices in the input graph, wit…