首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
admin
2021-01-13
51
问题
迪杰斯特拉(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下：对于n个元素的关键字序列{a1，a2，…，an}，当且仅当满足下列关系时称其为堆。在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】设有m台完全相同的机器运行n个独立的任务，运行任务i所需要的时间为ti，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基
阅读下列说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表17—3所示。为支持将来模拟更多种类的飞机，采用策
某软件公司现欲开发一款飞机飞行模拟系统，该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表16—4所示。为支持将来模拟更多种类的飞机，采用策略设计模式(Strategy)设计的类图如图16一12所示。图16—12中，Ai
阅读下列说明和图，回答问题。【说明】某大学为进一步推进无纸化考试，欲开发一考试系统。系统管理员能够创建包括专业方向、课程编号、任课教师等相关考试基础信息，教师和学生进行考试相关的工作。系统与考试有关的主要功能如下。(1)考试设置。教师制定试
某高校欲开发一个成绩管理系统。记录并管理所有选修课程的学生的平时成绩和考试成绩，其主要功能描述如下。(1)每门课程都由3～6个单元构成，每个单元结束后会进行一次测试，其成绩作为这门课程的平时成绩。课程结束后进行期末考试，其成绩作为这门课程的考试成绩。(
(2021年下半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】设有n个货物要装入若干个容重为C的集装箱以便运输，这n个货物的体积分别为{s1，s2，…，sn}，且有si≤C(1≤i≤n)。为
在RS-232C接口信号中，数据终端就绪信号的连接方向为(61)。
The most accurate and most boring way to(66)Java is that it is a new computer programming language developed by Sun Microsystems
王某是某公司的软件设计师，完成某项软件开发后按公司规定进行软件归档。以下有关该软件的著作权的叙述中，正确的是________。
随机试题
下列哪项不是痂下愈合的特点
参与细胞间信号传递的物质有
对于婴儿住院时的护理叙述不正确的是
下列有关硝普钠的叙述中，错误的是
类风湿关节炎的关节外表现的基本病理改变是
A、甲类非处方药B、终止妊娠药品C、乙类非处方药D、未列入非处方药目录的抗菌药不得在零售药店销售的是()。
填制记账凭证若发生了错误，正确的处理方法是()。
某省辖市一事业单位未按要求报送统计报表，收到统计报表催报单后，仍未按规定时间上报。市统计局认为该单位涉嫌统计违法，遂向其先后送达统计行政处罚告知书和行政处罚决定书。该单位不服市统计局的处罚决定，先后申请了行政复议，提起了行政诉讼。经审理，受理行政复议和行政
下列关于事前风险的说法中，错误的是()。
解方程x2+2．5|x|-1．5=0．
最新回复
(
0
)
