CSP-S 2019 第一轮 第13题：以下哪些算法不属于贪心算法？（)

题目

以下哪些算法不属于贪心算法？（）

选项

• A. Dijkstra 算法
• B. Floyd 算法
• C. Prim 算法
• D. Kruskal 算法

答案

B

题解

答案是 B. Floyd 算法。

判断是否属于贪心算法，关键看它是否通过每一步的局部最优选择来求解。

• A. Dijkstra 算法：每次选取尚未确定最短距离、且当前距离最小的顶点，属于贪心算法（要求边权非负）。
• B. Floyd 算法：通过枚举允许经过的中间顶点，不断更新任意两点间的最短距离，属于动态规划。
• C. Prim 算法：每次选择连接当前生成树与树外顶点的最小权边，属于贪心算法。
• D. Kruskal 算法：按边权从小到大选择不会形成环的边，属于贪心算法。

记忆：Dijkstra、Prim、Kruskal 是贪心，Floyd 是动态规划。