单源最短路径 BellmanFord算法,BellmanFord算法,BellmanFord算法能够在一般情况下，解决单源最短路径问题。允许图中出现权为负数的边。该算法还会返回一个布尔值。如果布尔值为false，表示途中存在从源点可达的权为负的回路. 首先介绍松弛计算。如下图：,松弛计算之前，点B的值是8，但是点A的值加上边上的权重2，得到5，比点B的值（8）小，所以，点B的值减小为5。这个过程的意义是，找到了一条通向B点更短的路线，且该路线是先经过点A，然后通过权重为2的边，到达点B。,BellmanFord算法三个部分,第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。 第二，进行循环，循环下标为从1到n1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。 第三，遍历途中所有的边（edge（u，v），判断是否存在这样情况： d（v） d (u) + w(u,v) 则返回false，表示途中存在从源点可达的权为负的回路。,之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。 考虑如下的图：,在回过来看一下bellmanford算法的第三部分，遍历所有边，检查是否存在d（v） d (u) + w(u,v)。因为第二部分循环的次数是定长的，所以如果存在无法收敛的情况，则肯定能够在第三部分中检查出来。比如此时，点A的值为2，点B的值为5，边AB的权重为5，5 -2 + 5. 检查出来这条边没有收敛。所以，BellmanFord算法可以解决图中有权为负数的边的单源最短路径问。,