Bellman-Ford算法教学PPT

    Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。

Bellman-Ford算法的流程如下：
   给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，Bellman－Ford算法可以大致分为三个部分:

   第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。

   第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

   第三，遍历图中所有的边（edge（u，v）），判断是否存在这样情况：
       d（v） > d (u) + w(u,v)
   则返回false，表示途中存在从源点可达的权为负的回路。

    之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则应为无法收敛而导致不能求出最短路径。

    两者都用到了一个“松弛计算”的方法，也就是在遍历图的顶点和边的过程中修改距离数组的值，从而来找出最短路径。

下面的课件很好的讲解了Bellman-Ford算法。

精彩内容：