题目内容
(请给出正确答案)
[主观题]
使用Floyd算法计算图8-30的各对顶点之间的最短路径。
请帮忙给出正确答案和分析,谢谢!
答案
查看答案
请帮忙给出正确答案和分析,谢谢!
第2题
第3题
求最短路径的FLOYD算法的时间复杂度为(16)。
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
第4题
下面哪些使用的不是贪心算法()
A.单源最短路径中的Dijkstra算法
B.最小生成树的Prim算法
C.最小生成树的Kruskal算法
D.计算每对顶点最短路径的Floyd-Warshall算法
第5题
已知一个图如图8-42(b)所示,依据Dijkstra算法求从顶点l到其余各顶点的最短路径的顺序应是()。
A、2,5,4,6,3
B、2 , 5,3,4,6
C、2,3,5,4,6
D、5,4,6,3,2
第6题
为,这里的路径长度是指路径中所含的边数。编写一个算法求T的直径、并分析算法的时间复杂度。
第9题
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径,假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点“为初始顶点;②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;③重复步骤②,直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行,请证明之,否则,请举例说明。【2009年全国试题41(10分)】