贪婪算法（Greedy algorithm）

1、基础

定义：贪婪算法分阶段地工作，在每一阶段，选择在当前最好的决策，不考虑将来的后果。所以一般只能得到局部最优而不是全局最优。

贪婪算法：

Dijkstra 算法Prim 算法Kruskal 算法哈夫曼编码

2、Dijkstra 算法

原理：

把起点的 dv 初始化为0，其它的为∞，并设置所有点的最短路径都是不知道的声明起点最短路径已知，根据权值更新邻接点的 dv 和 pv从未知最短路径的点中，选择 dv 最小的值，更新邻接点的 dv 和 pv重复步骤 3 直到所有点的最短路径都已知

伪代码：

3、哈夫曼编码

原理：一棵树的权等于它的树叶出现的频率的和，哈夫曼编码就是要使得树的权最小。每一个元素都可以看成是一棵树，任意选取最小权的两颗树T1和T2，组合成新的树。不断组合，直到所有的节点都被包含在一棵树中。

……….