多项选择题
给定带权有向图G =（V，E），其中每条边的权是非负实数。另外，给定V中的一个顶点A，称为源，求从源顶点A出发到其他各顶点的最短路径长度称为单源最短路径长度问题。关于单源最短路径问题的Dijkstra 算法，下面哪些描述是正确的？（）
A.设定一个顶点集合S，初始时，S={A}，每次从V-S中选择顶点加入S，直到全部加入，算法结束
B.每次选择加入S集合的顶点是从A顶点出发的最短路径长度已知的顶点，也就是V-S集合中最短特殊路径长度最小的顶点，通常算法中用dist[]数组记录各顶点的最短特殊路径长度
C.每次从V-S集合选择加入S集合的顶点是V-S集合中的顶点同S集合的顶点连接边最短的，通常算法中用dist[]数组记录S集合中各顶点与V-S集合中各顶点的最短连接边
D.每次选择一个顶点加入S集合后，都要检查是否需要更新dist[]数组元素的值
点击查看答案
相关考题
-
单项选择题
下图中A~F顶点分别代表6个村庄，图中的边代表村庄之间的距离，为了满足这六个村庄相互通信的需要（任意两个村庄有线路可达），需要架设通信线路，这里要求代价最小化（即线路总长度最小），请你分析问题找到代价最小的方案，并计算出线路总长度（）。
A.线路总长度22
B.线路总长度20
C.线路总长度21
D.线路总长度23 -
单项选择题
哈夫曼编码树是用贪心算法解决的典型问题，分析该算法，回答如下问题，假定有n个字符生成的编码树，问编码树中的结点总数是多少？可能的最长的字符编码是多少位？（）
A.2n-1个结点；n-1位编码
B.2n个结点；n-1编码
C.2n个结点；n位编码
D.2n-1个结点；n位编码 -
单项选择题
某中学有一个开水房，只有一个供热水龙头，课间时，会有很多同学去排队打开水，同学们的水瓶大小不一，每个同学打水时都会将自己的水瓶装满。管理开水房的师傅是个聪明人，他想到了一个排队方案，也就是同学们按照他给出的排队方法，可以使同学们的平均等待时间最短。你分析一下，给出这个排队的方法，假定有n个人，第i个同学打水所需要的时间为ti，并给出平均等待时间的计算公式（）。（注意：第i个同学的等待时间包含前i-1个的打水时间和+自己打水的时间ti）
A.按照打水时间从大到小排队，假定排队后第i个人的打水时间是ti，平均等待时间T=∑（n-i+1）ti/n 1< =i< =n
B.按照打水时间从大到小排队，平均等待时间T=∑ti/n 1< =i< =n
C.按照打水时间从小到大排队，平均等待时间T=∑ti/n 1< =i< =n
D.按照打水时间从小到大排队，假定排队后第i个人的打水时间是ti，平均等待时间T=∑（n-i+1）ti/n 1< =i< =n
