首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; ②选择离u最近且尚未在最
admin
2015-12-30
73
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
①设最短路径初始时仅包含初始顶点,令当前顶点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
学硕统考专业
相关试题推荐
关于大陆人民大规模达到台湾的第一次明确的记录出现在()。
建立中国道教史上第一个成熟的神仙系统的是()。
第三次科技革命促进了社会经济结构和社会生活结构的变化,其在社会经济结构方面的变化主要是()
30年代,美国政府对一系列国际问题执行中立政策,最主要的原因是()。
国家实施的“211工程”计划主要是针对()
简述尼克松主义的主要内容。(东北师范大学1999年世界现代史真题)
以下选项中中原王朝对西藏管辖设置机构对应有误的一项是()。
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
假定某采用页式虚拟存储管理的计算机系统中,主存储器容量为1GB,被分为262144块物理块,物理块号为0,1,2,……,262143。某进程的地址空间占4页,逻辑页号为0,1,2,3,被分配到主存储器的第20,45,101,58号物理块中。回答:
随机试题
根据我国现行有关资本金制度的规定,除国家对采用高新技术成果有特别规定外,以工业产权、非专利技术作价出资的比例不得超过投资项目资本金总额的()。
左边是给定纸盒的外表面,下列哪一项能由它折叠而成?
虽然金融危机最严重时期已经过去,但世界经济______的基础尚不牢固,势头仍然脆弱。人民币大幅______可能打击中国出口,进而产生连锁反应,危及中国和世界经济复苏。填入横线部分最恰当的一项是()。
某司机开车从A城到B城,若按原定速度前进,则可准时到达,当路程走了一半时,司机发现实际平均速度只达到原定速度的。如果司机想准时到达B城,那么在后一半的行程中,实际速度与原定速度的比应是多少?
关于物价下跌,请回答:(2008年南京大学919经济学原理)物价下跌导致总需求增加的理论依据是什么?
甲、乙二人共同盗窃一辆价值20万元的汽车销赃得款6万元,甲分得5万元,乙分得1万元。关于此案,下列说法中正确的是()。(2009年单选15)
(2015年)为了实现利润的最大化,厂商需要对某商品确定其定价模型,设Q为该商品的需求量,P为价格,MC为边际成本,η为需求弹性(η>0)。(I)证明定价模型为(Ⅱ)若该商品的成本函数为C(Q)=1600+Q2,需求函数为Q=40一P,试由(I)中的定
在TCP/IP参考模型中负责将源主机的报文分组发送到目的主机的是()。
当前工资表中有100条记录,当前记录号为10,用MAX命令计算工资最大值时,若缺省[范围]短语条件,则系统将( )。
TheGoulburnValleywasoneofAustralia’sprosperousdairyingregions.Butoverthelastfiveyears,it’sestimatedthathalft
最新回复
(
0
)