Hey, Is countinng the number of shortest paths in a weighted directed acyclic graph with nonnegative weights #P-complete?

If so, is there a proof I can read somewhere?



No, it's easily solved in polynomial time. Suppose you have some designated start vertex s from which you want to count shortest paths. Then, if D(v) denotes the distance from s to v and N(v) denotes the number of shortest paths from s to v, then these two quantities may be computed by a single pass through all the vertices of the DAG, in a topological ordering: if v=s then D(v)=0 and N(v)=1, else D(v) is the minimum of D(w)+lenghth(w,v) over edges from w to v and N(v) is the sum of N(w) over vertices w achieving that minimum value.

The assumption of nonnegative weights is irrelevant.

  • $\begingroup$ Assuming that #P is not equal to FP of course! $\endgroup$ – Emil Nov 9 '09 at 19:12

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.