单源最短路分析及算法实现

单源最短路分析及算法实现

最短路径的理解性解释:Va 到 Vb 的最短路的意义是 在一个带权图中,从节点Va到节点Vb的权值总和最小的路径 就是Va 到 Vb的最短路,这个权值可以是距离 时间 等各种量

理解最短路径首先要理解什么是最优子结构  最优子结构是在各种动态规划贪心以及最短路算法中都很关键的一个结构。  最优子结构的意思就是,问题局部的最优解包含在全局的最优解之中,这样才能把问题分成较小的问题先进行处理。

可以通过反证法证明,最短路问题是最优子结构,方法详见 算法导论第三版 P375

在计算最短路之前,还要考虑一个特殊情况,如果在图中存在负权值的边,就可能有一种比较特殊的情况了: 如果 图中存在负权值的边的话但不存在和的权值为负的环,那么 每一个路径的最短距离都可以精确求出,没有问题,不过,如果图中存在和为负权值的环,最短路就没有意义了  因为 总可以通过经过完整的一次环,来得到更小的一个权值 ,理论上 这个最短路径的大小为  -∞

求最短路的某些算法假设输入的边权值全为非负 如 Dijkstra算法,而还有一些算法只要没有负权值的环就可以 如 Bellman Ford算法 ,如果存在负权值的环的环也可以通过算法报告出来

先试试如何应用这个算法,再继续研究算法的正确性;                             //参考POJ 1860

 

Leave a Reply

Your email address will not be published. Required fields are marked *

eighteen − 18 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.