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

题目

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

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

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

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

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

相似考题

1.Dijkstra 算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。()此题为判断题(对，错)。

2.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用()。A、求关键路径的方法B、求最短路径的Dijkstra方法C、宽度优先遍历算法D、深度优先遍历算法

3.● 求单源点最短路径的迪杰斯特拉（Dijkstra ）算法是按（57） 的顺序求源点到各 顶点的最短路径的。（57）A. 路径长度递减 B. 路径长度递增C. 顶点编号递减 D. 顶点编号递增

4.●试题六阅读以下说明和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++代码】#include<iostream．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算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻： S={0，2，3，4}，选取的目标顶点是顶点1 则可能修改最短路径是（）。”相关问题

  • 第1题：

    下面哪些使用的不是贪心算法()

    A.单源最短路径中的Dijkstra算法

    B.最小生成树的Prim算法

    C.最小生成树的Kruskal算法

    D.计算每对顶点最短路径的Floyd-Warshall算法


    正确答案：D

  • 第2题：

    求顶点间的最短路径问题，考虑的是下面的哪一种图()。

    A、无向图

    B、有向图

    C、带权的无向图

    D、带权的有向图


    参考答案：D

  • 第3题：

    阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。

    1. 【说明】

    实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。

    【算法】

    第一步：首先访问连通图G的指定起始顶点v；

    第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。

    第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。

    因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。


    正确答案：(1)邻接的顶点 (2)邻接的且未被访问的 (3)未访问过 (4)未被访问过的邻接点的 (5)访问过
    (1)邻接的顶点 (2)邻接的且未被访问的 (3)未访问过 (4)未被访问过的邻接点的 (5)访问过 解析：本题考查连通图的深度优先遍历算法的非递归过程。
    在做题前，我们首先来了解一下图的遍历。和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
    连通图的深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。其关键是每次遍历都是往下直到最后再往回搜索，找到还未被访问过的邻接点的顶点，然后从该顶点出发，对它及下面的顶点进行深度优先遍历。下面来具体分析其算法。
    第(1)空在第二步中，在访问起始顶点v后应该访问的结点，那么这个结点肯定是与起始顶点v邻接的顶点，因此此空答案为“邻接的顶点”。
    第(2)空是在访问p顶点后应该访问的顶点，接下来应该也是访问与p顶点邻接的顶点，但这个时候p顶点的邻接顶点中有已经被访问过了的顶点，因此在访问前还需判断此顶点是否被访问过了，所以此空答案为“邻接的且未被访问的”。
    第(3)空也在第二步中，结合前后的内容，可以知道此空是要判断是否还可以找到与当前访问顶点邻接而未被访问的顶点，根据上面分析，如果找不到，才往回搜索，因此此空答案为“未访问过”。
    第(4)空是回退过程中要注意的地方，一般回退到还未被访问过的邻接点的顶点，接着访问这个未被访问过的邻接点。因此此空答案为“未被访问过的邻接点的”。
    第(5)空是存放在栈中的内容，栈具有后进先出的特点，根据上面对深度优先遍历的分析可以知道，在回退的过程中需要用到被访问过的顶点，而且回退的过程是按遍历的顶点的顺序回退的，越后被访问的顶点越先被回退，因此此空答案是“访问过”。

  • 第4题：

    Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。()

    此题为判断题(对，错)。


    正确答案：√

  • 第5题：

    关键路径是指AOE(Active On Edge)网中______。

    A．最长的回路

    B．最短的回路

    C．从源点到汇点(结束顶点)的最长路径

    D．从源点到汇点(结束顶点)的最短路径

    A．

    B．

    C．

    D．


    正确答案：C
    解析：AOE(Activity On Edge)网是一个有向图，通常用来估算工程的完成时间，图中的顶点表示事件，有向边表示活动，边上的权表示完成这一活动所需的时间。AOE网没有有向回路，存在唯一的入度为O的开始顶点，及唯一的出度为O的结束顶点。对AOE网最关心的两个问题是：完成整个工程至少需要多少时间?哪些活动是影响工程进度的关键?这就引出两个概念：关键路径和关键活动。
      · 关键路径：从开始顶点到结束顶点的最长路径，路径的长度也是工程完成的最少时间。
      · 关键活动：关键路径上的所有活动，关键活动的最大特征是：该活动的最早开始时间等于该活动所允许的最迟开始时间。关键活动拖延时间，整个工程也要拖延时间。求关键路径只需求出起点到终点的最长路径。注意，关键路径不是唯一的。

  • 第6题：

    关键路径是指AOE(Activity On Edge)网中(38)。

    A．最长的回路

    B．最短的回路

    C．从源点到汇点(结束顶点)的最长路径

    D．从源点到汇点(结束顶点)的最短路径


    正确答案：C
    解析：在AOE网中，用顶点表示活动，用有向边vi，vi＞表示活动vi必须先于活动vi进行。如果在有向环的带权有向图中用有向边表示一个工程中的各项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这种有向图叫做用边表示活动的网络，简称AOE网络。关键路径是指在AOE网络中从源点到汇点的最长路径。拓扑排序、最短路径和计算关键路径都是有向图的重要运算。根据关键路径的定义，正确答案为C。

  • 第7题：

    关键路径是指AOE(Activity On Edge)网中______。

    A．最长的回路

    B．最短的回路

    C．从源点到汇点(结束顶点)的最长路径

    D．从源点到汇点(结束顶点)的最短路径


    正确答案：C

  • 第8题：

    判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。

    A.求关键路径的方法
    B.求最短路径的Dijkstra方法
    C.广度优先遍历算法
    D.深入度优先遍历算法

    答案：D
    解析：
    判断一个图是否存在回路的方法包括：(1)设图G是n个顶点的无向图，若G的边数e＞=n，则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图，若G的每个顶点的度＞=2，则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑排序输出结束后所余下的顶点均有前驱，则说明只得到了部分顶点的拓扑有序序列，图中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说，若深度优先遍历过程中遇到了回边则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上顶点的弧；但是，如果从有向图上的某个项点v出发进行深度优先遍历，若在dfs(v)结束之前出现一条认顶点v到顶点v的回边，因u在生成树上是v的孙子，则有向图必定存在半含顶点u和顶点v的环。

  • 第9题：

    阅读下列说明和?C?代码，回答问题?1?至问题?2，将解答写在答题纸的对应栏内。
    【说明】
    一个无向连通图?G?点上的哈密尔顿（Hamiltion）回路是指从图?G?上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路劲。一种求解无向图上哈密尔顿回
    路算法的基础私下如下：假设图?G?存在一个从顶点?V0?出发的哈密尔顿回路?V1——V2——V3——...——Vn-1——V0。算法从顶点?V0?出发，访问该顶点的一个未被访问的邻接顶点?V1，接着从顶点?V1?出发，访问?V1?一个未被访问的邻接顶点?V2，..。；对顶点?Vi，重复进行以下操作：访问?Vi?的一个未被访问的邻接接点?Vi+1；若?Vi?的所有邻接顶点均已被访问，则返回到顶点?Vi-1，考虑Vi-1?的下一个未被访问的邻接顶点，仍记为?Vi；知道找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
    【C?代码】
    下面是算法的?C?语言实现。
    （1）常量和变量说明
    n :图?G?中的顶点数
    c［］［］:图?G?的邻接矩阵
    K:统计变量，当期已经访问的定点数为?k+1
    x［k］:第?k?个访问的顶点编号，从?0?开始
    Visited［x［k］］：第?k?个顶点的访问标志，0?表示未访问，1?表示已访问
    ⑵C?程序




    【问题?1】（10?分）
    根据题干说明。填充?C?代码中的空（1）~（5）。
    【问题?2】（5?分）
    根据题干说明和?C?代码，算法采用的设计策略为（ ），该方法在遍历图的顶点时，采用的
    是（?）方法（深度优先或广度优先）。


    答案：
    解析：
    【问题 1】（10 分）



    【问题 2】（5 分）
    回溯法、深度优先。

  • 第10题：

    求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间约为（）ms。


    正确答案:160

  • 第11题：

    判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（）。

    • A、求关键路径的方法
    • B、求最短路径的Dijkstra方法
    • C、深度优先遍历算法
    • D、广度优先遍历算法

    正确答案:C

  • 第12题：

    单选题
    判定一个有向图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用（）。
    A

    求关键路径的方法

    B

    求最短路径的Dijkstra方法

    C

    深度优先遍历算法

    D

    广度优先遍历算法


    正确答案： D
    解析： 暂无解析

  • 第13题：

    设计一个算法,求图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　　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;
    　　}

  • 第14题：

    阅读下列说明，回答问题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

  • 第15题：

    求有向图G=(V,E)中每一对顶点间的最短路径,用Dijkstra算法和弗罗伊德算法,时间复杂度都是O(n3)。()

    此题为判断题(对，错)。


    正确答案：√

  • 第16题：

    用Dijkstra算法求解最短路问题时,顶点标号的含义是()。

    A、该顶点到起点的最短路长度

    B、该顶点到终点的最短路长度

    C、与该顶点相连的最短边长度

    D、以上说法均不对


    参考答案：A

  • 第17题：

    下列算法中，()算法用来求图中某顶点到其他顶点所有顶点之间的最短路径。

    A.Dijkstra

    B.Floyed

    C.Prim

    D.Kruskal


    正确答案：A

  • 第18题：

    B.Floyed算法求解所有顶点对之间的最短路径：

    procedure floyed;


    正确答案：

     

    begin
    for I:=1 to n do
    for j:=1 to n do
    if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点}
    for k:=1 to n do {枚举中间结点}
    for i:=1 to n do
    for j:=1 to n do
    if a[i,k]+a[j,k]<a[i,j] then begin
    a[i,j]:=a[i,k]+a[k,j];
    p[I,j]:=p[k,j];
    end;
    end;

  • 第19题：

    阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内。
    【说明】
    一个无向连通图G点上的哈密尔顿（Hamiltion）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路径。哈密尔顿回路算法的基础如下：假设图G存在一个从顶点V0出发的哈密尔顿回路V1--V2--V3--...--Vn-1--V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，..。；对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；直到找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
    【C代码】
    下面是算法的C语言实现。
    （1）常量和变量说明
    n :图G中的顶点数
    c［］［］:图G的邻接矩阵
    K:统计变量，当前已经访问的顶点数为k+1
    x［k］:第k个访问的顶点编号，从0开始
    Visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问
    （2）C程序

    #include #include #define MAX 100voidHamilton（intn,int x［MAX,intc[MAX][MAX]）｛int;int visited[MAX];int k;/*初始化 x 数组和 visited 数组*/for （i=0:i=0）｛x[k]=x[k]+1;while（x[k]
    【问题1】（10分）
    根据题干说明。填充C代码中的空（1）～（5）。
    【问题2】（5分）
    根据题干说明和C代码，算法采用的设计策略为（ ），该方法在遍历图的顶点时，采用的
    是（ ）方法（深度优先或广度优先）。


    答案：
    解析：
    【问题1】（10分）
    1. visited[0] = 1
    2. visited[x[k]] == 0
    3. k==n-1&&c[x[k]][x[0]==1
    4. visited[x[k]] = 1
    5. k = k - 1
    【问题2】（5分）
    回溯法、深度优先。

  • 第20题：

    在AOE网络中关键路径叙述正确的是()。

    A.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间
    B.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间
    C.从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间
    D.从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间

    答案：A
    解析：
    关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。

  • 第21题：

    用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。


    正确答案:递增

  • 第22题：

    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是（）。

    • A、G中有弧
    • B、G中有一条从Vi到Vj的路径
    • C、G中没有弧
    • D、G中有一条从Vj到Vi的路径

    正确答案:D

  • 第23题：

    填空题
    用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。

    正确答案： 递增
    解析： 暂无解析

  • 第24题：

    填空题
    求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间约为（）ms。

    正确答案： 160
    解析： 暂无解析

相关内容