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] } }