贪心算法——最短路径算法

内容简介：塔里木大学课程设计贪心算法——Dijkstra 算法一、贪心算法简介顾名思义，贪心算法总是作出在当前看来是最好的选择，就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心算法具有两个重要的性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来的所作的选择，也不依赖于子问题的解。对于一个具体问题，要确定他是否具有贪心选择性质，我们必须证明每一步所做的贪心...