首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
admin
2015-12-30
74
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点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
学硕统考专业
相关试题推荐
1978年直接领导和发动真理标准问题讨论的中央领导人是()。
对《魏玛宪法》的内容和影响叙述不正确的是()。
19世纪末中国维新变法思想的基本内容是什么?与18世纪法国启蒙思想相比,两者在促进社会变革的作用上有何不同?为什么?
世界天文史上最早实地测量子午线的记录是由谁进行的?()
下列选项中不属于《国际联盟盟约》内容的是()。
下列选项中,对魏晋玄学描述不正确的是()
对苏联高度集中的体制的客观评价是()。①基本上适应苏联当时的生产力发展水平②这种体制有严重缺点和弊端③后来这种体制阻碍了苏联国民经济的发展④这种体制在历史上起过积极的作崩
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
激光打印机的打印原理是()。
随机试题
关于骨盆出口狭窄是指下列哪项
申请执业注册时,以下可以注册的情形是
投标人应填报工程量清单计价格式中列明的所有需要填报的单价和合价,如未填报,则()。
单位因特殊情况需坐支现金的,在支付时应报经开户银行审查批准。()
下列事项中,不属于企业收入的是()。
根据受益对象进行分配,应付职工薪酬计提时可以记入的会计科目有()。
第三期牙本质(tertiarydentin)
法的本质主要表现在()。
Treesareusefultomaninthreeveryimportantways:theysupplyhimwithwoodandotherproducts;theygivehimshade;andt
Gesturesarethesilentlanguageofeveryculture.Itisimportanttoknowthebodylanguageofeverycountry,orwemaybe【B1】_
最新回复
(
0
)