24.2 Single-source shortest paths in directed acyclic graphs
24.2-1
Run $\text{DAG-SHORTEST-PATHS}$ 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.2-2
Suppose we change line 3 of $\text{DAG-SHORTEST-PATHS}$ to read
Show that the procedure would remain correct.
When we reach vertex $v$, the last vertex in the topological sort, it must have $out\text-degree$ $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 for-loop of line 4 is never entered for this final vertex, so we may as well not consider it.
24.2-3
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{DAG-SHORTEST-PATHS}$ procedure so that it finds a longest path in a directed acyclic graph with weighted vertices in linear time.
There are two ways to transform a PERT chart $G = (V, E)$ with weights on the vertices to a PERT chart $G' = (V', E')$ with weights on edges. Both ways satisfy $|V'| \le 2|V|$ and $|E'| \le |V| + |E|$, so we can scan $G'$ using the same algorithm to find the longest path through a directed acyclic graph.
In the first way, we transform each vertex $v \in V$ into two vertices $v'$ and $v''$ in $V'$. All edges in $E$ that enters $V$ will also enter $V'$ in $E'$, and all edges in $E$ that leaves $V$ will leave $V''$ in $E'$. Thus, if $(u, v) \in E$, then $(u'', v') \in E'$. All such edges have weight 0, so we can 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$. Finally, we get $|V'| \le 2|V|$ and $|E'| \le |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$, but try to add one new source vertex $s$ to $V'$, given 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-degree 0 in $G$. Thus, the only vertex with in-degree 0 in $G'$ is the new source $s$. The weight of edge $(u, v) \in E'$ is the weight of vertex $v$ in $G$. We have the weight of each entering edge in $G'$ is the weight of the vertex it enters in $G$.
24.2-4
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 well-defined. Topological sort takes $O(V + E)$ and the nested for-loops take $O(V + E)$ so the total runtime is $O(V + E)$.