Finding the shortest path in a DAG is extremely easy:

See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

However, I cannot find a way of parallelising this code. Is there a way of doing that?

  • 1
    $\begingroup$ 1. Please remove the pseudocode and just give us the main idea. A wall of text with code is hard to read. Is the idea to just topologically sort and then process the nodes in top. sorted order (basically, the standard algorithm given in every algorithms textbook)? If so, you can say so. 2. What research have you done? Where have you looked? Have you done a literature search? $\endgroup$
    – D.W.
    Jun 4 '15 at 19:20

In complexity theory, the notion of P-complete (wiki) denotes the problems that are (widely believed) difficult to parallelize effectively. (Note: I am not good at this area. Please correct me if I am wrong.)

One typical P-complete problem is

Circuit Value Problem (CVP): Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate.

The "shortest path in DAG" problem is similar to CVP. I think it is not hard for you to find a reduction in the literature with, for example, the paper A Compendium of Problems Complete for P as a starting point.

A positive side: Of course you can layer the nodes in DAG and parallel the computation layer by layer to some extent.

  • $\begingroup$ This is helpful. Thanks. For the original poster: see cs.stackexchange.com/q/1415/755 for explanations of P-completeness and some significant caveats about why P-completeness can't really be equated with "efficiently parallelizable in practice". $\endgroup$
    – D.W.
    Jun 5 '15 at 4:37
  • $\begingroup$ Thank you. So the best one can do is creating a layered graph and then process each layer in parallel, right? $\endgroup$
    – Charles G.
    Jun 5 '15 at 6:47
  • $\begingroup$ @CharlesG. It probably is (I cannot say that for sure). $\endgroup$
    – hengxin
    Jun 5 '15 at 6:52
  • $\begingroup$ From what I know, the relation between this complexity theory view on parallelisability and parallelisability in practice is effectively nil. $\endgroup$
    – Raphael
    Jun 5 '15 at 8:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.