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
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityHey, 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
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.