首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
admin
2021-01-13
55
问题
迪杰斯特拉(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://jikaoti.com/ti/AzG7FFFM
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某运输公司决定为新的售票机开发车票销售的控制软件。图13-15给出了售票机的面板示意图以及相关的控制部件。售票机相关部件的作用如下所述：(1)目的地键盘用来输入行程目的地的
阅读以下说明和图，回答问题l至问题3．将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统，用于处理客户通过电话、传真、邮件或web站点所下订单。其主要功能如下：(1)增加客户记录。将新客广信息添加到客户文件，并分配一个客户号以备后
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某医院欲开发病人监控系统。该系统通过各种设备监控病人的生命体征，并在生命体征异常时向医生和护理人员报警。该系统的主要功能如下：(1)本地监控：定期获取病人的生命特征，如体温、血
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某慈善机构欲开发一个募捐系统，己跟踪记录为事业或项目向目标群体进行募捐而组织的集体性活动。该系统的主要功能如下所述。(1)管理志愿者。根据募捐任务给志愿者发送加入邀请、邀请跟进
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某学校拟开发一套实验管理系统，对各课程的实验安排情况进行管理。【需求分析】一个实验室可进行多种类型不同的实验。由于实验室和实验员资源有限，需根据学生人数分批次安排实验室和实验
阅读以下说明，根据要求回答问题1～问题3。【说明】某快递公司为了方便管理公司物品运送的各项业务活动，需要构建一个物品运送信息管理系统。【需求分析结果】(1)快递公司有多个分公司，分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公司可以
某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。【需求分析结果】(1)商场需要记录的信息包括商场编号(编号唯一)、商场名称、地址和联系电话。某商场信息如表13-1所示。(2)每个商场包含不
某高校欲开发一个成绩管理系统。记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下。(1)每门课程都由3～6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成绩。(
阅读下列说明和C++代码，填写程序中的空(1)～(6)，将解答写入答题纸的对应栏内。【说明】以下C++代码实现一个简单绘图工具，绘制不同形状以及不同颜色的图形。部分类及其关系如图7所示。【C++代码】#includ
软件测试是软件开发中不可缺少的活动，通常(35)在代码编写阶段进行。检查软件的功能是否与用户要求一致是(36)的任务。
随机试题
以下费用中也称为间接费用的是()。
胆囊动脉多源于（）
决定社会面貌的基本因素是（）
生地、熟地同用的方剂是
无明显临床症状的女性淋球菌感染者为
药材商品称荆三棱的原植物为
下列抗生素类抗真菌药，唯一可用于治疗深部和皮下真菌感染的是()。
商用房贷款的贷款期限在1年以内(含1年)的，实行合同利率，遇法定利率调整可分段计息。()
新的国家安全观不仅包括传统的政治安全和国防安全，还包括经济安全、科技安全、文化安全、生态安全、社会公共安全等。其中，国家安全的支柱与核心是
数据清洗工作不包括(10)。
最新回复
(
0
)
