哪些算法不属于贪心算法

2021年8月26日 | 分类: 【编程】

【题目】

以下哪些算法不属于贪心算法?( )

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

【解析】

用来查找最小生成树的算法,除了Kruskal算法,还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。

参考:https://code.weblog.org/bc3e0f5bfbaf0c70

Floyd算法属于动态规划,枚举所有情况。

弗洛伊德算法(Floyd-Warshall)又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法(多源最短路径)。

特点:每一次从邻接矩阵选取一个顶点k,然后再去矩阵中遍历两个顶点i,j,看看是i→j的路径短,还是i→k→j的路径短,就是完全的暴力算法。

参考:https://www.cnblogs.com/luoyoucode/p/12919601.html
参考:https://baike.baidu.com/item/Floyd%E7%AE%97%E6%B3%95/291990

答案选择:B