图论------贝尔曼-福德（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, &v, &w);//存储边的信息
    for (int i = 2; i <= n; i++)
        dic = 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);//输出结果
}

留意事项：

        最外层代码循环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轮循环，那么各人思索下，怎么提前退出循环呢？
课后作业：

        改进这段代码使代码可以或许处理惩罚无向图。
        怎样证实到达最优解提前退出循环。
        来日诰日带来答案。



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金