关于最短路算法(迪杰斯屈拉算法)，下列论述正确的有( )。
A: 算法可以解决有向图中指定两顶点间的最短通路问题。
B: 算法的时间复杂度是O（n3）。
C: 算法结束时的顶点标号就是到达该顶点的最短通路长度。
D: 算法的每次运行可以求出任意顶点对间的最短通路长度。
A: 算法可以解决有向图中指定两顶点间的最短通路问题。
B: 算法的时间复杂度是O（n3）。
C: 算法结束时的顶点标号就是到达该顶点的最短通路长度。
D: 算法的每次运行可以求出任意顶点对间的最短通路长度。
A,C
举一反三
- 扩展求加权简单连通图中两个顶点之间最短通路的迪克斯特拉算法，以便求出顶点[tex=0.571x0.786]c59+3vo0/Vn/FvNRhDRu5g==[/tex]与图中其余每个顶点之间的最短通路的长度。
- 使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为________。
- 使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为________。 A: O((log2)^2) B: O(nlogn) C: n^3 D: n^2
- 中国大学MOOC: 使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为________。
- 可用Dijkstra算法求解任意两顶点间的最短路径问题。
内容
- 0
使用弗洛伊德算法，求任意2个顶点的最短路径，该算法的时间复杂度为________。
- 1
可用Dijkstra算法求解任意两顶点间的最短路径问题。 A: 正确 B: 错误
- 2
单源最短路径算法可用于求得图中任意两个顶点间的最短路径
- 3
下列对于最短路径算法的阐述，正确的是（ ）。Dijkstra算法是求从指定源点到其余各顶点的最短路径算法，算法要求边上权不能为负。利用Dijkstra算法求每一对不同顶点对之间的最短路径的算法时间复杂度为O(n^3)。Floyd算法是求解每一对不同顶点对之间的最短路径的算法，算法中允许弧上的权为负。 A: I，II，III B: II，III C: I D: III
- 4
利用Dijkstra算法求所有不同顶点对的最短路径的算法时间复杂度为( )。 A: O(n) B: O(n2) C: O(logn) D: O(n3)