Number of Shortest paths problem

Question

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

Answer 1

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.