24.2.md

Exercises 24.2-1

---

Run DAG-SHORTEST-PATHS on the directed graph of Figure 24.5, using vertex r as the source.

Answer

straightforward.

Exercises 24.2-2

---

Suppose we change line 3 of DAG-SHORTEST-PATHS to read 3 for the first |V| - 1 vertices, taken in topologically sorted order Show that the procedure would remain correct.

Answer

因为最后一次对结果没有影响.

Exercises 24.2-3

---

The PERT chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge (u, v) would indicate that job u must be performed before job v. Weights would then be assigned to vertices, not edges. Modify the DAG-SHORTEST-PATHS procedure so that it finds a longest path in a directed acyclic graph with weighted vertices in linear time.

Answer

PERT(G)
	topologically sort the vertices of G
	INITIALIZE(G)
	for each vertex u, taken in topologically sorted order
		do for each vertex v ∈ Adj[u]
			do RELAX(u,v)
			
INITIALIZE(G)
	for each vertex v ∈ V[G]
		do d[v] = w[v]
		   π[v] = NIL
			
RELAX(u, v)
	if(d[v] < d[u] + w[v])
		d[v] = d[u] + w[v]
		π[v] = u

Exercises 24.2-4

---

Give an efficient algorithm to count the total number of paths in a directed acyclic graph. Analyze your algorithm.

Answer

DAG-PATHS(G, s)
	topologically sort the vertices of G
	INITIALIZE(G, s)
	for each vertex u, taken in topologically sorted order
		do for each vertex v ∈ Adj[u]
			do c[v] = c[v] + c[u] 
			
INITIALIZE(G, s)
	for each vertex v ∈ V[G]
		do c[v] = 0
	c[s] = 1

---

Follow @louis1992 on github to help finish this task.

本节部分答案参考自这里