网友您好， 请在下方输入框内输入要搜索的题目：
题目内容
（请给出正确答案）
51、在一个带权有向图G中，某两个顶点间的最短路径，一定包含路径起点关联的最短弧。
参考答案和解析
B
更多 “51、在一个带权有向图G中，某两个顶点间的最短路径，一定包含路径起点关联的最短弧。” 相关考题
考题
●试题六阅读以下说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】本题将有向网(带权有向图)定义为类AdjacencyWDigraph。类中的数据成员n表示有向网中的顶点数;a为带权邻接矩阵，用于存储有向网中每一对顶点间弧上的权值;c为二维数组，存储有向网中每一对顶点间的最短路径长度;kay为二维数组，存储最短路径，kay［i］［j］=k表示顶点i 到达顶点j的最短路径必须经过顶点k。类中的主要成员函数有：Input():输入有向网的顶点数、各条弧及权值，建立带权领接矩阵a。若顶点i到顶点j有弧，则a［i］［j］取弧上的权值，否则a［i］［j］的值取NoEdge。AllPairs();用弗洛伊德(Floyd)算法求有向网中每一对顶点间的最短路径长度。OutShortestPath(int i,int j):计算顶点i到顶点j的最短路径。outputPath(int i,int j):输出顶点i到顶点j的最短路径上的顶点。Floyd算法的基本思想是递推地产生一个矩阵序列C0,C1，C2，…，Cn,其中C0是已知的带权邻接矩阵，a,Ck(i,j)(0≤i,j＜n)表示从顶点i到顶点j的中间顶点序号不大于k 的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k＜n,有Ck(i,j)=C0(i,j)=a［i］［j］。递推地产生C1，C2，…，Cn的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。【C++代码】#includeiostream．h＃define NoEdge 10000 //当两个顶点之间没有边相连时，在邻接矩阵中用NoEdge表示void Make2DArray(int * * x,int rows,int cols);class AdjacencyWDigraph{privateint n;//有向网中的顶点数目int**a;//存储顶点间弧上的权值int**c;//存储计算出的最短路径长度int**kay;//存储求出的最短路径pubic:int Vertices()const {return n;}void AllPairs();void Input();//输入有向网的顶点数、各条弧及权值，建立邻接矩阵avoid OutShortestPath(int i,int j);//计算顶点i到j的最短路径(试卷中未列出)~AdjacencyWDigraph();//析构函数(试卷中未列出)private:void outputPath(int i,int j);};void AdjacencyWDigraph::AllPairs(){int i,j,k,t1,t2,t3;for(i=1;i＜=n;k++)for(j=1;j＜=n;++j){c［i］［j］= (1) ;kay［i］［j］=0;}for(k=1;k＜=n;k++)for(i=1;i＜=n;i++){if(i==k) continue;t1=c［i］［k］;for(j=1;j＜=n;j++){if(j==k||j==i)continue;t2=c［k］［j］;t3=c［i］［j］;if(t1!=NoEdge t2!=NoEdge (t3==NoEdge||t1+t2＜t3)){c［i］［j］= (2) ；kay［i］［j］= (3) ;}}//for}//for}void AdjacencyWDigraph:: outputPath(int i,int j){//输出顶点i到j的最短路径上的顶点if(i==j)return;if(kay［i］［j］==0)cout＜＜j＜＜′′;else { outputPath(i, (4) ); outputPath( (5) );}}void Adjacency WDigraph::Input(){int i,j,u,v,w,E;cout＜＜″输入网中顶点个数：″;cin＞＞n;cout＜＜″输入网中弧的个数:″;cin＞＞E;Make2DArray(a,n+1,n+1);for(i=1;i＜=n;i++)for(j=1;j＜=n;j++)a［i］［j］=NoEdge;for(i=1;i＜=n;i++)a［i］［i］=0;Make2DArray(c,n+1,n+1);Make2DArray(kay,n+1,n+1);for(i=1;i＜=E;i++){cout＜＜″输入弧的信息(起点终点权值)：″；cin＞＞u＞＞v＞＞w;a［u］［v］=w;}}void Make2DArray(int**x,int rows,int cols){int i,j;x=new int*［rows+1］;for(i=0;i＜rows+1;i++)x［i］=new int ［cols+1］;for(i=1;i＜=rows;i++)for(j=1;j＜=cols;j++＝x［i］［j］=0;}
考题
● 求单源点最短路径的迪杰斯特拉（Dijkstra ）算法是按（57） 的顺序求源点到各 顶点的最短路径的。（57）A. 路径长度递减 B. 路径长度递增C. 顶点编号递减 D. 顶点编号递增
考题
阅读下列说明，回答问题l和问题2，将解答填入答题纸的对应栏内。【说明】现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：W：权重矩阵n：图的顶点个数sP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到nrain_SP：最小的最短路径权重之和min_v：具有最小的最短路径权重之和的顶点i：循环控制变量j：循环控制变量k：循环控制变量LOCATE-SHOPPINGMALL(W，n)1 D(0)=W2 for(1)3 for i=1 t0 n4 for j=1 t0 n56 (2)7 else8 (3)9 for i=1 to n10 sP[i] =O11 for j=1 to n12 (4)13 min sP=sP[1]14 (5)15 for i=2 t0 n16 if min sPsP[i]17 min sP=sP[i]18 min V=i19 return (6)
考题
关键路径是指AOE(Active On Edge)网中______。A．最长的回路B．最短的回路C．从源点到汇点(结束顶点)的最长路径D．从源点到汇点(结束顶点)的最短路径A．B．C．D．
考题
在具有6个顶点的无向简单图中，当边数最少为(26)条时，才能确保该图一定是连通图，当边数最少为(27)条时，才能确保该图一定是哈密尔顿图。给定带权的有向图，如下图所示。设该图代表一个地区的交通图，从S到T的最短路径有(28)条，路径的长度是(29)，从S出发经过每点一次且只有一次到T的路径(哈密尔顿路径)有(30)条。A．11B．12C．13D．55
考题
以下说法中正确的是(49)。A．带权连通图的某最小生成树的权值之和一定小于其他生成树的权值之和B．从源点到终点的最短路径是惟一的C．任意一个AOV网不一定存在拓扑序列D．任意一个AOE网中的关键路径是惟一的
考题
第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。
考题
在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。A.一定存在弧B.
在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（59）。A.一定存在弧＜vi,vj＞B.一定存在弧＜vj,vi＞C.可能存在vi到vj的路径，而不可能存在vj到vi的路径D.可能存在vj到vi的路径，而不可能存在vi到vj的路径
考题
从起点到终点的最短路线，以下叙述（）不正确。A、从起点出发的最小权有向边必含在最短路线中B、整个图中权最小的有向边必包含在最短路线中C、整个图中权最大的有向边可能含在最短路线中D、从起点到终点的最短路线是唯一的
考题
最短路径法的特点是什么？（）A、该方法取最短路径为行驶路径，从起点到终点存在两条或两条以上的路径B、将最短路径作为车辆选择路径，此方法最为简便，投资少C、该方法取最短路径为行驶路径，从起点到终点存在两条或多条的路径D、该方法取最短路径为行驶路径，从起点到终点存在多条路径
考题
多选题关于最短路，以下叙述（）不正确。A从起点出发到终点的最短路是唯一的B从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的C从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上D从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上E整个网络的最大权边的一定不包含在从起点到终点的最短路线上
热门标签
最新试卷
