Bellman-Ford算法详解

Bellman-Ford算法定义

Bellman-Ford算法就是求解有负边权的单源路径问题。
我觉得这篇pdf挺好理解的Bellman-ford算法

分析：

设起点 start 终点 end
那么由start 到 end ，要想找到最短路，那么它可能会经过k个点，
（k=0,1,2,3…),那么诠释这一思想的核心代码为

for(int k=1; k<=n-1; k++)//1
    for(int i=1 ;i<m ; i++)//2
        if(dis[v[i]] > dis[u[i]] + w[i])//3
            dis[v[i]]=dis[u[i]]+w[i];//4
  /*
1.n为顶点个数
2.m为边的个数
34.相当于松弛操作，u,v用来存顶点权值，w[i]就表示从u[i]到v[i]的边权是w[i]
*/
1
2
3
4
5
6
7
8

公式说明,递推
dis1[s]=edge[s][t];//直达边，即是直接连接s到t的那条边
disk[s]=min(disk-1[s],min(disk-1[j]+edge[j][s])//经过k-1个点后，最短路径

图解Bellman-ford算法

它解决的是负权边的问题，同时保证没有形成负权边回路，它最多进行n-1次松弛
操作，为了保证不形成回路
1

针对上图，我们设置1号点为起点，2，3，4，5为终点
那么首先起始图

进入松弛操作前，初始化所有的值为无穷大+∞

松弛操作后

           1    2    3    4    5
dis1       0    3   -5    ∞    ∞
dis2       0    3   -5    1    -4
dis3       0    2   -5   -1    -4
dis4       0    0   -5   -1    -4
 因为本题共有5个点，所以最多进行5-1=4次松弛操作，得到最小解
1
2
3
4
5