itgle.com

第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。

题目

第n最短路径问题

*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。

*同理，第n最短路径可在求解第n-1最短路径的基础上求解。

相似考题

1.路径分析，其核心是最佳路径和最短路径的求解。比较这两者，可见()。A、最短路径不考虑网线和转角的阻碍强度，以求得两结点的最近路径B、当网线的阻碍强度为路线的长度，转角的阻碍强度为零，最佳路径就成为最短路径C、最佳路径为转角的阻碍强度为最小的路径D、最佳路径为网线上的阻碍强度为最小的路径

2.关键路径就是完成项目时间最短的路径。()

3.工期总和最短的一条路径成为关键路径,关键路径时间是完成该项目所需的最短时间。()此题为判断题(对，错)。

4.最短路径描述不正确的是()。A、由各个连线长度组成B、可能不止一条C、由网络最短路决策产生D、只是最短路径问题的可行解

参考答案和解析
正确答案：

 

 

更多“第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。”相关问题

  • 第1题：

    关键路径是()。

    A、工期总和最短的一条路径

    B、工期总和最长的一条路径

    C、活动数量最多的路径

    D、活动数量最少的路径


    参考答案：B

  • 第2题：

    最短路径描述不正确的是()。

    A、由各个连线长度组成

    B、可能不止一条

    C、由网络最短路决策产生

    D、只是最短路径的可行解


    参考答案：D

  • 第3题：

    最短路径

    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}

  • 第4题：

    关键路径是AOE网中()。

    A.最长的回路
    B.最短的回路
    C.从源点到终点的最长路径
    D.从源点到终点的最短路径

    答案：C
    解析：
    关键路径是指从开始顶点到结束顶点的最短路径，路径的长度也是工程完成的最少时间。关键活动是指关键路径上的所有活动，关键活动的最大特征是该活动的最早开始时间等于该活动所允许的最迟开始时间。

  • 第5题：

    第K条最短路径可分为哪两类？


    正确答案:一类是两点之间边分离的第K条最短路径；一类是两点之间点分离的第K条最短路径。

  • 第6题：

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


    正确答案:递增

  • 第7题：

    关键路径是AOE网中（）。

    • A、从源点到终点的最长路径
    • B、从源点到终点的最短路径
    • C、最长的回路
    • D、最短的回路

    正确答案:B

  • 第8题：

    OSPF使用最短路径优先（SPF）算法，根据拓扑结构计算最短路径树（SPFTree），其中最短路径树的节点是指（）。

    • A、路由器
    • B、路由器和网段
    • C、端口和网段
    • D、路由器和端口

    正确答案:B

  • 第9题：

    最短路径法的特点是什么？（）

    • A、该方法取最短路径为行驶路径，从起点到终点存在两条或两条以上的路径
    • B、将最短路径作为车辆选择路径，此方法最为简便，投资少
    • C、该方法取最短路径为行驶路径，从起点到终点存在两条或多条的路径
    • D、该方法取最短路径为行驶路径，从起点到终点存在多条路径

    正确答案:A,B

  • 第10题：

    单选题
    下面的说法正确的是（）
    A

    关键路径是项目网络图中耗时最长的路径，该历时代表了完成项目的最短时间

    B

    关键路径是项目网络图中耗时最短的路径，该历时代表了完成项目的最长时间

    C

    关键路径是项目网络图中耗时最长的路径，该历时代表了完成项目的最长时间

    D

    关键路径是项目网络图中耗时最短的路径，该历时代表了完成项目的最短时间


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

  • 第11题：

    单选题
    关于项目管理中的关键路径，正确的说法是（）
    A

    “关键”是指关键路径中最重要的活动

    B

    关键路径就是指最短的路径

    C

    因为是“关键”，所以只有唯一的一条关键路径

    D

    关键路径反映的是项目完成的最短时间


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

  • 第12题：

    单选题
    关键路径是事件结点网络中（  ）。
    A

    从源点到汇点的最长路径

    B

    从源点到汇点的最短路径

    C

    最长回路

    D

    最短回路


    正确答案： A
    解析：

  • 第13题：

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

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


    正确答案：√

  • 第14题：

    关键路径是事件结点网络中()。

    A.从源点到汇点的最长路径

    B.从源点到汇点的最短路径

    C.最长回路

    D.最短回路


    正确答案：A

  • 第15题：

    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;

  • 第16题：

    最短路径算法中的最短是指实际距离最短。()


    答案：错
    解析：

  • 第17题：

    OSPF使用最短路径优先（SPF）算法，根据拓扑结构计算最短路径树（SPFTree），以下关于最短路径树的节点描述正确的是？（）

    • A、最短路径树上的节点是对路由器和端口的描述
    • B、最短路径树上的节点有Transit节点和Stub节点两种类型
    • C、最短路径树上的路由器节点是Stub节点的一种
    • D、最短路径树上的路由器节点是Transit节点的一种

    正确答案:B,D

  • 第18题：

    关键路径是事件结点网络中（）。

    • A、从源点到汇点的最长路径
    • B、从源点到汇点的最短路径
    • C、最长的回路
    • D、最短的回路

    正确答案:A

  • 第19题：

    最短路径


    正确答案: 带权图中，从一个顶点V0到另一个顶点V1的一条路径上所经过边的权值之和定义为该路径的带权路径长度，其中最短的那条称作最短路径。此路径的长度称为从v到u的距离。

  • 第20题：

    关键路径是网络图中（）

    • A、时间最短的路径
    • B、时间最长的路径
    • C、最短的路径
    • D、最重要路径

    正确答案:B

  • 第21题：

    单选题
    关键路径是事件结点网络中（）。
    A

    从源点到汇点的最长路径

    B

    从源点到汇点的最短路径

    C

    最长的回路

    D

    最短的回路


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

  • 第22题：

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

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

  • 第23题：

    单选题
    路径分析，其核心是最佳路径和最短路径的求解。比较这两者，可见（）
    A

    最短路径不考虑网线和转角的阻碍强度，以求得两结点的最近路径

    B

    当网线的阻碍强度为路线的长度，转角的阻碍强度为零，最佳路径就成为最短路径

    C

    最佳路径为转角的阻碍强度为最小的路径

    D

    最佳路径为网线上的阻碍强度为最小的路径


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

相关内容