Hey, Is countinng the number of shortest paths in a weighted directed acyclic graph with nonnegative weights #Pcomplete?
If so, is there a proof I can read somewhere?
Thanks
Hey, Is countinng the number of shortest paths in a weighted directed acyclic graph with nonnegative weights #Pcomplete? If so, is there a proof I can read somewhere? Thanks 


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. 

