Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

Thanks

share|improve this question
add comment

1 Answer

up vote 8 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|improve this answer
    
Assuming that #P is not equal to FP of course! –  Emil Nov 9 '09 at 19:12
add comment

Your Answer

 
discard

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.