【特惠】26考研
红包
【考研】专业课HOT
26考研
【MBA】在职考研
【申硕】同等学力
【报录比】查询
计划
【分数】录取线
计划
【高分】抢跑课
预备
【词汇】5500大纲
免费
【AI】智能择校
免费
【资料】考研大纲
精
扫码加入训练营
牢记核心词
学习得礼盒
【题目】
41.(10分)带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;
③重复步骤②,直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。
【答案要点】
该方法不一定能(或不能)求得最短路径。举例说明如下:
图a
图b
图a中,设初始顶点为1,目标顶点为4,欲求从顶点1到顶点4之间的最短路径。显然, 这两点之间的最短路径长度为2。但利用给定方法求得的路径长度为3,因此这条路径并不是这两点之间的最短路径。
图b中,设初始顶点为1,目标顶点为3,欲求从顶点1到顶点3之间的最短路径。利用给定的方法,无法求出顶点1到顶点3的路径。
本文关键字: 带权图(权值非负,表示边连接的两顶点
添加班主任领资料
添加考研班主任
免费领取考研历年真题等复习干货资料
推荐阅读
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
2024年考研初试考试结束后,相信同学们都比较关心考后的真题以及答案了。新东方在线第一时间为大家整理了本次考试对应的真题以及答案解
资料下载
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
新东方在线考研资料合集
下载方式:微信扫码,获取网盘链接
目录:
1.2013-2023年近10年政数英真题及解析PDF版(新东方)
2.2013-2023年专业课考试历年真题及解析PDF版
3.24考研复习备考资料大合集:大纲+备考资料+词汇书+考前押题+自命题
资料介绍:
1.2013-2023年近10年政数英真题及解析PDF版(新东方)
、
2.2013-2023年专业课考试历年真题及解析PDF版
3.24考研复习备考资料大合集
3.24考研复习备考资料:考研大纲
3.24考研复习备考资料:政数英备考资料+自命题真题
------------------
考研备考过程中,尤其是专业课部分,参考往年的考试真题,对于我们的复习有更好的帮助。北京大学考研真题资料都有哪些?小编为大家进行了汇总。
北京大学考研真题资料-公共课
北京大学考研真题资料-专业课
以上就是关于“北京大学考研真题资料下载(历年汇总)”的整理,更多考研资料下载,请关注微信获取下载地址。
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
扫码添加【考研班主任】
即可领取资料包
阅读排行榜
相关内容