算法设计与分析答案参考
9页1、1、用Floyd算法求下图每一对顶点之间的最 短路径长度,计算矩阵 D, D, D和D,其中 Di, j表示从顶点i到顶点j的不经过编号oi23k 大于k的顶点的最短路径长度。解0 20 20 2072D 305D 305D 305D 306102310501050850850在每条边的矩阵行中依次加入顶点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 78 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 378 5 6 3 4 1 28 7 6 5 4 3 2 13、对于下图使用Dijkstra算法求由顶点a至9 顶点h的最短路径。 be2g212ad323
2、182cf2h解: 用V表示已经找到最短路径的顶点,V表示与V中某E为与V中的顶点相邻接且距离最1121短的路径。步骤12121. abab 2. a,bd个顶点相邻接且不在121V中的顶点;E表示加入到 最短路径中的边,abbd 3.dc,df 4. a,b,d,ca,b,c,d,fea,b,dfc,f ab,bd ab,bd df 5.ab,bd,dc,df fe 6. a,b,c,d,e,fg 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,hab,bd,de,df,fe,eg,gh 结果:从a到h的最短路径 为,权值为18。求所有顶点对之间的最短路径可以使用Dijkstra算法,使其起始节点从a循环到h,每次求起始节点到其他节点的最 短路径,最终可以求得所有顶点对之间的最短路径。 补充例题:求A到各个顶点的最短路径: 解:4用动态规划策略求解最长公共子序列问题:(1)给出计算最优值的递归方程。(2)给定两个序列X=B,C,D,AY=A,B,C,B,请采用动态规划策略求出其最长公共
3、子序列,要求给出过程。解:(1当i0或j0时当i,j0且xy时IIk1max(cijlLcilj)当 i,jo 且 xy 时Y A B CBX0000B 0 0 1 1 1C00122 D 0 0 1 2 2 A 0 1 12 2 最长公共子序列:BC5、对下图所示的连通网络G,用克鲁斯卡尔(Kruskal) 算法求G的最小生成树T,请写 出在算法执行过程中,依次加 入T的边集TE中18217 2119 11 9 6 3 2615 6 4 5 17 的边。说明 该算法的贪心策略和算法的基 本思想,并简要分析算法的时 间 复 杂 度 。 答 : TE=(3,4), (2,3),(1,5),(4,6)(4,5)贪心策略是每次都在连接两个不同连通分量的边中选权值最小 的边。 基本思想:首先将图中 所有顶点都放到生成树中,然 后每次都在连接两个不同连通 分量的边中选权值最小的边, 将其放入生成树中,直到生成 树中有 n-1 条边。 时间复杂度 为: O(eloge) 6、快速排序算法对下列实例排序,算法执行 过程中,写出数组 A 第一次被分割的过程。 A=(65,70,75,80,85,55,
《算法设计与分析答案参考》由会员pu****.1分享,可在线阅读,更多相关《算法设计与分析答案参考》请在金锄头文库上搜索。
上半年保险公司利润翻倍
人教版选修五第一章第二节有机化合物的结构特点A卷
沪教版一年级数学上学期看图列式计算专项同步
推荐三年级语文说课稿范文集合五篇
广场盛大开业开业庆典活动策划方案供参考
法治主题班会
某集团招标文件的编制
物业公司职责的规定范文(3篇).doc
冬季亲子运动会主持词
软件采购合同
公司注册房屋租赁合同律师版(九篇).doc
【施工管理】装修拆除工程施工方案(2)
安徽省地方标准白芍栽培技术规程
焊接工艺技术标准
公司办公房屋租赁合同书
工作面对接安全技术制定
小学四年级英语试题
2023生育保险委托书集合15篇
有关物业年度工作总结(2篇).doc
xx区超高温陶瓷产业高质量发展规划(审阅稿)
2023-01-22 7页
2023-03-11 12页
2023-10-19 8页
2023-07-17 7页
2023-04-20 2页
2023-05-23 8页
2023-10-18 2页
2023-06-14 3页
2024-01-24 23页
2023-09-05 20页