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 community
Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

$\begingroup$
$\endgroup$

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

$\begingroup$
$\endgroup$

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.