🏷️ 知识点：Floyd算法

下列关于图的最短路径的叙述中，正确的是（　　）。

Ⅰ．Dijkstra 算法求单源最短路径不允许边的权为负。 Ⅱ．Dijkstra 算法求每对顶点间的最短路径的时间复杂度为 O(n²)。 Ⅲ．Floyd 算法求每对顶点间的最短路径允许边权为负，但不允许含有负权回路。

A. Ⅰ、Ⅱ和Ⅲ B. 仅Ⅰ C. Ⅰ和Ⅲ D. Ⅱ和Ⅲ

[tag_link]

正确答案：C

结论

选 C。

推导

Ⅰ正确：Dijkstra 的贪心确定性要求边权非负。Ⅱ错误：对 n 个源点分别运行 Dijkstra（朴素实现）为 O(n³)，不是 O(n²)。Ⅲ正确：Floyd 可处理负边，但负权回路使最短路无定义。

易错点

要区分“单源”与“每对顶点”；算法调用次数会改变复杂度。