图论------贝尔曼-福德（Bellman-Ford）算法

算法概述：

        Bellman-Ford算法核心代码如下

        for(int i = 1;i<=n-1;i++)

                for(int j = 1;j<=m;j++)

                        if(dic[v[j]]> dic[u[j]] + w[j]]

                                dic[v[j]] = dic[u[j]] + w[j];

        首先我们要了解一个点就是我们这次不再使用邻接矩阵来存储图的信息，而是定义三个一维数组来存储图的信息。

        首先定义 u[n] 来存储边的起点，v[n]来存储边的终点，w[n]来存储边的长（权重）。

    例如存储如下元素

          4 4
        1 2 3
        2 4 7
        3 4 5
        3 1 3

---

        和Dijkstra算法一样，这段代码也是求单源最短路径，所以我们同样也要定义一个dic[n]数组来存储所有点到1的最短距离。注意，这里因为使用的并非邻接矩阵，所以初始化dic时默认除了dic[1] = 0以外，暂时全部看作不连通，也就是假设以以上数据为例，dic内容要初始化为

【0 ，inf, inf, inf】,其中inf看作无穷大，表示不通。

        那么我们再来看核心代码的最后两句。

        

                if(dic[v[j]]> dic[u[j]] + w[j]]

                                dic[v[j]] = dic[u[j]] + w[j];

        dic[v[j]]的值是1 到 v[j]这个点的值， dic[u[j]] 是 1 到 u[j] 这个点的值 ， w[j] 是 u[j] 到 v[j] 的值，意思是如果如果 1 通过 1 -> u[j] -> v[j] 这条路比 1 -> v[j] 值小的话，更新dic[v[j]]的值。也就是通过u[j] ->v[j] 这条边进行松弛来优化路径。

        初始化示意图如下：

        

       

for(int i = 1;i<=n-1;i++)

                for(int j = 1;j<=m;j++)

                        if(dic[v[j]]> dic[u[j]] + w[j]]

                                dic[v[j]] = dic[u[j]] + w[j];

当第一轮循环时:

当先通过 j = 1 通过第一条边进行优化时， if(dic[ 2 ] > dic[ 1 ] + 3]，发现dic[2 ] 需优化，然后

重置 dic[2] = dic[1]+3 = 3。

当 j = 2 时 通过第二条边进行优化时， if(dic[ 4 ] > dic[ 2 ] + 7],发现dic[4] 可以优化，然后

重置 dic[ 4 ] = dic[ 2 ] + 7 = 3+7 = 10。

当 j = 3时，通过第三条边进行优化时，if(dic[ 4 ] > dic[ 3 ] + 5]，发现dic[4]无法优化，因为

dic[ 4 ] = 10 < dic[ 3 ] + 5  =inf + 5。

当 j = 4 时 通过第四条边进行优化时， if(dic[ 1 ] > dic[ 3 ] + 3],发现dic[1]无法优化，因为

dic[ 1 ] = 0 < dic[ 3 ] + 3  =inf + 3。

最后经过一轮松弛后得到 dic = [0, 3, inf ,10];

---

        当 i= 2 进行第二轮松弛时，

        

当先通过 j = 1 通过第一条边进行优化时， if(dic[ 2 ] > dic[ 1 ] + 3]，发现dic[2 ] 无需优化，因为 dic[2] = dic[1]+3 = 3。

当 j = 2 时 通过第二条边进行优化时， if(dic[ 4 ] > dic[ 2 ] + 7],发现dic[4] 无需优化

当 j = 3时，通过第三条边进行优化时，if(dic[ 4 ] > dic[ 3 ] + 5]，发现dic[4]无需优化

当 j = 4 时 通过第四条边进行优化时， if(dic[ 1 ] > dic[ 3 ] + 3],发现dic[1]无需优化

这样我们就完成了这组数据，因为这是构建的有向图，所以1 才无法到达 3.

既然很清晰流程了 我再丢给大家一组数据：

5 7
1 2 8
1 3 1
1 4 2
3 4 2
2 4 3
3 5 3
4 5 3

        现在请找到一张草稿纸来试着执行刚才所讲的流程。

具体代码：

        

#include<stdio.h>
int main(void)
{
    int u[10], v[10], w[10];
    int n, m, inf = 99999999;
    int dic[10] = { 0 };

    scanf_s("%d%d", &n, &m);

    for (int i = 1; i <= m; i++)
        scanf_s("%d%d%d", &u[i], &v[i], &w[i]);//存储边的信息

    for (int i = 2; i <= n; i++)
        dic[i] = inf;//初始化1 的单源最短路径值。

//核心代码

    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= m; j++)
            if (dic[v[j]] > dic[u[j]] + w[j])
                dic[v[j]] = dic[u[j]] + w[j];

    for (int i = 1; i <= n; i++)
        printf("%d ", dic[i]);//输出结果
}

注意事项：

        最外层代码循环n-1次的原因是，n 个顶点，1到任何顶点的最多经过n-1个顶点。每一轮松弛循环如果没有完成单源最短路径的最终结果，都至少会有一次松弛。

        细心的同学可能会发现我们刚才使用的数据：

   5 7
1 2 8
1 3 1
1 4 2
3 4 2
2 4 3
3 5 3
4 5 3

        是上一篇文章的内容，在上一篇中结果是：0 5 1 2 4 。

而在这里答案是：0 8 1 2 4。

        那么为什么会造成这种影响呢，因为我们使用的这段代码是处理有向图的，而在上一篇文章中是处理无向图的，那么有没有什么办法来改进这段代码使代码能够处理无向图呢？答案当然是可以的，而且十分简单。

        聪明的同学注意到数据

          4 4
        1 2 3
        2 4 7
        3 4 5
        3 1 3

        在第二轮就能发现没有优化证明已经得出结果，每必要进行n-1轮循环，那么大家思考下，怎么提前退出循环呢？

课后作业：

        改进这段代码使代码能够处理无向图。

        如何证明达到最优解提前退出循环。

        明天带来答案。