首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基干______策略的算法。
admin
2021-01-13
59
问题
迪杰斯特拉(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图，回答问题1至问题3，将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方，通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下：(1)注册。顾客在买药之前，必须先在网上药店注册。注册过程中需填写顾客资料
阅读以下说明，根据要求回答问题1～问题3。【说明】某快递公司为了方便管理公司物品运送的各项业务活动，需要构建一个物品运送信息管理系统。【需求分析结果】(1)快递公司有多个分公司，分公司信息包括分公司编号、名称、经理、办公电话和地址。每个分公司可以
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】对有向图进行拓扑排序的方法是：(1)初始时拓扑序列为空：(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；(3)重复(2)，
阅读下列说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】现要求实现一个能够自动生成求职简历的程序，简历的基本内容包括求职者的姓名、性别、年龄及工作经历。希望每份简历中的工作经历有所不同，并尽量减少程序中的重复代码。现采
阅读下列说明和图，回答问题l～问题3，将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSegment)构成，每个路段
(2021年下半年下午试题四)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】设有n个货物要装入若干个容重为C的集装箱以便运输，这n个货物的体积分别为{s1，s2，…，sn}，且有si≤C(1≤i≤n)。为
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】0-1背包问题定义为：给定i个物品的价值v[1…i]、重量w[1…i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。
容量为64块的Cache采用组相联方式映像，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应为(7)位，主存区号应为(8)位。
实体联系模型(简称ER模型)中的基本语义单位是实体和联系。ER模型的图形表示称为ER图。联系可以同(37)实体有关。实体与实体之间的联系可以是(38)。利用ER模型进行数据库的概念设计，可以分成3步：首先设计局部ER，然后把各个局部ER模型综合成一个全局
设集合A={{1，2，3}，{4，5}，{6，7，8}}，则下式为真的是(19)，设A：{1，2}，B={a，L，c}，C={c，d}，则Ax(B∩C)=(20)。
随机试题
背景某写字楼，剪力墙结构。因工程需要在其剪力墙的外侧安装点式玻璃幕墙。土建工程已经完毕，施工时没有预埋件，而且抹灰工序已经完成。现需要在该处安装后埋件，安装完毕后土建要对其进行抹灰和涂料处理；抹灰后埋件不得外露。监理工程师要求上报安装后埋件前对剪力墙部位
胆总管末端位于十二指肠的（）
关于多层螺旋CT能够同时采集多幅图像的数据，关键的改革是
A、62～115μmol/LB、53～97μmol/LC、3.1～5.7mmol/LD、0.56～1.70mmol/LE、1.9～3.61mmol/L男性血肌酐用Taffe法测定的参考范围是
A．清暑益气丸B．藿香正气水C．九味羌活丸D．小活络丸E．薏苡仁汤发热汗多，头痛面红，烦躁，胸闷，口渴多饮。舌红少津，脉洪大，当选用的中成药是()。
下列测绘成果中，属于机密级测绘成果的是()。
《建设工程施工合同(示范文本)》规定，如需验收，应( )。
国家助学贷款是由国家指定的商业银行面向在校的全日制高等学校中经济确实困难的()，用于帮助他们支付在校期间的学费和H常生活费，并由教育部门设立“助学贷款专户资金”给予财政贴息的贷款。
完全竞争市场和垄断竞争市场的主要区别在于()。
关于收养人的条件，下列说法错误的是()。
最新回复
(
0
)
