算法 第9章 贪婪技术(李静).ppt

贪婪技术 背包问题 Prim算法是否能产生一个最优解 最短路径的另一个例子 在第i次迭代开始以前该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径他们构成了一棵子树Ti 和Ti的顶点相邻的顶点集合成为边缘顶点以它们为候选对象选出下一个最接近起点的顶点 对于每一个边缘顶点u该算法求出它到最近的树中顶点v的距离 给每个顶点附加两个标记 数字标记d指出目前为止该算法求出的从起点到该顶点间最短