首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
admin
2021-01-13
111
问题
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
选项
A、分治
B、动态规划
C、贪心
D、回溯
答案
C
解析
本题考查算法的设计策略。单源点最短路径问题是指给定图G和源点v
0
，求从v
0
到图G中其余各项点的最短路径。迪杰斯特拉(Dijkstra)算法是一个求解单源点最短路径的经典算法，其思想是：把图中所有的顶点分成两个集合S和T，S集合开始时只包含顶点v
0
，T集合开始时包含图中除了顶点v
0
之外的所有顶点。凡是以v
0
为源点，已经确定了最短路径的终点并入S集合中，顶点集合T则是尚未确定最短路径的顶点集合。按各顶点与v
0
间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中，使得从v
0
到S集合中各顶点的路径长度始终不大于从v
0
到T集合中各顶点的路径长度。该算法是以一种贪心的方式将T集合中的顶点加入到S集合中的，而且该贪心方法可以求得问题的最优解。
转载请注明原文地址:https://www.kaotiyun.com/show/8tCZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和图，根据要求回答问题1～问题3。【说明】某航空公司会员积分系统(CFrequentFlyer)的主要功能描述如下：乘客只要办理该航空公司的会员卡，即可成为普卡会员(CBasic)。随着飞行里程数的积累，可以从普卡会员升级到银卡会员(CSi
阅读以下说明和图，根据要求回答问题1～问题3。【说明】某航空公司会员积分系统(CFrequentFlyer)的主要功能描述如下：乘客只要办理该航空公司的会员卡，即可成为普卡会员(CBasic)。随着飞行里程数的积累，可以从普卡会员升级到银卡会员(CSi
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某医院欲开发病人监控系统。该系统通过各种设备监控病人的生命体征，并在生命体征异常时向医生和护理人员报警。该系统的主要功能如下：(1)本地监控：定期获取病人的生命特征，如体温、血
阅读下列说明和图，回答问题l至问题4，将解答填入答题纸的对应栏内。【说明】某公司欲开发招聘系统以提高招聘效率，其主要功能如下：(1)接受申请验证应聘者所提供的自身信息是否完整，是否说明了应聘职位，受理验证合格的申请，给应聘者发送致谢信息。(2)评
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m
阅读下列说明和C语言代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。
某公司的主要业务是出租图书和唱碟。由于业务需求，该公司委托希赛公司开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。希赛公司决定采用面向对象的分析和设计方法开发此系统。图14-3所示为某类图书或唱碟被借阅时应记录的信息，
阅读下列说明和图，回答问题l～问题3，将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSegment)构成，每个路段
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】0-1背包问题定义为：给定i个物品的价值v[1…i]、重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。
在面向对象技术中，类属是一种(1)机制。一个类属类是关于一组类的一个特性抽象，它强调的是这些类的成员特征中与(2)的那些部分，而用变元来表示与(3)的那些部分。
随机试题
在调制甜酸味时，如果出现偏甜的现象，可以用添加________的方法加以调节。
Ourpublictransportationsystemisnot______fortheneedsofthepeople.Weneedmorebusesandsubways.
A．每日换药1～2次B．每天换药1次C．隔1～2天换药1次D．隔2～3天换药E．3～5天后第一次换药感染伤口，分泌物较多，应()
关于反转时间(TI)的叙述，正确的是
后张法预制梁板时，预应力损失过大的原因有()。
根据现行法律规定，《会计法》适用于中华人民共和国境内，包括已回归祖国的香港、澳门地区。( )
会员单位应建立以()为核心的客户管理和服务制度，不得为不符合投资者适当性标准的投资者申请股指期货交易编码。
党的十九大报告指出，党的()是党的根本性建设，决定党的建设方向和效果。
甲手持匕首寻找抢劫目标时，突遇精神病人丙持刀袭击。丙追赶甲至一死胡同，甲迫于无奈，与丙搏斗，将其打成重伤。此后，甲继续寻找目标，见到丁后便实施暴力，用匕首将其刺成重伤，使之丧失反抗能力。此时甲的朋友乙驾车正好经过此地，见状后下车和甲一起取走丁的财物(约2万
A=HallucinogensB=CocaineC=AlcoholWhichdrug...mayslowdownbodyfunctions?【P1】______canleadtothedrivers’dis
最新回复
(
0
)
