首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
admin
2015-12-30
56
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点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
学硕统考专业
相关试题推荐
(北魏孝文帝)“初谋南迁,恐众心恋旧,乃示为大举,因以胁定群情,外谋南伐,其实迁也。1日人怀土,多不所愿,内惮南征,无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。
下列不是春秋时代齐国管仲改革的内容的是()
刘向子刘歆继承父业,完成了这一工作,并且写出了()一书,是我国第一部目录书。
世界天文史上最早实地测量子午线的记录是由谁进行的?()
以下选项不属于希腊城邦的形成方式和途径的是()。
布雷顿森林体系
下列法律文件中,规定内阁对君主负责的是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
随机试题
急性肾衰竭血液透析指征为
中年男性患者,发现视力下降2天,右眼视力降至0.5,左眼0.6,眼底检查发现双眼视盘边界稍模糊,视盘充血。黄斑部可疑水肿。证实这一诊断的重要检查应当包括
下列不属于药物衣的是
在进行桥梁承载能力检算时,承载能力检算系数Z1作为结构抗力效应的修正系数,其值不大于1。()
下列关于商用房贷款的签约流程表述错误的是()。
下列事项中,应确认预计负债的有()。
下列权力不属于公安机关的侦查权的是()
A、76B、123C、171D、514B前两个圆圈中数字的规律:11×2+25+7=54,36×2+29+5=106,则问号处数字应为7×9+13+47=123,故选B。
AnOhioStateUniversitystudyhaslinkedbehaviorinyoungchildren【1】thetypeofjobtheirmotherhas.Motherswithcomplexoc
A、Shepainteditbyherself.B、Shehiredherbrothertopaintit.C、Itneedstobepainted.D、Itisn’tbeautifullypainted.B语义理
最新回复
(
0
)