MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
up vote 9 down vote accepted

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.

share|cite|improve this answer
Assuming that #P is not equal to FP of course! – Emil Nov 9 '09 at 19:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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