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.

  • 2
    $\begingroup$ What research have you done? Searching "Parallel Single Shortest Path Algorithm" into Google gives a few papers. $\endgroup$ – Ryan Jul 24 '14 at 14:29
  • $\begingroup$ Yep, but as far is I can see they are all either randomized or run in $\omega(\log n)$ time. Did you find another one? $\endgroup$ – user1742364 Jul 24 '14 at 15:55
  • $\begingroup$ @user1742364, you might edit your question to show us what research you've done. Have you done a careful literature search? (This means looking for papers on Google Scholar, then using their related work sections and what cites them to find other relevant papers, repeat until done.) E.g., if you've done a careful literature search, you could tell us that in the question and list the closest papers you've found and what their result is and how it differs from what you are looking for. Show us what you've tried on your own and what research you've already done, in the question. $\endgroup$ – D.W. Jul 24 '14 at 21:51
  • $\begingroup$ Okay, I added some remarks. Hope it helps. $\endgroup$ – user1742364 Jul 25 '14 at 8:05
  • $\begingroup$ Note that $o(n) \cap \omega(\log n) \neq \emptyset$. $\endgroup$ – Raphael Jul 25 '14 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.