一般使用Floyd算法求解单源点到其余顶点之间的最短路径。

题目

一般使用Floyd算法求解单源点到其余顶点之间的最短路径。

相似考题

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

2.● 迪杰斯特拉（Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了 （63） 算法策略（63）A. 贪心B. 分而治之C. 动态规划D. 试探＋回溯

3.下面哪些使用的不是贪心算法()A.单源最短路径中的Dijkstra算法B.最小生成树的Prim算法C.最小生成树的Kruskal算法D.计算每对顶点最短路径的Floyd-Warshall算法

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

更多“一般使用Floyd算法求解单源点到其余顶点之间的最短路径。”相关问题

  • 第1题：

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

  • 第2题：

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

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


    正确答案：√

  • 第3题：

    用Floyd算法求解最短路问题,()。

    A、对于图中边的长度要求非负

    B、只适用于有向图

    C、只适用于无向图

    D、以上说法均不对


    参考答案：D

  • 第4题：

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

    A．最长的回路

    B．最短的回路

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

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

    A．

    B．

    C．

    D．


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

  • 第5题：

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

    A.Dijkstra

    B.Floyed

    C.Prim

    D.Kruskal


    正确答案：A

  • 第6题：

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

    A．最长的回路

    B．最短的回路

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

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


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

  • 第7题：

    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;

  • 第8题：

    求最短路径的FLOYD算法的时间复杂度为(16)。

    A．O(n)

    B．O(n+e)

    C．O(n2)

    D．O(n3)


    正确答案：D
    解析：FLOYD算法的时间复杂度为n3。

  • 第9题：

    距离向量路由算法要求每个节点保存一张距离向量表（即路由表），其中最关键的路由信息是（ ）。


    A.源节点到目的节点的最短距离
    B.源节点到目的节点的路径
    C.本节点到目的节点的输出节点（下一节点）地址
    D.本节点到目的节点的路径

    答案：C
    解析：
    距离向量路由算法要求每个节点保存一张距离向量表（即路由表），其中包括各目的节点、本节点到对应目的节点的最短距离、本节点到目的节点的输出节点（下一节点）地址。

  • 第10题：

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

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

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

  • 第11题：

    求解此类最短路径问题，主要有（）几种算法。

    • A、Dijkstra算法
    • B、地图里程法
    • C、实地测量法
    • D、逐次逼近法
    • E、Floyd算法

    正确答案:A,D,E

  • 第12题：

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

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

  • 第13题：

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

  • 第14题：

    迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。本质上说,该算法是一种基于()策略的算法。

    A.分治

    B.动态规划

    C.贪心

    D.回溯


    正确答案：C

  • 第15题：

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

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

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

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

    D、以上说法均不对


    参考答案：A

  • 第16题：

    ●迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于(62)策略的算法。

    (62)

    A．分治

    B．动态规划

    C．贪心

    D．回溯


    正确答案：C

  • 第17题：

    ● 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（61）策略的算法。 A.分治 B.动态规划 C.贪心 D.回溯


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

  • 第18题：

    最短路径

    A.标号法求解单源点最短路径：

    var

    a:array[1..maxn,1..maxn] of integer;

    b:array[1..maxn] of integer; {b[i]指顶点i到源点的最短路径}

    mark:array[1..maxn] of boolean;

    procedure bhf;

    var

    best,best_j:integer;


    正确答案：

     

    begin
    fillchar(mark,sizeof(mark),false);
    mark[1]:=true; b[1]:=0;{1为源点}
    repeat
    best:=0;
    for i:=1 to n do
    If mark[i] then {对每一个已计算出最短路径的点}
    for j:=1 to n do
    if (not mark[j]) and (a[i,j]>0) then
    if (best=0) or (b[i]+a[i,j]<best) then begin
    best:=b[i]+a[i,j]; best_j:=j;
    end;
    if best>0 then begin
    b[best_j]:=best；mark[best_j]:=true;
    end;
    until best=0;
    end;{bhf}

  • 第19题：

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

    A．最长的回路

    B．最短的回路

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

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


    正确答案：C

  • 第20题：

    试题（10）

    距离向量路由算法要求每个节点保存一张距离向量表（即路由表），其中最关键的路由信息是 （10） 。

    （10）

    A. 源节点到目的节点的最短距离

    B. 源节点到目的节点的路径

    C. 本节点到目的节点的输出节点（下一节点）地址

    D. 本节点到目的节点的路径


    正确答案：C
    试题（10）分析
    本题考查路由算法与协议方面的基本知识。
    距离向量路由算法要求每个节点保存一张距离向量表（即路由表），其中包括各目的节点、本节点到对应目的节点的最短距离、本节点到目的节点的输出节点（下一节点）地址。
    参考答案
    （10）C

  • 第21题：

    求最短路径常用的算法有()。

    A.Prim算法和Kruskal算法
    B.深度优先遍历算法和广度优先遍历算法
    C.Dijkstra算法和Floyd算法
    D.拓扑排序算法

    答案：C
    解析：
    A项是最小生成树的算法，B项是图的遍历算法，D项中的回溯法是求解递归过程的一种重要方法。

  • 第22题：

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


    正确答案:递增

  • 第23题：

    （）是基于单源点的最小费用路径算法。

    • A、Dijksta算法和Floyd-Warshall算法
    • B、Dijksta算法和Bellman-Ford算法
    • C、Bellman-Ford算法和Floyd-Warshall算法
    • D、Floyd-Warshall算法

    正确答案:B

  • 第24题：

    单选题
    求解最短路径的Floyd算法的时间复杂度为（  ）。
    A

    O（n）

    B

    O（n+c）

    C

    O（n*n）

    D

    O（n*n*n）


    正确答案： B
    解析：

相关内容