Skip to content

Latest commit

 

History

History
90 lines (63 loc) · 3.22 KB

25.2.md

File metadata and controls

90 lines (63 loc) · 3.22 KB
Raw

Exercises 25.2-1

Run the Floyd-Warshall algorithm on the weighted, directed graph of Figure 25.2. Show the matrix D(k) that results for each iteration of the outer loop.

Answer

straightforward.

Exercises 25.2-2

Show how to compute the transitive closure using the technique of Section 25.1.

Answer

将EXTEND-SHORTEST-PATHS中第7行的min换成OR,+换成AND

Exercises 25.2-3

Modify the FLOYD-WARSHALL procedure to include computation of the Π(k) matrices according to equations (25.6) and (25.7). Prove rigorously that for all i ∈ V , the predecessor subgraph Gπ,i is a shortest-paths tree with root i.

Answer

UNSOLVED

Exercises 25.2-4

As it appears above, the Floyd-Warshall algorithm requires Θ(n3) space, since we compute for i, j, k = 1, 2,...,n. Show that the following procedure, which simply drops all the superscripts, is correct, and thus only Θ(n2) space is required.

Answer

当然是正确的,因为这个动态规划只需要保存上一个状态.也就是要计算当前这个状态只需要借助上一个状态.

Exercises 25.2-5

Suppose that we modify the way in which equality is handled in equation (25.7):

Is this alternative definition of the predecessor matrix Π correct?

Answer

感觉正确呀.

Exercises 25.2-6

How can the output of the Floyd-Warshall algorithm be used to detect the presence of a negative-weight cycle?

Answer

只需要在正常的Floyd-Warshall算法完成后再多跑一个循环,如果有一个值还能更新则说明有负权回路.

Exercises 25.2-7

Another way to reconstruct shortest paths in the Floyd-Warshall algorithm uses values Φij(k) for i, j, k = 1, 2,..., n, where Φij(k) is the highest-numbered intermediate vertex of a shortest path from i to j in which all intermediate vertices are in the set {1, 2,..., k}. Give a recursive formulation for  Φij(k) , modify the FLOYD-WARSHALL procedure to compute the Φij(k) values, and rewrite the PRINT-ALL-PAIRS-SHORTEST-PATH procedure to take the matrix Φ = (Φij(n)) as an input. How is the matrix Θ like the s table in the matrix-chain multiplication problem of Section 15.2?

Answer

			Φij(k－1)   如果dij(k-1) <= dik(k-1) + dkj(k-1) 
Φij(k) ＝ 
			k			otherwise
			

PRINT-ALL-PAIRS-SHORTEST-PATH(Φ,i,j)
	if i == j
		then print i
	else if Φ(i,j) = -1
		then print "no path from 'i' to 'j' exists"
	else
		PRINT-ALL-PAIRS-SHORTEST-PATH(Φ,i,Φ(i, j))
		print Φ(i, j)
		PRINT-ALL-PAIRS-SHORTEST-PATH(Φ,Φ(i, j),j)

Exercises 25.2-8

Give an O(V E)-time algorithm for computing the transitive closure of a directed graph G = (V, E).

Answer

对每个节点都跑一次DFS. 一共V个点,E条边，所以是O(VE)的时间.

Exercises 25.2-9

Suppose that the transitive closure of a directed acyclic graph can be computed in f(|V|,|E|) time, where f is a monotonically increasing function of |V| and |E|. Show that the time to compute the transitive closure G* = (V, E*) of a general directed graph G = (V, E) is f(|V|,|E|) + O(V + E*).

Answer

UNSOLVED

Follow @louis1992 on github to help finish this task.