求最短路径常用的算法有()。A.Prim算法和Kruskal算法 B.深度优先遍历算法和广度优先遍历算法 C.Dijkstra算法和Floyd算法 D.拓扑排序算法

正确答案：B

 

参考答案：
　　利用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　　S[v] = false; //S初始为空集
　　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　　min= MaxInt;
　　for(w=0;w　　if(!S[w]&&D[w]　　{v=w; min=D[w];} //选择一条当前的最短路径，终点为v
　　S[v]=true; //将v加入S
　　for(w=0;w　　if(!S[w]&&(D[v]+G.arcs[v][w]　　D[w]=D[v]+G.arcs[v][w]; //更新D[w]
　　Path [w]=v; //更改w的前驱为v
　　}//if
　　}//for
　　/*最短路径求解完毕，设距离顶点v0的最短路径长度最大的一个顶点为m */
　　Max=D[0];
　　m=0;
　　for(i=1;i　　if(Max　　return m;
　　}

参考答案：D

正确答案：A

正确答案：√

正确答案：D

参考答案：B

正确答案：C

正确答案：C

正确答案：C
试题61分析分治法：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。回溯算法（试探法）：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。针对单源最短路径问题，由Dijkstra提出了一种按路径长度递增的次序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看做是已生成的源点到其自身的长度为0的路径）。这是一种典型的贪心策略，就是每递增一次，经对所有可能的源点、目标点的路径都要计算，得出最优。带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。参考答案（61）C