首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
admin
2013-09-16
55
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点U=V;③重复步骤②,直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。
选项
答案
该方法求得的路径不一定是最短路径。例如,对于下图所示的带权图,如果按照题中的原则,从A到C的最短路径为A→B→C,事实上其最短路径为A→D→C。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/a0xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
保加利亚共产党于1990年4月改名为保社会党,它在政府中沦为少数派的时间是()。
《国策基准》
克里特文明的文字类型是()。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
1979年3月,邓小平在中央理论工作务虚会上首次明确提出必须坚持()。
规定了电流、电动势、电阻等概念的物理学家是()。
在击溃国民党的全面进攻和重点进攻中,人民解放军的主要作战目标是()。
以下()协议完成了从网卡到IP地址的映射。
在一个按字节编址的计算机中,若数据在存储器中以小端方案存放。假定int型变量i的地址为08000000H,i的机器数为01234567H,地址:08000000H单元的内容是()。
某计算机存储器按字节编址,主存地址空间大小为64MB,现用4MBx8位的RAM芯片组成32MB的主存储器,则存储器地址寄存器MAR的位数至少是____。
随机试题
一个测验要能实际测出其所要测量的特性或功能的程度,这是对测量工具要求中的()
生长轨迹现象主要受哪一因素的影响
老年人的动脉管壁硬化,大动脉的弹性阻力作用减弱,因此()
防雷保护装置中,利用建筑物钢筋混凝土立柱中的一对钢筋作()。明装的接闪器和引下线应由()组成。
3.在使用倒扣价格方法即:与该货物进口的同时或者大约同时,将该进口货物、相同或者类似进口货物在第一级销售环节销售给无特殊关系买方最大销售总量的单位价格,但应当扣除下列()。
1960年8月提出对国民经济实行“调整、巩固、充实、提高”方针的是()。
你是新毕业的大学生,被安排到涉密岗位上班。工作第一天网上流传了一份机密资料,与你单位掌握的机密信息类似。有人怀疑是你和你的领导泄露的。你该怎么办?
18世纪的产业革命开启了人类社会工业化历程。许多国家通过工业化,极大地促进了经济增长,同时也产生了环境污染等生态问题。有学者据此把工业化比喻为一把双刃剑。从唯物辩证法看,工业化与环境污染之间的联系
Humansareuniqueintheextenttowhichtheycanreflectonthemselvesandothers.Humansareableto【C1】______.tothinkinab
Ican’tbelievethekindofrubbishthatsomepeoplecallart.Yesterday,mygirlfrienddraggedmetoamodernart【C6】______to
最新回复
(
0
)