带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路

admin2013-09-16 33

问题带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点U=V；③重复步骤②，直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之；否则，请举例说明。

选项

答案该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为A→D→C。 [*]

解析

转载请注明原文地址:https://kaotiyun.com/show/a0xi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

我国第一部系统的史学理论著作是()。

关于荷马时代的叙述，不正确的是()。

科举是一种读书、应考、任官三位一体的选官方法，其中的进士科始创于()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

“二战期间，美国研制了原子弹并用于实践；1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道；德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

有关并发进程相互之间的关系，正确的说法是

1949年中华人民共和国的建立，标志着中国从半殖民地半封建社会进入（）

真武汤与实脾散的共同药物是

抑制性突触后电位产生的离子机制是

2017年5月10B，甲公司以310万元(含已宣告但尚未领取的现金股利10万元)购入乙公司股票100万股作为交易性金融资产，另支付手续费3万元。(1)5月30日，甲公司收到现金股利10万元。2017年6月30日，该股票每股市价为4元。(2)8月10日

根据《国务院关于全面建立临时救助制度的通知》，临时救助工作要坚持()有机结合。

下列选项中划线字的读音全都正确的一项是()。

我国第一本教育心理学著作是1908年房东岳编著的《教育实用心理学》。()

蔬菜是人类不可缺少的食物，它富含人体需要的维生素、矿物质及消化系统所必需的粗纤维等。下列说法中错误的是()。，