首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条,在找到一条最短路径的同时,还需要输出不同最短路径的条数。现有一种解决该问题的方法: (1)初始化结点集合S为仅包含源结点s
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条,在找到一条最短路径的同时,还需要输出不同最短路径的条数。现有一种解决该问题的方法: (1)初始化结点集合S为仅包含源结点s
admin
2014-12-08
77
问题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条,在找到一条最短路径的同时,还需要输出不同最短路径的条数。现有一种解决该问题的方法:
(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
学硕统考专业
相关试题推荐
联邦德国的“新东方政策”的代表人物是()。
近代西方自由主义流派众多,其中功利主义学说代表人物是()。
对巴黎公社的评述,正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器,建立新的国家机器③其实践和经验,丰富了马克思主义理论④由于无产阶级的不成熟,其失败是不可避免的
印度孔雀帝国时代,就土地占有情况而言,占全国土地的绝大部分的是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
设某多道程序系统中有用户使用内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执行结
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
随机试题
下列以纳米作为测量大小的微生物是
毛细胞白血病属于特殊类型的
经返修或加固处理的分项工程、分部工程,虽然改变外形尺寸但仍能满足结构安全和()要求,可按技术处理方案文件和协商文件进行验收。
存货周转率越高,表示存货管理的实绩越好。()
民主政体的法律一般保护最大多数人的利益,因为他们源于大多数的公民,这些公民易于犯错,但他们不会站在自己利益的反面。相反,寡头政治的法律有助于将财富和权力集中在少数人手中,因为从本质上看,寡头政治是由少数人建构起来的。因此可以断定,一般情况下,民主政体的立法
如果概念B所表达的对象均在概念A所表达的范围之内,概念A所表达的对象有些在概念B所表达的范围之内,有些在概念B所表达的范围之外,则概念A与概念B之间存在真包含关系。根据上述定义,下列哪项中划横线的两个概念是真包含关系?()
创造一个故事,将所要记忆的信息编在一起的学习策略属于()。
“公民在法律面前一律平等”属于()。
LastyearatthistimeJessicaAndersonwasworkinginChicago,oneofthecoldestcitiesintheUnitedStates.Nowsheisworking
______(让世界发展如此之快的)isthemodernscienceandtechnology.
最新回复
(
0
)