免费智能真题库
>
历年试卷
>
软件设计师
>
2011年下半年 软件设计师 上午试卷 综合知识
第62题
知识点:
单源点最短路径
最短路径
关键词:
算法
最短路径
章/节:
计算机软件知识
迪杰斯特拉(Dijkstra)算法用于求解图上的
单源点
最短路径
。该算法按路径长度递增次序产生
最短路径
,本质上说,该算法是一种基于(62)策略的算法。
A. 分治
B. 动态规划
C. 贪心
D. 回溯
本题目为专供试卷题目。
【如需要,请开通】
您暂时无法使用本功能。
【如需要,请开通】
为保障您的权益,请登录
相关试题:图
更多>
第18题
2017年下半年
55%
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,链接顶点的边表示包含的活动,边上数字表示活动的持续时间(天)。完成..
第65题
2014年上半年
52%
Prim算法和Kruscal算法都是无向连通网的最小生成树的算法,Prim算法从一个顶点开始,每次从剩余的顶点中加入一个顶点,该顶点与当..
第61题
2019年下半年
64%
对于如下所示的有向图,其邻接矩阵是一个(60)的矩阵。采用邻接链表存储时,顶点1的表结点个数为2,顶点5的表结点个数为0,顶点2和..
相关试题:最短路径
更多>
第65题
2022年下半年
30%
采用Dijkstra算法求解下图A点到E点的最短路径,采用的算法设计策略是(64),该最短路径的长度是(65)?。
第64题
2022年下半年
41%
采用Dijkstra算法求解下图A点到E点的最短路径,采用的算法设计策略是(64),该最短路径的长度是(65)?。
知识点讲解
·
单源点最短路径
·
最短路径
单源点最短路径
单源点最短路径是指给定带权有向图
G
和源点
v
,求从
v
到
G
中其余各顶点的最短路径。迪杰斯特拉提出了按路径长度递增的次序产生最短路径的算法。
最短路径
单源点最短路径
单源点最短路径是指给定带权有向图
G
和源点
v
,求从
v
到
G
中其余各顶点的最短路径。迪杰斯特拉提出了按路径长度递增的次序产生最短路径的算法。
每对顶点间的最短路径
若每次以一个顶点为源点,重复执行迪杰斯特拉算法
n
次,便可求得网中每一对顶点之间的最短路径。弗洛伊德提出了求最短路径的算法,该算法在形式上要简单一些。
题号导航
2011年下半年 软件设计师 上午试卷 综合知识
本试卷我的完整做题情况
1
/
2
/
3
/
4
/
5
/
6
/
7
/
8
/
9
/
10
/
11
/
12
/
13
/
14
/
15
/
16
/
17
/
18
/
19
/
20
/
21
/
22
/
23
/
24
/
25
/
26
/
27
/
28
/
29
/
30
/
31
/
32
/
33
/
34
/
35
/
36
/
37
/
38
/
39
/
40
/
41
/
42
/
43
/
44
/
45
/
46
/
47
/
48
/
49
/
50
/
51
/
52
/
53
/
54
/
55
/
56
/
57
/
58
/
59
/
60
/
61
/
62
/
63
/
64
/
65
/
66
/
67
/
68
/
69
/
70
/
71
/
72
/
73
/
74
/
75
/
第62题 在手机中做本题