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.
Instead of modifying the $\text{DAGSHORTESTPATHS}$ procedure, we'll modify the structure of the graph so that we can run $\text{DAGSHORTESTPATHS}$ on it. In fact, we'll give two ways to transform a PERT chart $G = (V, E)$ with weights on vertices to a PERT chart $G' = (V', E')$ with weights on edges. In each way, we'll have that $V' \le 2V$ and $E' \le V + E$. We can then run on $G'$ the same algorithm to find a longest path through a dag as is given in Section 24.2 of the text.
In the first way, we transform each vertex $v \in V$ into two vertices $v'$ and $v''$ in $V'$. All edges in $E$ that enter $v$ will enter $v'$ in $E'$, and all edges in $E$ that leave $v$ will leave $v''$ in $E'$. In other words, if $(u, v) \in E$, then $(u'', v') \in E'$. All such edges have weight $0$. We also put edges $(v', v'')$ into $E'$ for all vertices $v \in V$, and these edges are given the weight of the corresponding vertex $v$ in $G$. Thus, $V' = 2V$, $E' = V + E$, and the edge weight of each path in $G'$ equals the vertex weight of the corresponding path in $G$.
In the second way, we leave vertices in $V$ alone, but we add one new source vertex $s$ to $V'$, so that $V' = V \cup \{s\}$. All edges of $E$ are in $E'$, and $E'$ also includes an edge $(s, v)$ for every vertex $v \in V$ that has $in\textdegree$ $0$ in $G$. Thus, the only vertex with $in\textdegree$ $0$ in $G'$ is the new source $s$. The weight of edge $(u, v) \in E'$ is the weight of vertex $v$ in $G$. In other words, the weight of each entering edge in $G'$ is the weight of the vertex it enters in $G$. In effect, we have "pushed back" the weight of each vertex onto the edges that enter it. Here, $V' = V + 1$, $E' \le V + E$ (since no more than $V$ vertices have $in\textdegree$ $0$ in $G$), and again the edge weight of each path in $G'$ equals the vertex weight of the corresponding path in $G$.
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  PATHS(G) topologically sort the vertices of G for each vertex u, taken in reverse topologically sorted order for each v ∈ G.Adj[u] u.paths = u.paths + 1 + v.paths 