首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条,在找到一条最短路径的同时,还需要输出不同最短路径的条数。现有一种解决该问题的方法: (1)初始化结点集合S为仅包含源结点s
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条,在找到一条最短路径的同时,还需要输出不同最短路径的条数。现有一种解决该问题的方法: (1)初始化结点集合S为仅包含源结点s
admin
2014-12-08
76
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条,在找到一条最短路径的同时,还需要输出不同最短路径的条数。现有一种解决该问题的方法:
(1)初始化结点集合S为仅包含源结点s;用一个整型数组Counter[v]来记录从结点s到结点v的最短路径的条数;各结点Counter的初始值为0。
(2)从未加入S的结点中选择当前距离最小的结点v(“当前距离”是指从s到v且仅经过S中结点的最短距离),将其加入S。
(3)对每个与v相邻的结点w,若w不在S内,检查: ①若v的加入使得w的当前距离变小,则更新w的当前距离为(v,w)的边长与v的当前距离之和,并日.令Counter[w]=1。 ②若v的加入是s到w的长度相同的另一条最短路径,则Counter[w]++;
(4)重复步骤(2)和(3),直到所有结点都被收录到集合S中。 若该方法可行,请证明之;否则,请举例说明。
选项
答案
首先,该算法是错误的。图8一10给出了反例:设图中各边长为1,则从s到w有3条长度棚同的路径,而使用此算法得到的结果为2。 [*] 问题出现在以下3个地办: (1)当v的加入产生新的最短路径时,从s到v再到w的最短路径条数等于v的最短路径条数,而不是仅等于1。所以步骤(3)中①的Counter[w]=1 应改为等于Counter[w]=Counter[v]。 (2)若v的加入是s到w的长度相同的另一条最短路径,则w的最短路径条数并不是仅增加了1,而是v带过来的所有最短路径。所以(3)中②的Counter[w]++改为(Counter[w]+=Couter[v]。 (3)根据前两步的修改,Counter[s]的初始值必须为1,而不是0,否则后面所有结点的Counter都会一直是0。 总结:此题属于对经典Dijkstra算法的推广应用,类似题目还有累积所有长度相同的最短路径上的结点个数等,其实现原理相同。另一类相似的推广应用是找到包含边数最少的那条最短路径,这时题干中算法的第(3)步应该改为以下步骤。 对每个与v相邻的结点w,若w不在S内,检查: ①若v的加入使得w的当前距离变小,则更新w的当前距离为(v,w)的边长与v的当前距离之和,更新Counter[w]=Counter[v]+1,并将v记录在w的路径上。 ②若v的加入是s到w的长度相同并且边数更少(Counter[w]>Counter[v]+1)的另一条最短路径,则Counter[w]=Counter[v]+1,并将v记录在w的路径上。 这里的整型数组Counter[v]记录从s结点到v结点的最短路径包含的边数,各结点Counter的初始值均为0。此问题很容易出错的地方是当发现另一条长度相同但包含边数更少的最短路径时,只更新了Counter,却忘记了更新w的路径。 类似的题目还有求包含最多边的最短路径,或者给每个结点赋予价值,求价值最高的最短路径等,其实现原理相同。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/xZxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
共产国际第七次代表大会讨论的主题是()。
张仲景的代表性著作是()。
系统总结了6世纪以前黄河中下游地区农牧业生产经验的著作是()。
汉灵帝中平元年(184),()在7州28郡同时俱起,这是中国历史上第一次组织、准备比较严密的农民起义。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发
随机试题
对于数字乳腺摄影来说,需要对极小物体进行探测和分类,特别是微钙化灶可以小到100~200μm,任何平板探测器都必须能够对这些感兴趣的极小微钙化灶进行成像,所以平板探测器的像素尺寸范围应在
患者女,23岁。持续发热伴畏寒、周身肌肉酸痛7天,于7月15日入院,疼痛以腓肠肌尤为显著,全身乏力、食欲减退。体查:巩膜黄染,胸前区可见出血点,肝肋下1cm,脾未扪及。实验室检查:WBC10×109/L,N0.75,L0.25,尿胆红素(+),尿胆原(十)
会计法律制度是促进会计职业道德规范形成和遵守的制度保障。()
对超额运营成本形成的功能性贬值的测算,通常可以采用的步骤是()。
Cp值越大,说明()。
甲公司拥有一件申请日为2007年3月21日、公布日为2008年9月26日的发明专利申请。下列专利文献均记载了与该申请中所请求保护的技术方案相同的技术内容,哪些构成了该申请的抵触申请?
故宫太和殿的屋顶形式是()。
明朝实行“重其所重”的原则,加重了对伦理教化方面犯罪的处罚。 ( )
简述陶行知“生活教育”。
MIPS是用来衡量计算机系统()性能指标的。
最新回复
(
0
)