内容发布更新时间 : 2024/11/20 12:28:56星期一 下面是文章的全部内容请认真阅读。

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

在每条边的矩阵行中依次

加入顶点1,2,3，判断有无最短路径 k2、设有n=2

个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表： ①每个选手必须与其他n-1名选手比赛各一次； ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。 k（1）如果n=2，循环赛最少需要进行几天； 1 2 3 4 5 6 7 8 3（2）当n=2=8时，请画出循环赛日程表。 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 解：（1）至少要进行n天 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 （2）如右图： 6 5 8 7 2 1 4 3 7

8 5 6 3 4 1 2 8 7 6 5 4 3 2 1

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

用V表示已经找到最短路径的顶点，V表示与V中某

个顶点相邻接且不在121V中的顶点；E表示加入到最短路径中的边，E为与V中的顶点相邻接且距离最1121短的路径。 步骤 V V E E 12121. {a} {b} {} {ab} 2. {a,b} {d} {ab} {bd} 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 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的最短路径为，权值为18。

求所有顶点

对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。 补充例题：求A到各个顶点的最短路径： 解： 4、用动态规划策略求解最长公共子序列问

题： （1）给出计算最优值的递归方程。 （2）给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。 解：(1当i0或j0时当i,j0且xy时

当i,j0且xy时

（2）

Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0

0 0 Ｂ 0 0 1 1 1 Ｃ 0 0 1 2

2 Ｄ 0 0 1 2 2 Ａ 0 1 1

2 2 最长公共子序列：｛ＢＣ｝ 5、对下图所示的连通网络G，用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中，依次加入T的边集TE中 18 2 1 7 21 19 11 9 6 3 26

15 6 4 5 17 的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。 答： TE={(3,4), (2,3),(1,5),（4,6）（4,5）} 贪心策略是每次都在连接两个不