Skip to content

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

1
 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.

Instead of modifying the $\text{DAG-SHORTEST-PATHS}$ procedure, we'll modify the structure of the graph so that we can run $\text{DAG-SHORTEST-PATHS}$ 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 2|V|$ 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'| = 2|V|$, $|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\text-degree$ $0$ in $G$. Thus, the only vertex with $in\text-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$. 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\text-degree$ $0$ in $G$), and again the edge weight of each path in $G'$ equals the vertex weight of the corresponding path 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)$.

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