单源最短路分析及算法实现
[ ]The content is recoverd from Wordpress Blog, for more details please check HERE
September 20, 2014
最短路径的理解性解释：Va 到 Vb 的最短路的意义是 在一个带权图中，从节点Va到节点Vb的权值总和最小的路径 就是Va 到 Vb的最短路，这个权值可以是距离 时间 等各种量
理解最短路径首先要理解什么是最优子结构 最优子结构是在各种动态规划，贪心以及最短路算法中都很关键的一个结构。 最优子结构的意思就是，问题局部的最优解包含在全局的最优解之中，这样才能把问题分成较小的问题先进行处理。
可以通过反证法证明，最短路问题是最优子结构，方法详见 算法导论第三版 P375
在计算最短路之前，还要考虑一个特殊情况，如果在图中存在负权值的边，就可能有一种比较特殊的情况了： 如果 图中存在负权值的边的话但不存在和的权值为负的环，那么 每一个路径的最短距离都可以精确求出，没有问题，不过，如果图中存在和为负权值的环，最短路就没有意义了 因为 总可以通过经过完整的一次环，来得到更小的一个权值 ，理论上 这个最短路径的大小为 -∞
求最短路的某些算法假设输入的边权值全为非负 如 Dijkstra算法，而还有一些算法只要没有负权值的环就可以 如 Bellman Ford算法 ，如果存在负权值的环的环也可以通过算法报告出来
先试试如何应用这个算法，再继续研究算法的正确性； //参考POJ 1860
ACM Algorithm, GraphTheory C. Linux, kernel, Laravel, PHP, Python, Shell, Web, wine
Historical Comments
Post navigation ————— NEXT
POJ 1860 Currency Exchange PREVIOUS POJ 题目分类整理 [转]