Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ (i.e., the number of vertices or edges) and the total work time may be worse than $O(m + n\log n)$.The most suitable algorithm I found is the one of Han, Pan, Reif in the paper Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs. They present an algorithm for the all pair shortest path problem that runs in $O(\log n \log\log n)$ time in the CRCW model (concurrent read, concurrent write; that's okay for my scenario) and uses $O(n^3/(\log \log n \log^{7/6} n))$ processors.Although the running time is perfect, I wonder if the number of processors or the total work time can be improved when restricting to the single-source shortest path problem. However, I didn't find anything comparable. There are many non-deterministic algorithms running on random graphs and many variations of the Dijkstra algorithm with linear running time. 
Parallel single source shortest path algorithm
algorithms;shortest path;parallel computing