Skip to content

Latest commit

 

History

History
113 lines (82 loc) · 4.03 KB

25.1.md

File metadata and controls

113 lines (82 loc) · 4.03 KB
Raw

Exercises 25.1-1

Run SLOW-ALL-PAIRS-SHORTEST-PATHS on the weighted, directed graph of Figure 25.2, showing the matrices that result for each iteration of the loop. Then do the same for FASTER-ALL-PAIRS-SHORTEST-PATHS.

Answer

straightforward.

Exercises 25.1-2

Why do we require that wii = 0 for all 1≤i≤n?

Answer

为了保证递归定义式25.2的正确性.

Exercises 25.1-3

What does the matrix

	 	0  ∞  ∞  ...  ∞
	 	∞  0  ∞  ...  ∞
L(0) =  ∞  ∞  0  ...  ∞
	 	.  .  .  .    .
	 	.  .  .   .   .
	 	.  .  .    .  .
	 	∞  ∞  ∞  ...  ∞

used in the shortest-paths algorithms correspond to in regular matrix multiplication?

Answer

单位矩阵

Exercises 25.1-4

Show that matrix multiplication defined by EXTEND-SHORTEST-PATHS is associative.

Answer

A brute force verification will work. Here is the proof. Proof of the exercise 25.1-4.pdf

Exercises 25.1-5

Show how to express the single-source shortest-paths problem as a product of matrices and a vector. Describe how evaluating this product corresponds to a Bellman-Ford-like algorithm (see Section 24.1).

Answer

向量就是所有节点对矩阵L的一行（行号为单源起点），W依然是权重矩阵。矩阵乘法中，向量与W的第i列相乘对应算法第3，4行中对 (?, i) 这类的边进行松弛。

Exercises 25.1-6

Suppose we also wish to compute the vertices on shortest paths in the algorithms of this section. Show how to compute the predecessor matrix Π from the completed matrix L of shortest-path weights in O(n3) time.

Answer

FING-Π(L, w)
	for i <- 1 to n
		for j <- 1 to n
			for k <- 1 to n
				do if L(i,k)+w(k,j) = L(i,j)
					do Π(i,j) = k

Exercises 25.1-7

The vertices on shortest paths can also be computed at the same time as the shortest-path weights. Let us define  to be the predecessor of vertex j on any minimum-weight path from i to j that contains at most m edges. Modify EXTEND-SHORTEST-PATHS and SLOW- ALL-PAIRS-SHORTEST-PATHS to compute the matrices Π(1), Π(2),..., Π(n-1) as the matrices L(1), L(2),..., L(n-1) are computed.

Answer

这个改动很简单.

就是更新l(ij)的时候同时更新Π,类似于relax松弛操作.

所以伪代码暂时就不写啦.

Exercises 25.1-8

The FASTER-ALL-PAIRS-SHORTEST-PATHS procedure, as written, requires us to store ⌈lg(n - 1)⌉ matrices, each with n2 elements, for a total space requirement of Θ(n2 lg n). Modify the procedure to require only Θ(n2) space by using only two n × n matrices.

Answer

这道题跟pow(2, n)一样.

pow(2,n)
	res <- 1
	temp <- 2
	while(n > 0)
		if n%2 = 1
			res *= temp
			n--
		else
			temp *= 2
			n /= 2
	return res

这里的res和temp就是对应的两个n*n矩阵.

Exercises 25.1-9

Modify FASTER-ALL-PAIRS-SHORTEST-PATHS so that it can detect the presence of a negative-weight cycle.

Answer

只需要查看最后的L(n-1)矩阵.如果对角线上的元素有负值,就说明有负权回路.

如果是有三个节点，ABC，由A到B为-1，B到C为-1，C到A为-1，最后的L(n-1)矩阵的对角线不会是负值。因为算法考虑的是最多n-1条边的情况，而负环的最大可能性是n条边，所以如果不多循环一次的话是无法检测出的；另外也可以多循环一次，查看两个矩阵是否有变化，这样是O(n^2)，而仅仅是多循环一次检查对角线的话只用O(n)

Exercises 25.1-10

Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.

Answer

跟练习25.1-9差不多,我们可以根据L矩阵的对角线判断存不存在负权回路.如果L(m)是第一次对角线出现负值，那么m就是我们的值.

Follow @louis1992 on github to help finish this task.