题8

题8

题目

下列关于图的最短路径的相关叙述中, 正确的是 ( ).
I. Dijkstra 算法求单源最短路径不允许边的权为负
II. Dijkstra 算法求每对顶点间的最短路径的时间复杂度是
III. Floyd 算法求每对顶点间的最短路径允许边的权为负, 但不允许含有负边的回路
A. I、II 和 III
B. 仅 I
C. I 和 III
D. II 和 III

分析

解

C
在负权图中, Dijkstra 算法既不能保证每次选出的顶点都是真正的最近顶点, 又不能保证已确定的最短路径不再被改变, 因此 Dijkstra 算法不允许边的权为负, I 正确。
求每对顶点间的最短路径需要调用 Dijkstra 算法 次,时间复杂度为 ,II 错误。
Floyd 算法求每对顶点间的最短路径允许有负边存在, 但不允许有包含负边组成的回路, III 正确。