算法第4章贪心法.ppt

算法正确性证明 定理4.10 当算法进行到第 k 步时对于S 中每个结点 i dist[i] = short[i] 归纳基础 k=1, S={s}, dist[s]=short[s]=0, 命题为真. 归纳步骤 假设命题对于k 为真. 考虑 k+1步, 选择顶点v (边 {u,v}. 假若存在另一条 s-v 路径 L (绿色)最后一次出S 顶点为 x, 在这次从S 中出来后 经过V?S 第一个顶