在图6-9中,由点O(0,0)到点P(5,6)的最短路径共有(63)条。
A.126
B.128
C.252
D.256
第1题:
n个顶点c条边的图求解最短路径的Floyd算法的时间复杂度为()。
A.O(n)
B.O(n+c)
C.O(n*n)
D.O(n*n*n)
第2题:
管线设计问题中对于中间某个点i,找出从点A到点i的最短路和点i到点E的最短路,两个最短路合起来就一定是点A到点E的最短路。
第3题:
n个顶点c条边的图求解最短路径的Floyd算法的时间复杂度为
A.O(n)
B.O(n+c)
C.O(n*n)
D.O(n*n*n)
第4题:
3、对于有n个顶点e条边的有向图,求最短路径的Dijkstra算法的时间复杂度为()。
A.O(n)
B.O(n+e)
C.O(ne)
D.O(n2)
第5题:
对于给定的有权无向图G,下列哪个说法是正确的()
A.G的最小生成树中,任意一对顶点间的路径必是它们在G中的最短路径
B.设顶点V到W的最短路径为P。若我们将G中每条边的权重都加1,则P一定仍然是V到W的最短路径
C.单源最短路问题可以用O(∣E∣+∣V∣)的时间解决
D.以上都不对