24.2 Singlesource shortest paths in directed acyclic graphs
24.21
Run $\text{DAGSHORTESTPATHS}$ on the directed graph of Figure 24.5, using vertex $r$ as the source.

$d$ values:
$$ \begin{array}{cccccc} r & s & t & x & y & z \\ \hline 0 & \infty & \infty & \infty & \infty & \infty \\ 0 & 5 & 3 & \infty & \infty & \infty \\ 0 & 5 & 3 & 11 & \infty & \infty \\ 0 & 5 & 3 & 10 & 7 & 5 \\ 0 & 5 & 3 & 10 & 7 & 5 \\ 0 & 5 & 3 & 10 & 7 & 5 \end{array} $$

$\pi$ values:
$$ \begin{array}{cccccc} r & s & t & x & y & z \\ \hline \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} & \text{NIL} \\ \text{NIL} & r & r & \text{NIL} & \text{NIL} & \text{NIL} \\ \text{NIL} & r & r & s & \text{NIL} & \text{NIL} \\ \text{NIL} & r & r & t & t & t \\ \text{NIL} & r & r & t & t & t \\ \text{NIL} & r & r & t & t & t \end{array} $$
24.22
Suppose we change line 3 of $\text{DAGSHORTESTPATHS}$ to read
1 3 for the first V  1 vertices, taken in topologically sorted orderShow that the procedure would remain correct.
When we reach vertex $v$, the last vertex in the topological sort, it must have $out\textdegree$ $0$. Otherwise there would be an edge pointing from a later vertex to an earlier vertex in the ordering, a contradiction. Thus, the body of the forloop of line 4 is never entered for this final vertex, so we may as well not consider it.
24.23
The PERT chart formulation given above is somewhat unnatural. In a more natural structure, vertices would represent jobs and edges would represent sequencing constraints; that is, edge $(u, v)$ would indicate that job $u$ must be performed before job $v$. We would then assign weights to vertices, not edges. Modify the $\text{DAGSHORTESTPATHS}$ procedure so that it finds a longest path in a directed acyclic graph with weighted vertices in linear time.
(Removed)
24.24
Give an efficient algorithm to count the total number of paths in a directed acyclic graph. Analyze your algorithm.
We will compute the total number of paths by counting the number of paths whose start point is at each vertex $v$, which will be stored in an attribute $v.paths$. Assume that initial we have $v.paths = 0$ for all $v \in V$. Since all vertices adjacent to $u$ occur later in the topological sort and the final vertex has no neighbors, line 4 is welldefined. Topological sort takes $O(V + E)$ and the nested forloops take $O(V + E)$ so the total runtime is $O(V + E)$.
1 2 3 4 5 6  PATHS(G) topologically sort the vertices of G for each vertex u, taken in topologically sorted order for each v ∈ G.Adj[u] v.paths = u.paths + 1 + v.paths return the sum of all paths attributes 