计算机类
单选题求解最短路径的Floyd算法的时间复杂度为（ ）。A O（n）B O（n+c）C O（n*n）D O（n*n*n）
题目
O（n）
O（n+c）
O（n*n）
O（n*n*n）
参考答案和解析
相似问题和答案
第1题：
路径分析，其核心是最佳路径和最短路径的求解。比较这两者，可见()。
A、最短路径不考虑网线和转角的阻碍强度，以求得两结点的最近路径
B、当网线的阻碍强度为路线的长度，转角的阻碍强度为零，最佳路径就成为最短路径
C、最佳路径为转角的阻碍强度为最小的路径
D、最佳路径为网线上的阻碍强度为最小的路径
第2题：
A.分治
B.动态规划
C.贪心
D.回溯
第3题：
● 迪杰斯特拉（Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了 （63） 算法策略
（63）
A. 贪心
B. 分而治之
C. 动态规划
D. 试探＋回溯
第4题：
距离-向量路由算法最优路径计算的复杂度要比链路-状态路由算法最优路径计算的复杂度大。
此题为判断题(对，错)。
第5题：
●迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于(62)策略的算法。
(62)
A．分治
B．动态规划
C．贪心
D．回溯
第6题：
此题为判断题(对，错)。
第7题：
A、对于图中边的长度要求非负
B、只适用于有向图
C、只适用于无向图
D、以上说法均不对
第8题：
下面哪些使用的不是贪心算法()
A.单源最短路径中的Dijkstra算法
B.最小生成树的Prim算法
C.最小生成树的Kruskal算法
D.计算每对顶点最短路径的Floyd-Warshall算法
第9题：
下列关于算法复杂度描述正确的是（ ）。
A. 算法的时间复杂度是指算法执行的时间
B. 算法的空间复杂度是指执行这个算法所需的内存空间
C. 一个算法的空间复杂度大，则其时间复杂度必定大
D. 一个算法的空间复杂度大，则其时间复杂度必定小
算法的时间复杂度是指执行算法所需的计算工作量。算法的空间复杂度是指执行这个算法所需的内存空间。在一个算法的空间复杂度大的情况下，其时间复杂度可能会很大，具体视情况而定；反之亦然。
第10题：
● 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于（61）策略的算法。 A.分治 B.动态规划 C.贪心 D.回溯
试题61分析分治法：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。回溯算法（试探法）：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。针对单源最短路径问题，由Dijkstra提出了一种按路径长度递增的次序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看做是已生成的源点到其自身的长度为0的路径）。这是一种典型的贪心策略，就是每递增一次，经对所有可能的源点、目标点的路径都要计算，得出最优。带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。参考答案（61）C