Practice Day nine:Leetcode T 787

今天，我们来学习Bellman-Ford算法

Bellman-Ford是一种用于求解单源最短路径的算法，听起来和Dijkstra比较相似，但Dijkstra无法解决负权边的问题，但Bellman-Ford可以。

现在，我们来看看他是怎么做到的吧！

实现逻辑：

与Dijkstra不太一样的是，Dijkstra每个节点只处理一次，

Bellman-Ford的循环是整体的循环，所有边每次都参与循环。循环的次数取决于点的个数，若点的个数为n，则循环次数为n-1。

这个n-1是有些门道在里头的：我们知道，三个节点在寻找最短路径时，最多形成两条边，所以n个节点最多形成n-1边，虽然这个说法不大严谨，但从数学归纳的角度就是这样。

那么，当n次循环时，仍存在节点的最短距离改变，说明链接的节点存在负权环（负权环：若干个节点形成环的样子，整个环的边相加的值为负数），这时再寻找下去就没有意义了。

这里可以发现，判断停止的条件为是否还有最短距离的改变。也就是说，这个算法存在早停机制，只要存在某次循环时记录的节点最短距离不改变，那么说明已经达到最短距离了，不必再进行循环。

事实上Bellman-Ford在更新最短距离（他们管这种操作叫“松弛操作”）的逻辑上，与Dijkstra是相同的只不过Bellman-Ford是一股脑把所有边全部遍历一遍，而Dijkstra是挑着点更新。如果不太清楚是如何更新节点最小值的，建议把 Day9的Dijkstra 算法再看一遍。此处不再重复介绍。

1 选定源节点

2 从源节点开始作为当前处理节点，遍历当前处理节点所有边，所有边通通处理一遍

3 进入到下一个节点的处理，随便哪个都行，Bellman-Ford没有Dijkstra这么讲究。不过根据不同的选择，时间的消耗可能会有所不同。

4 继续遍历下一个节点，直至所有节点的所有边都被处理完成。

5 循环步骤1，2，3，4的操作，直至不再有节点最小值更新，或已经循环了n次（注意不是n-1次，而是要多循环一次，判断是否存在负权边）。

完成了对Bellman-Ford算法的理解后，我们来解决题目吧。

实际上，他就是想要找到从源节点到目的节点的最小距离。

开始动手构建程序。

这一次的官方解答不够快，我找到一个超快的方法，只是不知道作者是谁，很抱歉无法附上作者。

这个算法在提交成功后的第一名，运行时间为0ms。

来看看他是怎么实现的吧。

1 Bellman-Ford算法和Dijkstra算法的组件是一样的，作者这里使用了静态数组，因为这样会比动态数组更快，比较重要的一个原因是题目限制了输入的元素的个数不超过100个。

    int pre[110],d[110];

其中

pre用于存储上一轮松弛操作后的距离

d用于存储当前每个节点到源节点的最短距离

2 基本组件构建完成，我们现在来构建Bellman-Ford算法的基本框架

    void bellman_ford(vector<vector<int>>& flights,int u,int k)

传入的元素有：flights（该数组存储了边长及两端的节点索引）、源节点（u）、最大松弛轮数（k）

其中，这个k实际为题目要求的起始节点到目标节点之间的最少节点个数。

3 首先，对数组d（距离）进行初始化。

这个哥们初始化数组的方式比较别致

        memset(d,0x3f,sizeof(d));
        d[u]=0;

memset（）函数，的原型如下

void *memset(void *ptr, int value, size_t num);

作用是将一块连续内存的每个字节设置为指定值

• 参数：
  • ptr：指向要初始化的内存块的指针（如数组名、动态分配的内存地址）。
  • value：要设置的字节值（虽然类型是 int，但实际只使用低 8 位，即 0~255 范围）。
  • num：要设置的总字节数。

这么文绉绉的东西，想必大家不会喜欢看，我们直接来看看他在这里是怎么工作的

① 这里第一个参数，我们传入了数组d的首位地址。即从头开始初始化

② 第二个参数，传入了每一个字节的大小，0x3f是16进制的表示方式，其十进制表示为63

这里数组d的元素为int型的，我们知道，int型有四个字节，那么，执行这个操作后，数组中每一个元素的值都会变为 0x3f3f3f3f

这是由四个0x3f拼接而成的结果，十进制表示为1061109567（约 10^9）

这里的目的是用于表示一个比较大的数字，或者说成表示无穷也无妨

③第三个参数传入的是需要设置的总字节数，这里他传入了sizeof(d)，即希望处理整个数组，那么整个数组的元素都会被初始化为 0x3f3f3f3f

memset（）到此讲解完毕

我们注意到，d[u]=0，这是初始化源节点，为循环开头做准备

4接着开始循环，即进行k次松弛操作

    for (int i = 1; i <= k; ++i)

5 然后哥们又来骚操作

            memcpy(pre,d,sizeof(d));

这个操作的含义是把数组d的所有元素复制到数组pre中

让我们来看看memcpy()函数

void *memcpy(void *dest, const void *src, size_t n);

• dest：目标内存地址（如 pre 数组名，接收复制结果）。
• src：源内存地址（如 d 数组名，提供复制数据）。
• n：要复制的总字节数（sizeof(d) 计算 d 数组的总字节数

那么此处不再讲解

注意了，此时这个操作是存在于循环之内的，也就是说每一次的循环都会进行一次赋值更新

6 然后开始标记本轮是否存在更新，这是用于判断迭代是否应该停止的标志。

我们给他一个bool值来实现这个功能

            bool f=true;

7 接下来开始遍历所有的边，进行松弛操作

            for(int j=0;j<(int)flights.size();j++){
                int x=flights[j][0];
                int y=flights[j][1];
                int z=flights[j][2];
                if(pre[x]+z<d[y]) {
                    d[y]=pre[x]+z;
                    f=false;
                }

            }

对于（int）flights.size（），实际上是把size返回的size_t类型强制转化为（int）型，这其实是有必要的，因为数组flights的元素属性其实是vector<int>型，无法直接与int型的 j 进行比较，所以我们需要进行强制类型转化。

然后是比较常规的数组处理为节点操作，不再讲解

然后就是更新最小值

如果发生了更新，标记点 f 就由true变为false，循环不会 停止，除非超出了最大的松弛次数

8 当循环结束后，证明此轮松弛操作结束

现在需要判断是否存在更新操作，如果没有，循环直接终止，退出Bellman-Ford算法

            if(f){
                break;
            }

9 好了，Bellman-Ford算法已经构建完成，比之Dijkstra的构建还是简单了不少

现在，我们来处理主函数，事实上就是调用Bellman-Ford算法

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        bellman_ford(flights,src,k+1);
        return (d[dst]>=0x3f3f3f3f/2?-1:d[dst]);
    }

注意到这里传入Bellman-Ford算法的k值加上了1，这里需要分清楚：Bellman-Ford算法的k指的是最大松弛轮数，而主函数的k指的是源节点与目的节点路径中节点的个数

我们知道松弛操作是节点数目减去1，所以此处传入的k理应+1，使之变为n-1

然后是返回值，这里我们可以看见判断条件是存储的目的节点dst对应的最小值应该大于0x3f3f3f3f/2,实际上就是选取一个足够大的数。

如果判断结果成立，说明没有找到需要的路径，因为题目所给的数不可能会有这么大，所以应该返回-1，表示没有找到，否则应该返回存储的值，表示找到了。