算法起步之Bellman-Ford算法

原文: 算法起步之Bellman-Ford算法

           从这篇开始我们开始介绍单源最短路径算法,他是图算法之一,我们前面说的贪心,图的遍历,动态规划都是他的基础,单源最短路径其实说的就是图中节点到节点的最短路径。就像我们使用百度地图从哪到哪一样,找出最近的距离,而单源最短路径问题不只是两点之间的路径,他有很多的变形,像单目的地最短路径问题,单节点对最短路径问题,所有节点对最短路径问题,最短路径的最优子结构问题。

        在介绍这类算法之前我们先规定节点的基本属性,我们规定节点都有一个key值,key值记录的是开始节点到本节点的最小距离,每个节点也都有一个p指针指向他的前驱节点。这里我们规定一个操作叫做松弛操作,我们的算法也是最终基于这个操作的。松弛操作就是去更新key的值。

算法起步之Bellman-Ford算法

        节点B的key值为8,表示从开始节点到B节点之前的最短估计距离是8,而节点A的key值3,是说从开始节点到A节点最短估计是3,当我们发现这个边时,从A到B的距离比较近,所以我们去更新B的key值,同时把B的前驱节点设置成A。这个过程就是松弛操作。

        我们说的Bellman-Ford算法是最简单的算法,就是从开始节点开始循环每一条边,对他进行松弛操作。最后得到的路径就是最短路径。过程如图:

算法起步之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】

上一篇:算法学习之路|A+B Format


下一篇:iOS中 按钮和标题完美各种排列/完美教程 韩俊强的博客