本文共 764 字，大约阅读时间需要 2 分钟。

Bellman-Ford算法定义

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
   
     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]*/
   

公式说明,递推

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号点为起点，2，3，4，5为终点

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

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

转载地址：http://ydwzi.baihongyu.com/