niusouti.com

18、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。

题目

18、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。

相似考题

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

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

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

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

参考答案和解析
对
更多“18、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。”相关问题

  • 第1题：

    （ 4 ）霍夫曼算法是求具有最 【 4 】 带权外部路径长度的扩充二叉树的算法。


    正确答案：

  • 第2题：

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

  • 第3题：

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

    A.分治

    B.动态规划

    C.贪心

    D.回溯


    正确答案：C

  • 第4题：

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

    (62)

    A．分治

    B．动态规划

    C．贪心

    D．回溯


    正确答案：C

  • 第5题：

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


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

  • 第6题：

    第n最短路径问题

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

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


    正确答案：

     

     

  • 第7题：

    图的应用算法有()。

    A.拓扑排序算法
    B.哈夫曼算法
    C.迪杰斯特拉算法
    D.克鲁斯卡尔算法

    答案：A,C,D
    解析：
    图的应用算法包括遍历算法、最短路径和求解最小生成树。哈夫曼是最小生成树的算法。

  • 第8题：

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


    答案：错
    解析：

  • 第9题：

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

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

    正确答案:C

  • 第10题：

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

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

    正确答案:A,D,E

  • 第11题：

    填空题
    霍夫曼算法是求具有最（）带权外部路径长度的扩充二叉树的算法。

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

  • 第12题：

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

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

    B

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

    C

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

    D

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


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

  • 第13题：

    路径分析，其核心是最佳路径和最短路径的求解。比较这两者，可见()。

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

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

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

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


    参考答案：B

  • 第14题：

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

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


    正确答案：√

  • 第15题：

    霍夫曼算法是求具有最【 】带权外部路径长度的扩充二叉树的算法。


    正确答案：小
    小 解析：霍夫曼算法是用来求具有最小带权外部路径长度的扩充二叉树的算法。

  • 第16题：

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

    A.Dijkstra

    B.Floyed

    C.Prim

    D.Kruskal


    正确答案：A

  • 第17题：

    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;

  • 第18题：

    判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用______。

    A．求关键路径的方法

    B．求最短路径的Dijkstra方法

    C．深度优先遍历算法

    D．广度优先遍历算法


    正确答案：C
    解析：本题考查AOV的运算，要检测一个工程是否可行，首先就应检查对应的AOV网是否存在回路，检测的一种方法就是对有向图构造其顶点的拓扑有序序列，而对AOV网进行拓扑排序主要考虑顶点的入度，相应的，若在AOV网中考查各项点的出度，这种排序就称为逆排序。同时，还可以利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先遍历时，最先退出DFS函数的顶点即是出度为零的顶点，它是拓扑有序序列中最后的一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

  • 第19题：

    在求边稠密的图的最小代价生成树时，()算法比较合适。

    A.普里姆(Prim)
    B.克鲁斯卡尔(Kruskal)
    C.迪杰斯特拉(Dijkstra)
    D.其他

    答案：A
    解析：

  • 第20题：

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


    正确答案:递增

  • 第21题：

    模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。

    • A、KMP算法
    • B、Prime算法
    • C、克鲁斯卡尔算法
    • D、迪杰斯特拉算法

    正确答案:A

  • 第22题：

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

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

  • 第23题：

    多选题
    图的应用算法有（）
    A

    克鲁斯卡尔算法

    B

    哈弗曼算法

    C

    迪杰斯特拉算法

    D

    拓扑排序算法


    正确答案： C,D
    解析：

  • 第24题：

    单选题
    以下几种算法中可以求解起讫点不同的单一路径规划（最短路径问题）的是（　　）。
    A

    扫描法    

    B

    表上作业法    

    C

    单纯形法    

    D

    Dijkstra算法


    正确答案： A
    解析：
    起讫点不同的单一路径规划（最短路线问题）这是线路优化模型理论中最为基础的问题之一。求解此类最短路径问题，主要有以下几种算法（可参考线性规划类书籍）：Dijkstra算法、逐次逼近法和Floyd算法。

相关内容