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

cpp 3 for the first |V| - 1 vertices, taken in topologically sorted order

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.

(Removed)

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)$.

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