1、下列关于Dijkstra算法的哪些说法正确A．Dijkstra算法是求加权图G中从某固定起点到其余各点最短路径的有效算法；B．Dijkstra算法可用于求解无向图、有向图和混合图的最短路径问题；C．Dijkstra算法的时间复杂度为O(n^2)，其中n为顶点数；D．Dijkstra算法对边权无要求。

题目

1、下列关于Dijkstra算法的哪些说法正确

A．Dijkstra算法是求加权图G中从某固定起点到其余各点最短路径的有效算法；

B．Dijkstra算法可用于求解无向图、有向图和混合图的最短路径问题；

C．Dijkstra算法的时间复杂度为O(n^2)，其中n为顶点数；

D．Dijkstra算法对边权无要求。

相似考题

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

2.Dijkstra算法不适合用计算机求解，因为无法迭代。()

3.求最大流的算法是()。A、Dijkstra算法B、破圈法C、加边法D、Ford-Fulkerson算法

4.下面()算法适合构造一个稠密图G的最小生成树。A.Prim算法B、Kruskal算法C.Floyd算法D、Dijkstra算法

参考答案和解析
Dijkstra 算法能处理带负权值的图
更多“1、下列关于Dijkstra算法的哪些说法正确”相关问题

  • 第1题：

    C. Dijkstra 算法：

    var

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

    b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点}

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

    procedure dijkstra(v0:integer);


    正确答案：

     

    begin
    fillchar(mark,sizeof(mark),false);
    for i:=1 to n do begin
    d[i]:=a[v0,i];
    if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;
    end;
    mark[v0]:=true;
    repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
    min:=maxint; u:=0; {u记录离1集合最近的结点}
    for i:=1 to n do
    if (not mark[i]) and (d[i]<min) then begin
    u:=i; min:=d[i];
    end;
    if u<>0 then begin
    mark[u]:=true;
    for i:=1 to n do
    if (not mark[i]) and (a[u,i]+d[u]<d[i]) then begin
    d[i]:=a[u,i]+d[u];
    pre[i]:=u;
    end;
    end;
    until u=0;
    end;

  • 第2题：

    下列关于比例估算法的说法，不正确的是（）。



    答案：D
    解析：
    比例估算法是根据已知的同类建设项目主要生产工艺设备占整个建设项目的投资比例，先逐项估算出拟建项目主要生产工艺设备投资,再按比例估算拟建项目的静态投资的方法。

  • 第3题：

    下列关于OSPF协议的说法中，错误的是（ ）。

    A.OSPF 的每个区域（Area） 运行路由选择算法的一个实例
    B.OSPF 采用Dijkstra 算法计算最佳路由
    C.OSPF路由器向各个活动端口组播Hello分组来发现邻居路由器
    D.OSPF协议默认的路由更新周期为30秒

    答案：D
    解析：
    ospf没有固定的路由更新周期，这个30秒是rip的更新周期。

  • 第4题：

    RIP路由刷新的算法是（）。

    • A、距离矢量算法
    • B、最短路径优先算法
    • C、Dijkstra算法
    • D、生成树

    正确答案:A

  • 第5题：

    求最大流的计算方法有（）

    • A、Dijkstra算法
    • B、Floyd算法
    • C、加边法
    • D、Ford-Fulkerson算法

    正确答案:D

  • 第6题：

    Dijkstra算法可用于正权网络也可用于负权网络。


    正确答案:错误

  • 第7题：

    Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的无向图，Prim算法和Dijkstra算法还能保证获得最优解吗？


    正确答案: 1）prim算法的选择标准是选择当前与T连结边的代价最小的节点加入。
    2）Dijkstra算法的选择标准是在与T邻接的顶点w中，选择从S到w路径最短的顶点。
    3）prim算法用于有负边的图可以获得最优解，Dijkstra算法不能获得最优解。

  • 第8题：

    下列哪项是距离向量算法（DVA）的别名（）

    • A、Dijkstra算法
    • B、SPF算法
    • C、Bellman-Ford算法
    • D、LSA

    正确答案:C

  • 第9题：

    下列关于Bellman-Ford算法的说法正确的是（）.

    • A、RIP路由协议基于Bellman-Ford算法
    • B、Bellman-Ford算法本质上就是Dijkstra算法
    • C、Bellman-Ford算法无须知道全网拓扑结构
    • D、Bellman-Ford算法是链路状态算法

    正确答案:A,C

  • 第10题：

    判断题
    Dijkstra算法可用于求解最短路中的所有情形。
    A

    对

    B

    错


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

  • 第11题：

    判断题
    Dijkstra算法是求最大流的一种标号算法。
    A

    对

    B

    错


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

  • 第12题：

    问答题
    简要说明Dijkstra算法（标号法）思想

    正确答案： （1） 首先从起点O开始，给每个节点一个标号，分为T标号和P标号两类
    T.标号是临时标号，表示从起点O到该点的最短路权的上限；
    P.标号是固定标号，表示从起点O到该点的最短路权。
    （2） 标号过程中，T标点一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号
    （3） 算法的每一步把某一点的T标号该百年为P标号，知道所有的T标号都该改变为P标号。即得到草始点O到其他各点的最短路权，标号过程结束。
    解析： 暂无解析

  • 第13题：

    Dijkstra提出的银行家算法属于

    A)死锁预防

    B)死锁避免

    C)死锁检测

    D 死锁解除


    正确答案：B

  • 第14题：

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

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

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

  • 第15题：

    Dijkstra算法可用于求解有负权的网络最短路问题。


    正确答案:错误

  • 第16题：

    Dijkstra算法和Ford算法均要求边的权重非负。


    正确答案:错误

  • 第17题：

    Dijkstra算法可用于求解最短路中的所有情形。


    正确答案:错误

  • 第18题：

    下面（）算法适合构造一个稠密图G的最小生成树。

    • A、Prim算法
    • B、Kruskal算法
    • C、Floyd算法
    • D、Dijkstra算法

    正确答案:A

  • 第19题：

    下列哪些不是路由的发现算法（）

    • A、距离矢量算法
    • B、状态连接法
    • C、Dijkstra算法
    • D、LS算法

    正确答案:C,D

  • 第20题：

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

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

    正确答案:A,D,E

  • 第21题：

    问答题
    Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的无向图，Prim算法和Dijkstra算法还能保证获得最优解吗？

    正确答案： 1）prim算法的选择标准是选择当前与T连结边的代价最小的节点加入。
    2）Dijkstra算法的选择标准是在与T邻接的顶点w中，选择从S到w路径最短的顶点。
    3）prim算法用于有负边的图可以获得最优解，Dijkstra算法不能获得最优解。
    解析： 暂无解析

  • 第22题：

    判断题
    Dijkstra算法可用于求解有负权的网络最短路问题。
    A

    对

    B

    错


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

  • 第23题：

    问答题
    简述Dijkstra算法（标号法）思想

    正确答案： 1）首先从起点O开始，给每个节点一个标号，分为T标号和P标号两类：T标号是临时标号，表示从起点O到该点的最短路权的上限；P标号是固定标号，表示从起点O到该点的最短路权。
    2）标号过程中，T标点一直在改变，P标号不再改变，凡是没有标上P标号的点，都标上T标号
    3）算法的每一步把某一点的T标号该百年为P标号，知道所有的T标号都该改变为P标号。即得到草始点O到其他各点的最短路权，标号过程结束。
    解析： 暂无解析

  • 第24题：

    多选题
    下列关于Bellman-Ford算法的说法正确的是（）.
    A

    RIP路由协议基于Bellman-Ford算法

    B

    Bellman-Ford算法本质上就是Dijkstra算法

    C

    Bellman-Ford算法无须知道全网拓扑结构

    D

    Bellman-Ford算法是链路状态算法


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

相关内容