🍋1.什么是bellman-ford算法？

       首先我们从百度百科来了解一下bellman-ford

           贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。

bellman-ford使用场景：

       1.bellman-ford适用于解决带有负权边的单源最短路问题。

       2.bellman-ford可用于判断图中是否存在负权环（但我们一般不使用该算法进行判断）

       3.bellman-ford可用于有边数限制的情况(使用bellman-ford最重要的标志)

🍐 2.bellman-ford和Dijkstra有什么区别？

      首先从适用场景上来说：Dijkstra值只能用于只有正权边的单源最短路问题，而bellman-ford算法不仅能适用于带正权边而且适用于带负权边的情况。而且当题目对边数有限制要求时，别犹豫，一定要使用bellman-ford算法。

      其次我们最关心的应该是算法的时间复杂度，朴素版的Dijkstra的时间复杂度是O（n^2），n是点的数量（和边无关系），而堆优化版的Dijkstra的时间复杂度为O（mlongn），m是边数，n是点的数量。而bellman-ford算法的时间复杂度是O（mn），这个复杂度还是比较高的。所以一般使用bellman-ford算法时，一定要注意题目中给定的点数和边数，如果不是非常明显具有使用bellman-ford的提示，对于bellman-ford算法一定要慎用。

🍍 3.什么是松弛操作？

          这个词语会经常出现在每一个最短路算法中，大家也会经常看见。上篇Dijkstra中我并没有认真的说清楚它的意思，只是有简略的语言带过了一下，这篇文章我们来细讲一下。

         首先，松弛操作是Dijkstra和bellman-ford能找到最短路径的核心操作，两种算法都是基于它来实现的。          

        我们以上面的简图为例，首先提高松弛操作那就一定要提到dist[]数组，它是保存从起点到每个点的最短距离，比如dist[j]表示从起点i到j的最短距离，更详细的解释在Dijkstra说明了，不太明白的建议去看看。

       上面的图中，A是起点，C是终点。我们在对B点做松弛操作时，要去遍历所有除去起点和本身的其他点，当然这个图里只有C点，然后判断dist[c]是否大于dist[b]+g[b][c]（此处的g数组是邻接矩阵数组，g[i][j]表示i点到j点这条边的距离）。上图中dist[c]本来是25，dist[b]是5，而g[b][c]是15，因为dist[c]>dist[b]+g[b][c]，所以我们将dist[c]更新为20，也就表示我们找到了一条到达C点更近的线路，这就是松弛操作。

       其实松弛操作非常好理解，就是判断，在已有的到达某点X的最短线路中，能否通过其他的点去更新这个最短路径，核心操作就是判断dist[c]是否大于dist[b]+g[b][c]。

🍅4.bellman-ford的基本思路和注意事项

1.图的存边方式

          bellman-ford算法是基于边来进行遍历迭代的，所以我们需要保存去保存每条边和它的权值，我们可以才取最简单的方式，也就是结构体存边即可，Java用一个Node类表示，属性有int类型的a，b，w。表示为有一条从a到b权值为w的边。

class Node{
    int a,b,w;
    public Node(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
    }
}

2.for循环n次，每次遍历所有的边（所以时间复杂度是O（nm））

       算法流程只需要循环n次，每次用所有的边去进行松弛操作即可，bellman-ford就是如此的简单，模板也非常容易记忆。只要知道松弛操作是如何，这个算法就是一个非常简单算法，因为它本身就是一个偏暴力的算法，所以时间复杂度比较高。

3.对于图中可能存在负权回路的情况

       如图这种情况，如果计算从A点到E点的距离，由于BCD是形成了一个负环，每循环一次权值就-1，所以如果循环无数圈就是负无穷，结果得到到E的最短距离是负无穷。但是大家不要担心，一般题目都不会出现这种情况，会说明，只不过大家要知道有这种情况产生。

       那是不是有负环就一定不能得到解呢？

       那也不一定，如果负环在我们走的路径上，那就会产生影响，否则是不会影响我们的最短路径的。

4.如何去利用bellman-ford解决有边数限制的情况

       其实我们前面就已经提过，在bellman-ford中我们先需要循环n次，代表了走了n条边的最短路径，我们现在限制只能走k条边，所以我们只需要让循环只走k次，以此来限制走的边数即可，其余的代码不需要改变。

5.backup作为备份数组的必要性

       在bellman-ford和Dijkstra算法中，都有dist数组记录最短路径，而bellman-ford中还有一个 backup 数组，它作为的是我们的备份数组。它的存在为的是防止前面的边松弛影响到后面的边的松弛操作。我们每次松弛的的时候利用的是上一次的结果来。

      比如在如图，边数限制为1的情况下，从1到3的最短路径应该为3。初始的时候dist[]数组应该是被初始化为正无穷的。如果此时我们对1~2这边进行操作以后使得dist[2]=1以后，再松弛2~3这条边的时候，就会导致dist[3]变成了2，也就没有无法保证只有1条边了。

      说白了其实就是bellman-ford的dist数组并不是实时更新，每一次循环m次都用的是上一次循环的dist数组，所以我们用backup备份上一次的dist数组。