itgle.com
70、Dijkstra算法是（）方法求出图中从某点到其余顶点最短路径的。A．通过深度优先遍历求出图中某顶点到其余顶点的最短路径B．通过广度优先遍历求出图中某顶点到其余顶点的最短路径C．按长度递减的顺序求出图的某顶点到其余顶点的最短路径D．按长度递增的顺序求出图的某顶点到其余顶点的最短路径
题目
70、Dijkstra算法是（）方法求出图中从某点到其余顶点最短路径的。
A．通过深度优先遍历求出图中某顶点到其余顶点的最短路径
B．通过广度优先遍历求出图中某顶点到其余顶点的最短路径
C．按长度递减的顺序求出图的某顶点到其余顶点的最短路径
D．按长度递增的顺序求出图的某顶点到其余顶点的最短路径
相似考题
更多“70、Dijkstra算法是（）方法求出图中从某点到其余顶点最短路径的。”相关问题
-
第1题：
设计一个算法,求图G中距离顶点v的最短路径长度最大的一个顶点,设v可达其余各个顶点。参考答案：
利用Dijkstra算法求v0到其它所有顶点的最短路径，分别保存在数组D[i]中，然后求出D[i]中值最大的数组下标m即可。
[算法描述]
int ShortestPath_MAX(AMGraph G, int v0){
//用Dijkstra算法求距离顶点v0的最短路径长度最大的一个顶点m
n=G.vexnum; //n为G中顶点的个数
for(v = 0; v
D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化
if(D[v]< MaxInt) Path [v]=v0; //如果v0和v之间有弧，则将v的前驱置为v0
else Path [v]=-1; //如果v0和v之间无弧，则将v的前驱置为-1
}//for
S[v0]=true; //将v0加入S
D[v0]=0; //源点到源点的距离为0
/*开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集*/
for(i=1;i
for(w=0;w
S[v]=true; //将v加入S
for(w=0;w
Path [w]=v; //更改w的前驱为v
}//if
}//for
/*最短路径求解完毕，设距离顶点v0的最短路径长度最大的一个顶点为m */
Max=D[0];
m=0;
for(i=1;i
}
-
第2题：
在AOE图中，关键路径是(39)。
A．从源点到汇点的最长路径
B．从源点到汇点的最短路径
C．最长的回路
D．最短的回路
正确答案：A
解析：在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网，简称AOE图。用AOE图表示一项工程计划时，对于一项工程来说，一般有一个开始状态和一个结束状态，所以在AOE网中至少有一个入度为0的开始顶点，称其为源点；另外，应有一个出度为。的结束顶点，称其为汇点。AOE中不应存在有向回路，否则整个工程无法完成。从源点到汇点的路径中，长度最长的路径称为关键路径，所以应选A。 -
第3题：
Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。()此题为判断题(对，错)。
正确答案：√
-
第4题：
关键路径是指AOE(Active On Edge)网中______。
A．最长的回路
B．最短的回路
C．从源点到汇点(结束顶点)的最长路径
D．从源点到汇点(结束顶点)的最短路径
A．
B．
C．
D．
正确答案：C
解析：AOE(Activity On Edge)网是一个有向图，通常用来估算工程的完成时间，图中的顶点表示事件，有向边表示活动，边上的权表示完成这一活动所需的时间。AOE网没有有向回路，存在唯一的入度为O的开始顶点，及唯一的出度为O的结束顶点。对AOE网最关心的两个问题是：完成整个工程至少需要多少时间?哪些活动是影响工程进度的关键?这就引出两个概念：关键路径和关键活动。
· 关键路径：从开始顶点到结束顶点的最长路径，路径的长度也是工程完成的最少时间。
· 关键活动：关键路径上的所有活动，关键活动的最大特征是：该活动的最早开始时间等于该活动所允许的最迟开始时间。关键活动拖延时间，整个工程也要拖延时间。求关键路径只需求出起点到终点的最长路径。注意，关键路径不是唯一的。 -
第5题：
下列算法中，()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。
A.Dijkstra
B.Floyed
C.Prim
D.Kruskal
正确答案：A
-
第6题：
关键路径是指AOE(Activity On Edge)网中(38)。
A．最长的回路
B．最短的回路
C．从源点到汇点(结束顶点)的最长路径
D．从源点到汇点(结束顶点)的最短路径
正确答案：C
解析：在AOE网中，用顶点表示活动，用有向边vi，vi＞表示活动vi必须先于活动vi进行。如果在有向环的带权有向图中用有向边表示一个工程中的各项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这种有向图叫做用边表示活动的网络，简称AOE网络。关键路径是指在AOE网络中从源点到汇点的最长路径。拓扑排序、最短路径和计算关键路径都是有向图的重要运算。根据关键路径的定义，正确答案为C。 -
第7题：
判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用______。
A．求关键路径的方法
B．求最短路径的Dijkstra方法
C．深度优先遍历算法
D．广度优先遍历算法
正确答案：C
解析：本题考查AOV的运算，要检测一个工程是否可行，首先就应检查对应的AOV网是否存在回路，检测的一种方法就是对有向图构造其顶点的拓扑有序序列，而对AOV网进行拓扑排序主要考虑顶点的入度，相应的，若在AOV网中考查各项点的出度，这种排序就称为逆排序。同时，还可以利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先遍历时，最先退出DFS函数的顶点即是出度为零的顶点，它是拓扑有序序列中最后的一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。 -
第8题：
RIP路由刷新的算法是（）。
- A、距离矢量算法
- B、最短路径优先算法
- C、Dijkstra算法
- D、生成树
正确答案:A -
第9题：
求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间约为（）ms。
正确答案:160 -
第10题：
关键路径是AOE网中（）。
- A、从源点到终点的最长路径
- B、从源点到终点的最短路径
- C、最长的回路
- D、最短的回路
正确答案:B -
第11题：
填空题用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。正确答案： 递增解析： 暂无解析 -
第12题：
判断题带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。A对
B错
正确答案： 错解析： 暂无解析 -
第13题：
阅读下列说明，回答问题l和问题2，将解答填入答题纸的对应栏内。
【说明】
现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。
现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。
下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：
W：权重矩阵
n：图的顶点个数
sP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n
rain_SP：最小的最短路径权重之和
min_v：具有最小的最短路径权重之和的顶点
i：循环控制变量
j：循环控制变量
k：循环控制变量
LOCATE-SHOPPINGMALL(W，n)
1 D(0)=W
2 for(1)
3 for i=1 t0 n
4 for j=1 t0 n
5
6 (2)
7 else
8 (3)
9 for i=1 to n
10 sP[i] =O
11 for j=1 to n
12 (4)
13 min sP=sP[1]
14 (5)
15 for i=2 t0 n
16 if min sP>sP[i]
17 min sP=sP[i]
18 min V=i
19 return (6)
正确答案：(1) k=1 tO n
(5)rain_v=1(6)min_v
(1) k=1 tO n
(5)rain_v=1(6)min_v
-
第14题：
求有向图G=(V,E)中每一对顶点间的最短路径,用Dijkstra算法和弗罗伊德算法,时间复杂度都是O(n3)。()此题为判断题(对，错)。
正确答案：√
-
第15题：
用Dijkstra算法求解最短路问题时,顶点标号的含义是()。A、该顶点到起点的最短路长度
B、该顶点到终点的最短路长度
C、与该顶点相连的最短边长度
D、以上说法均不对
参考答案：A
-
第16题：
●迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于(62)策略的算法。
(62)
A．分治
B．动态规划
C．贪心
D．回溯
正确答案：C
-
第17题：
● 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（61）策略的算法。 A.分治 B.动态规划 C.贪心 D.回溯
正确答案：C
试题61分析分治法：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。回溯算法（试探法）：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。针对单源最短路径问题，由Dijkstra提出了一种按路径长度递增的次序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看做是已生成的源点到其自身的长度为0的路径）。这是一种典型的贪心策略，就是每递增一次，经对所有可能的源点、目标点的路径都要计算，得出最优。带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。参考答案（61）C -
第18题：
关键路径是指AOE(Activity On Edge)网中______。
A．最长的回路
B．最短的回路
C．从源点到汇点(结束顶点)的最长路径
D．从源点到汇点(结束顶点)的最短路径
正确答案：C
-
第19题：
在AOE网络中关键路径叙述正确的是()。A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间
B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间
C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间
D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间答案：A解析：关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。 -
第20题：
用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。
正确答案:递增 -
第21题：
判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（）。
- A、求关键路径的方法
- B、求最短路径的Dijkstra方法
- C、深度优先遍历算法
- D、广度优先遍历算法
正确答案:C -
第22题：
带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。
正确答案:正确 -
第23题：
问答题请简述Dijkstra算法及其在GIS最短路径分析中的应用？正确答案： Dijkstra算法是按路径长度递增顺序产生各顶点的最短路径。
算法过程：设最短距离已确定的顶点集合称为红集点，最短距离尚未确定的为蓝集点。
1）按路径长度递增顺序产生
各蓝顶点的最短路径；
2）在当前蓝点集中选择一个距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的顺序产生各顶点的最短路径；
3）没扩充一个蓝点到红点集中，则剩余的蓝点的路径按照新加入的红点作为中间顶点进行修正，一旦加入新顶点使得蓝点路径长度最短，则用变短的路径代替原来的蓝点路径长度，重复以上过程；
4）直到所需求的蓝点已扩充到红点集时，算法结束。
应用：
1）选择要进行计算的两个结点；
2）对这两个结点进行联通分析，即采用宽度优先搜索方法，来快速判断这两个结点之间是否联通，也就是确定是否存在计算最短路径的必要，若联通则进行
3）调用Dijkstra算法，计算两个结点之间的最短路径
4）进过对计算出来的最短路径树进行优化处理后，生成最终的最短路径树，输出并推出。解析： 暂无解析 -
第24题：
填空题求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间约为（）ms。正确答案： 160解析： 暂无解析