Bellman-Ford最短路径算法解决的是单源最短路径问题，从源点到其他各个顶点的最短路径。现在有一个图G,包含n个顶点，m条边。有三个数组u、v、w，其长度都为m+1,这三个数组用来保存m条边的信息，对于第i(1<=i<=m)条边，u[i]表示其起点，v[i]表示其终点，w[i]表示从u[i]到v[i]的权值。
Bellman-Ford的思路是从边出发。有一个结论，含有n个顶点的图中任意两点的最短路径最多只会包含n-1条边。假设源点为a，b为其他顶点中的一个顶点。假设数组dis表示各个顶点到源点的距离，源点到源点的距离为0，初始值为dis[a]=0，dis[b]= ∞ 则a到其他各顶点的最短路径从包含一条边到包含n-1条边的代码如下：
for(int i = 1;i <= n-1;i++) {
for(int j = 1;j <= m;j++) {
if (dis[v[j]] > dis[u[j]] + w[j]) {
dis[v[j]] = dis[u[j]] + w[j]
}
}
}代码
if (dis[v[j]] > dis[u[j]] + w[j]) {
dis[v[j]] = dis[u[j]] + w[j]
}表示如果点v[j]到源点的距离大于点u[j]到源点的距离加上w[j]，那么点v[j]的距离就可以用点u[j]的距离加上w[j]来代替。这个操作叫做松弛。对于其他各点到源点的距离，用每一条边来进行松弛操作，则会逐步得到最短距离。重复n-1次得到最终结果
