从这篇开始我们开始介绍单源最短路径算法，他是图算法之一，我们前面说的贪心，图的遍历，动态规划都是他的基础，单源最短路径其实说的就是图中节点到节点的最短路径。就像我们使用百度地图从哪到哪一样，找出最近的距离，而单源最短路径问题不只是两点之间的路径，他有很多的变形，像单目的地最短路径问题，单节点对最短路径问题，所有节点对最短路径问题，最短路径的最优子结构问题。
在介绍这类算法之前我们先规定节点的基本属性，我们规定节点都有一个key值，key值记录的是开始节点到本节点的最小距离，每个节点也都有一个p指针指向他的前驱节点。这里我们规定一个操作叫做松弛操作，我们的算法也是最终基于这个操作的。松弛操作就是去更新key的值。
节点B的key值为8,表示从开始节点到B节点之前的最短估计距离是8，而节点A的key值3，是说从开始节点到A节点最短估计是3，当我们发现这个边时，从A到B的距离比较近，所以我们去更新B的key值，同时把B的前驱节点设置成A。这个过程就是松弛操作。
我们说的Bellman-Ford算法是最简单的算法，就是从开始节点开始循环每一条边，对他进行松弛操作。最后得到的路径就是最短路径。过程如图：
public class BellmanFord {
private int[] rank;
private int max=1000;
public boolean bellmanford(int[][]map,int start,int end){
init(map.length, start);
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map.length; j++) {
if (map[i][j]!=0) {
relex(i,j,map[i][j]);
}
}
}
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map.length; j++) {
if (rank[j]>rank[i]+map[i][j]) {
return false;
}
}
}
return true;
}
public void init(int max,int start){
rank=new int[max];
for (int i = 0; i < rank.length; i++) {
rank[i]=max;
}
rank[start]=0;
}
public void relex(int s,int e,int length){
if(rank[e]>rank[s]+length){
rank[e]=rank[s]+length;
}
}
}
友情提示：转载请注明出处【作者idlear 博客http://blog.csdn.net/idlear/article/details/19650965】