算法设计与分析答案参考

1、用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i, j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。 解

在每条边的矩阵行中无最短路径

2、设有n=2k个运动员足以下要求的比赛日

①每个选手必须与其他n-1名选手比赛各一次； ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。 （1）如果n=2k，循环赛最少需要进行几天； （2）当n=23=8时，请画出循环赛日程表。

1 2 3 4 5 6 7 解：（1）至少要进行n天

（2）如右图：

8 2 1 4 3 6 5 8 要进行循环赛，现设计一个满程表：

依次加入顶点1,2,3，判断有

7 3、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。

步骤 V1 V2 E1 1. {a}

{b} {}

E2

{ab} {bd}

2. {a,b} {d} {ab} 3. {a,b,d} {c,f} {ab,bd}

{dc,df}

{df}

{fe}

4. {a,b,d,c} {f} {ab,bd}

5. {a,b,c,d,f} {e} {ab,bd,dc,df}

6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh} 8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 结果：从a到h的最短路径为a?b?d?f?e?g?h，权值为

18。

求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。 补充例题：求A到各个顶点的最短路径： 解：

4、用动态规划策略求解最长公共子序列问题： （1）给出计算最优值的递归方程。

（2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最

长公共子序列，要求给出过程。 解：(1)

?c[i,j]??0当i?0或j?0时?c[i?1,j?1]?1当i,j?0且xi?yi时??max(c[i,j?1],c[i?1,j])当i,j?0且xi?yi时 Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2 2 Ｄ 0 0 1 2 2

Ａ 0 1 1 2 2 最长公共子序列：｛ＢＣ｝

2）

（5、对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算

1 2118 192 79 611 265 17

3 6 15 4

法的基本思想，并简要分析算法的时间复杂度。 答：

TE={(3,4), (2,3),(1,5),（4,6）（4,5）}

贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。

基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。 时间复杂度为：O(eloge)

6、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2) 解：第一个分割元素为65