一、贪婪算法简介
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
通过局部的最优解去合成最后的最优解。
二、贪婪算法求解最短路径算法描述：
准备：建立两个数组，分别存放当前条件下的最优解和已访问节点
1、初始化：将最优解置为无穷大，已访问节点数组置空，将起点的最优解置为0，并调为已访问
2、寻找最优解：遍历最优解数组，找出最优解，并将该点放置到已访问队列中
3、更新最优解：从2中的最优解出发，对最优解数组进行更新（如果从当前最优解出发到各个顶点的距离更优，则更新）
4、重复2.3两步，直至待访问队列为空
算法结束。
三、图解
四、实现代码：
噗，代码不是我的，直接copy教案了
[cpp] view plain template <class Weight, int graph_size> void Digraph<Weight, graph_size> :: set_distances(Vertex source, Weight distance[]) const /* Post: The array distance gives the minimal path weight from vertex source to each vertex of the Digraph. */ { Vertex v, w; bool found[graph_size]; // Vertices found in S for (v = 0; v < count; v++) { found[v] = false; distance[v] = adjacency[source][v]; } found[source] = true; // Initialize with vertex source alone in the set S. distance[source] = 0; for (int i = 0; i < count; i++) { // Add one vertex v to S on each pass. Weight min = infinity; for (w = 0; w < count; w++) if (!found[w]) if (distance[w] < min) { v = w; min = distance[w]; } found[v] = true; for (w = 0; w < count; w++) if (!found[w]) if (min + adjacency[v][w] < distance[w]) distance[w] = min + adjacency[v][w]; } }
