首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
admin
2013-09-16
78
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点U=V;③重复步骤②,直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。
选项
答案
该方法求得的路径不一定是最短路径。例如,对于下图所示的带权图,如果按照题中的原则,从A到C的最短路径为A→B→C,事实上其最短路径为A→D→C。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/a0xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中华人民共和国恢复了在联合国合法席位的时间是()。
分析百家争鸣的社会背景及主要原因。
试分析第二次世界大战的历史地位。
第二国际与第一国际特点的比较。
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
材料一:1913年,印度在政府注册的工厂有2744家,1922年时増加到4744家,民族资本获得了丰厚的利润,一战时期因而被印度企业家们称为创业的“黄金时代”。在两次世界大战期间,印度的制糖业和水泥业得到较快的发展,水泥和糖不再依靠进口。第二次世界大战时
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
高度为7的AVL树最少有()个结点。
随机试题
下列关于RAID的描述中,正确的是()。
施工单位应当严格按照专项方案组织施工,不得擅自修改专项方案。因规划调整、设计变更结构等原因确需调整的,修改后的专项方案应当()。
春雨公司2010年有关损益类账户本年累计发生额如下:(单位:元)假设春雨公司利润总额与应纳税所得额一致,所得税税率为25%。 要求:根据上述材料,回答问题:根据上述资料,计算春雨公司2010年度的营业利润为()元。
根据购买力平价理论,决定汇率长期趋势的主导因素是()。
以下关于基金托管费率计提标准的说法错误的是()。
甲公司20×7年3月1日从资本市场上购入某公司1%的股份,并划分为可供出售的金融资产,其购买价格为350万元,其中,已宣告尚未发放的现金股利为5万元。为此项交易,甲公司另支付了交易费用为2万元。3月31日,该股票的公允价值为365万元。甲公司在编制20×7
新型农村合作医疗统筹中通过设立统筹基金分别对住院和门诊费用进行补偿的是()。
在整个结构方法的出发点和实施步骤中,十分强调用户的()。
下列可以建立索引的数据类型是
Whatistheplanmainlyabout?
最新回复
(
0
)