设计一个算法,求图G中距离顶点v的最短路径长度最大的一个顶点,设v可达其余各个顶点。

第1题：

71、用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻： S={0，2，3，4}，选取的目标顶点是顶点1，则可能修改最短路径是（）。

A．从顶点2到顶点4的最短路径

B．从顶点0到顶点1的最短路径

C．从顶点0到顶点3的最短路径

D．从顶点0到顶点2的最短路径

第2题：

5、求单源点最短路径的Dijkstra算法是按（）的顺序求源点到各顶点的最短路径的。

A．路径长度递减

B．路径长度递增

C．顶点编号递减

D．顶点编号递增

第3题：

73、有一个顶点编号为0～4的带权有向图G，现用Floyd算法求任意两个顶点之间的最短路径，在算法执行的某时刻，已考虑了0～2的顶点，现考虑顶点3，则以下叙述中正确的是（）。

A．只可能修改从顶点3到顶点0～2的最短路径

B．只可能修改从顶点0～2到顶点3的最短路径

C．所有两个顶点之间的路径都可能被修改

D．只可能修改从顶点0～2到顶点4的最短路径

第4题：

顶点v的父亲点f（v)记录的是从起点v0到v的当前最短路径上v的前一个顶点。

第5题：

7、给定带权有向图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[]数组元素的值