首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
admin
2015-12-30
54
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;
③重复步骤②,直到u是目标顶点时为止。
请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。
选项
答案
该方法不一定能(或不能)求得最短路径。 举例说明: 图(a)中,设初始顶点为1,目标顶点为4,欲求从顶点1到顶点4之间的最短路径,显然这两点之间的最短路径长度为2。利用给定方法求得的路径长度为3,但这条路径并不是这两点之间的最短路径。 图(1))中,设初始顶点为1,目标顶点为3,欲求从顶点l到顶点3之间的最短路径。利用给定的方法,无法求出顶点1到顶点3的路径。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/BBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列对于两次世界大战之间的国际关系体系的描述,正确的一组是()①原有的四大帝国纷纷解体②中欧和东南欧已经出现了许多民族独立国家③欧洲的两侧出现了崛起的美国和社会主义的苏维埃俄国④远东出现了恶性发展的日本和独立
我国对资本主义工商业采取和平赎买的政策内容和成功意义。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
1945年,联合国成立之时,创始会员国共有()个国家。
根据越南战争的起源和发展,分析“冷战”时期美国对第三世界政策的目标和动机。
中国共产党主张和平解决西安事变的主要目的是()。
下列法律文件中,规定内阁对君主负责的是()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
随机试题
根据高血压分级标准,血压为175/112mmHg,属于
A.红外吸收光谱B.荧光分析法C.紫外-可见吸收光谱D.质谱E.电位法基于分子外层价电子吸收一定能量后,由低能级跃迁到较高能级产生的吸收光谱
A.吸收减少B.分布减慢C.酶促作用D.酶抑作用E.排泄减慢苯巴比妥与华法林合用时,后者的抗凝作用减弱,其原因是苯巴比妥有
以下对期权交易的描述,正确的是()。
乙注册会计师是ABC会计师事务所的项目经理,在工作过程中遇到以下问题,请代其作出正确的判断。在对B公司2009年度财务报表实施审计工作时,项目质量控制复核人员要在业务执行过程中的适当阶段及时实施复核,以使重大事项在出具报告前得到满意解决,项目质量控制复
2000版ISO9000系列标准的主要特点:标准的结构与内容能更好地适用于所有产品类别、不同规模和各种类型的组织的管理和运作。强调质量管理体系的有效性和效率,引导组织关注顾客和其他利益相关者、产品与过程,对标准要求的适用性进行了更加科学与明确的规定,在满
一般资料:求助者,男性,35岁,已婚,某公司部门经理。案例介绍:求助者出生于军人家庭,自幼随祖母在农村生活,上小学时回到父母身边。父母对他事事严格要求,养成了追求完美的性格特征。因带乡下口音,曾被同学笑话。对上学感到恐惧,苋得无助和目卑,但成绩一
阅读下面关于《大规模的海水运动》的教学片段,回答问题。教师:同学们,让我们一起跟随我国著名的航海家郑和扬帆起航,一起下西洋(多媒体播放影片)。同学们,为什么郑和下西洋常常选择在冬季的时候出发,而到了夏季的时候回来呢?学生:受洋流的影响。
某奶茶店每杯奶茶成本3元,售价12元,当天卖不完的奶茶不再出售,在某月第一周的7天里,该店每天会准备400杯奶茶,其中有4天卖光,有3天各剩余40杯,则该奶茶店这周赚了多少钱?
下列对IPv6地址FE80:0:0:0801:FE:0:0:04A1的简化表示中,错误的是()。
最新回复
(
0
)