首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
admin
2021-01-13
81
问题
迪杰斯特拉(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://kaotiyun.com/show/8tCZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图，回答问题l至问题4，将解答填入答题纸的对应栏内。【说明】某公司欲开发招聘系统以提高招聘效率，其主要功能如下：(1)接受申请验证应聘者所提供的自身信息是否完整，是否说明了应聘职位，受理验证合格的申请，给应聘者发送致谢信息。(2)评
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某学校开发图书管理系统，以记录图书馆藏图书及其借出和归还情况，提供给借阅者借阅图书功能，提供给图书馆管理员管理和定期更新图书表功能。主要功能的具体描述如下：(1)处理借阅。借阅者
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某学校拟开发一套实验管理系统，对各课程的实验安排情况进行管理。【需求分析】一个实验室可进行多种类型不同的实验。由于实验室和实验员资源有限，需根据学生人数分批次安排实验室和实验
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是：(1)初始时拓扑序列为空：(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；(3)重复(2)，
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】某应用中需要对100000个整数元素进行排序，每个元素的取值在0～5之间。排序算法的基本思想是：对每一个元素x，确定小于等于x的元素个数(记为m)，将x放在输出元素序列的第m
某高校欲开发一个成绩管理系统。记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下。(1)每门课程都由3～6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成
某高校欲开发一个成绩管理系统。记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下。(1)每门课程都由3～6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成绩。(
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某软件公司欲设计实现一个虚拟世界仿真系统。系统中的虚拟世界用于模拟现实世界中的不同环境(由用户设置并创建)，用户通过操作仿真系统中的l～2个机器人来探索虚拟世界。机器人维护着两个
国际标准MPEG—Ⅱ采用了分层的编码体系，提供了4种技术，它们是(46)。数字音频采样和量化过程所用的主要硬件是：(47)。AC-3数字音频编码提供了5个声道的频率范围是：(48)。要把一台普通的计算机变成多媒体计算机要解决的关键技术是：(
The most accurate and most boring way to(66)Java is that it is a new computer programming language developed by Sun Microsystems
随机试题
()是生产物流系统的终点，也是销售物流系统的起点。
＝________．
1岁小儿，7个月时会翻身和独坐，现坐不稳，脸色渐苍白，外周血象见红细胞体积大，中性粒细胞呈分叶过多现象，此小儿最可能的诊断是
患者，男，70岁。家属代诉：患者于今晨起床后半小时，突然昏仆，不省人事，目合口张，遗溺，手撤，四肢厥冷，脉细弱，治疗用隔盐灸，应取穴
有眩晕、眼震、构音障碍、交叉性瘫痪，见于有偏瘫、同向性偏盲、偏身感觉障碍，见于
根据《土地登记办法》，引起土地使用权变更的原因有()。
()是指借款人按借款合同约定的还款计划和还款方式及时、足额地偿还贷款本息。
如果一杯咖啡在巴黎为3欧元，在纽约为6美元，并且购买力平价理论成立，那么汇率是()。
Usingtheinformationinthepassage,completethetablebelow.Writeyouranswersinboxes8-10onyouranswersheet.
Theyhavealreadydiscussedthereport(give)______bythedepartmentmanager.
最新回复
(
0
)
