算法设计与分析基础(十四)_权重矩阵有向图求解完全最短路径

算法设计与分析基础(十四)

练习题

习题一

给出选择排序算法的递归描述，并分析算法的计算复杂度。

解：算法思想

1.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2.从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3.重复第二步，直到所有元素均排序完毕。

算法形式化描述：

Algorithm SelectionSort(A[0 ... n-1], n, index)
//输入：序列A[0 ... n-1]，序列规模n，未排序序列的起始位置index
begin
	if index >= n-1 then return
	min := index
for i := index+1 to n do
		if A[i] < A[min] then min := i
	Swap(A[index], A[min])
	SelectionSort(A, n, index+1)
end
1
2
3
4
5
6
7
8
9
10

解：算法思想：

1. 在待排序的n个元素的数组A[1…n]中找出最大元素；

2. 将该最大元素放置在A的尾端；

3. 对当前的A[1…n-1]递归的实施排序；

4. 上述递归的终止条件为：当n=1时，直接返回数组A。

算法的形式化递归描述：

//设max(A)为在A中选出最大元素的过程， 则选择排序算法可进行如下递归描述
//Input：待排序的数组A[1..n]，
//Output：元素具有增序排列数组A[1..n]，
Algorithm SSort (A, n)
begin
	if n=1 then return (A)
else  begin 
          a:=max(A);
Swap (a, A[n]);
		       SSort (A, n-1);
              return (A)
end;
end.
1
2
3
4
5
6
7
8
9
10
11
12
13

习题二

对于下面具有权重矩阵的有向图，求解完全最短路径问题

由题目可知图的权重矩阵为：也就是说：

习题三

如果图的边权重可为负，Prim算法总是能正确求出最小生成树吗？

解:如果图的边权重可为负，Prim算法总是能正确求出最小生成树。

假设图的边的最小权重为W，且为负数，可通过给所有边的权重都增加-W+1的方式，将所有权重为负的边变成权重为正的边，此操作不会改变最小生成树的结构，只是让最小生成树的总权重增加了k(-W+1)，其中，k是最小生成树所含边的数量，最后结果只需要将总权重减去k(-W+1)。

习题四

请证明，如果加权连通图的每一个权重都是唯一的，它的最小生成树也是唯一的。

证明：若最小生成树不唯一，则存在两颗最小生成树A与B，假设他们均有n条边，边e的权值记为w(e)。

分别将A、B的边按权值由小到大排列。

设A的边为a1, a2, a3, …, an，满足w(a1) < w(a2) < … < w(an)

B的边设为b1, b2, …, bn，满足w(b1) < w(b2) < … < w(bn)。

若A ≠ B，则A，B中必存在若干不同的边。设i为第一个不同边出现的位置，即a1 = b1, a2 = b2, …, ai-1 = bi-1，但ai ≠ bi，不妨设w(ai) > w(bi)。现将bi加入到A中，必将产生一条回路。

由于bi为最小生成树B中的边，从而bi与B中的b1, b2, …, bi-1，也就是A中的a1, a2, …, ai-1不构成回路。因此，bi加入到A所构成的回路中必有一条边aj，j ≥ i，使得w(bi) < w(ai) ≤ w(aj)。在A中去掉aj可得一颗生成树A′，显然A′的权值小于A的权值，这与**A为最小生成树矛盾。**由反证法原理得知边权值互不相等时，图的最小生成树是唯一的。

习题五

a. 对下面的数据构造一套哈夫曼编码：

b. 用a中的编码对文本ABACABAD进行编码。

c, 对于100010111001010用a中的编码进行解码。

解：

根据给定的数据构造如下哈夫曼树：

由上述哈夫曼树可得哈夫曼编码：

A: 0 B: 100 C: 111 D: 101 -: 110

b. 根据a中的哈夫曼编码，ABACABAD对应的编码为：0100011101000101

c. 100010111001010用a中的编码进行解码得：BAD-ADA。