Exercises 24.2-4

Let p(u) denote the number of paths start from u. For a node u, p(u) is equal to the summation of all p(v)+1, which there is a edge from u to v. We can compute the p value reverse topologically.

Exercises 24.2-3

Solution 1: For each node v, create a node v’. Remove out-edges of v from v then add to v’. Finally create a edge from v to v’ and the weight of this edge is the weight of v.

Solution 2: Add a new source vertex and link to nodes which has no in-edge. Then set all nodes’ in-edges’ weight to the weight of vertex.

Exercises 24.2-2

Because the last node has only in-edges, no out-edges.

Exercises 24.2-1