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
C++
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.

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

C++
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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用