贝尔曼-福特算法案例局限及java代码实现

贝尔曼-福特算法(Bellman–Ford algorithm )用于计算出起点到各个节点的最短距离，支持存在负权重的情况文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

• 它的原理是对图进行最多V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。
• Bellman Ford算法每次对所有的边进行松弛，每次松弛都会得到一条最短路径，所以总共需要要做的松弛操作是V - 1次。在完成这么多次松弛后如果还是可以松弛的话，那么就意味着，其中包含负环。
• 相比狄克斯特拉算法(Dijkstra algorithm),其最大优点便是Bellman–Ford支持存在负权重的情况，并且代码实现相对简单。缺点便是时间复杂度较高，达到O(V*E)，V代表顶点数，E代表边数。

可用于解决以下问题：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

• 从A出发是否存在到达各个节点的路径(有计算出值当然就可以到达)；
• 从A出发到达各个节点最短路径(时间最少、或者路径最少等)
• 图中是否存在负环路（权重之和为负数）

其思路为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

1. 初始化时将起点s到各个顶点v的距离dist(s->v)赋值为∞，dist(s->s)赋值为0
2. 后续进行最多n-1次遍历操作(n为顶点个数,上标的v输入法打不出来...),对所有的边进行松弛操作,假设:

   所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数， dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重， 若存在:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

   (dist(a) +weight(ab)) < dist(b)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

   则说明存在到b的更短的路径,s->...->a->b,更新b点的总花费为(dist(a) +weight(ab))，父节点为a

3. 遍历都结束后，若再进行一次遍历，还能得到s到某些节点更短的路径的话，则说明存在负环路

思路上与狄克斯特拉算法(Dijkstra algorithm)最大的不同是每次都是从源点s重新出发进行"松弛"更新操作，而Dijkstra则是从源点出发向外扩逐个处理相邻的节点，不会去重复处理节点，这边也可以看出Dijkstra效率相对更高点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

案例

案例一

先举个网上常见的例子介绍其实现的思路:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

如下图按Bellman–Ford算法思路获取起点A到终点的最短路径文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

由上介绍可知，由于该图顶点总数n=5个顶点，所以需要进行5-1 = 4 次的遍历更新操作，每次操作若能发现更短的路径则更新对应节点的值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

1.首先建立边对象信息,需要按从源点A出发，由近到远的顺序，不然没从源点开始的话dist(s)==∞无穷大会增加后续计算的麻烦:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

AB:-1
AC:4
BC:3
BE:2
BD:2
ED:-3
DC:5
DB:1
复制代码

1.首先列出起点A到各个节点耗费的时间:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

2.进行第一次对所有边进行的松弛操作:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

2.1统计经过1条边所能到达的节点的值AB,AC：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

AB:-1
AC:4
复制代码

2.2统计经过2条边所能到达的节点的值BC,BD,BE：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

BC:3
BE:2
BD:2
复制代码

以节点C为例,因为满足: dist(B) + weight(BC) > dist(C),即 -1 + 3 >4，所以C更新为2文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

2.3统计经过3条边所能到达的节点的值ED,DC：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

ED:-3
DC:5
DB:1
复制代码

3.尝试再进行第2次遍历，对所有边进行松弛操作，发现没有节点需要进行更新，此时便可以提前结束遍历，优化效率文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

4.由上表可知，此时便求出了源点A到各个节点的最短路径与线路文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

案例二

如下图，求出A到各节点的最短路径文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

1.该图共有节点7个，最多需要进行7-1=6次的对所有边的松弛操作文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

2.首先创建边对象:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

AB:6
AC:5
AD:5
CB:-2
DC:-2
BE:-1
CE:1
DF:-1
EG:3
FG:3
复制代码

3.进行第一次遍历松弛操作，可以得到:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

4.进行第二次遍历松弛操作，得到:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

5.进行第三次遍历松弛操作，结果并没有再次更新:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

6.此时上表边上A到各个节点的最短路径，可以通过倒序的方式得出路线文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

8.这边假设同级边对象(指的是从A出发，经过相同的边数可以到达的，比如DC,CB,BE,DF,CE经过2条边就可以到达)排序位置进行调整,并不会影响结果的正确性，但是会影响所需要的遍历的次数(不同级别):文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

比如上述,AB:6 ,AC:5,AD:5,CB:-2,DC:-2,BE:-1,CE:1,DF:-1,EG:3,FG:3 代码需要遍历3次才可以确认结果(最后一次用于确认结果不再更新)；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

AB:6，AC:5，AD:5，DC:-2，CB:-2，BE:-1，CE:1，DF:-1，EG:3，FG:3 代码需要遍历2次就可以确认结果；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

AB:6，AC:5，AD:5，BE:-1，CE:1，DF:-1，DC:-2，CB:-2，EG:3，FG:3 代码需要遍历4次就可以确认结果；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

有时候图的关系是用户输入的，对于顺序并不好强制一定是最佳的文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

局限性

案例三,存在负环路的情况

• 对案例一的图进行修改B->D为-2.使得B<->D这形成了负环路，所谓的负环路指的是环路权重之和为负数，比如上图 1 + (-2) = -1 < 0即为负环路。
• 因为负环路可以无限执行循环步骤，只要你想，可以在 B->D->B->D...这边无限循环，所以B、D的取值可以无限小， 然后当B、D取值无限小后再从B、D节点出发到达其他各个节点，都会导致其它节点的取值同样接近无限小，所以对于负环路的情况，Bellman–Ford只能判断出图存在负环路，而没有求出各个节点最短路径的意义
• Bellman–Ford求出的各个节点的最短路径后，可以再进行一次遍历，就可以判断出是否存在负环路。

例如,同案例一，对该图执行4次遍历后得到结果:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

此时结束后，所得到的结果并非是正确的最短路径，比如再进行一次遍历，更新从源点A出发，经过5条边所能到达的节点的值文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

发现此时存在可以更新的节点B，则证明图中存在了负环路。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

当没限制次数时，则无法得出各个节点的最短路径，若人为限制了遍历次数，则可以找出源点到各个节点的最短路径文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

小结

1.广度优先算法BFS主要适用于无权重向图重搜索出源点到终点的步骤最少的路径，当方向图存在权重时，不再适用文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

2.狄克斯特拉算法Dijkstra主要用于有权重的方向图中搜索出最短路径，但不适合于有负权重的情况.对于环图，个人感觉和BFS一样，标志好已处理的节点避免进入死循环，可以支持文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

3.贝尔曼-福特算法Bellman–Ford主要用于存在负权重的方向图中(没有负权重也可以用，但是效率比Dijkstra低很多)，搜索出源点到各个节点的最短路径文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

4.Bellman–Ford可以判断出图是否存在负环路，但存在负环路的情况下不支持计算出各个节点的最短路径。只需要在结束(节点数目-1)次遍历后，再执行一次遍历，若还可以更新数据则说明存在负环路文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

5.当人为限制了遍历次数后，对于负环路也可以计算出，但似乎没啥实际意义文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/4516.html

java实现

/**
 * 贝尔曼-福特算法
 * @author Administrator
 *
 */
public class BellmanFord {
	public static void main(String[] args){
		
		//创建图
		Edge ab = new Edge("A", "B", -1);
		Edge ac = new Edge("A", "C", 4);
		Edge bc = new Edge("B", "C", 3);
		Edge be = new Edge("B", "E", 2);
		Edge ed = new Edge("E", "D", -3);
		Edge dc = new Edge("D", "C", 5);
		Edge bd = new Edge("B", "D", 2);
		Edge db = new Edge("D", "B", 1);
		
		//需要按图中的步骤步数顺序建立数组，否则就是另外一幅图了，
		//从起点A出发，步骤少的排前面
		Edge[] edges = new Edge[] {ab,ac,bc,be,bd,ed,dc,db};
		
		//存放到各个节点所需要消耗的时间
		HashMap<String,Integer> costMap = new HashMap<String,Integer>();
		//到各个节点对应的父节点
		HashMap<String,String> parentMap = new HashMap<String,String>();
		
		
		//初始化各个节点所消费的，当然也可以再遍历的时候判断下是否为Null
		//i=0的时候
		costMap.put("A", 0); //源点
		costMap.put("B", Integer.MAX_VALUE);
		costMap.put("C", Integer.MAX_VALUE);
		costMap.put("D", Integer.MAX_VALUE);
		costMap.put("E", Integer.MAX_VALUE);
		
		//进行节点数n-1次循环
		for(int i =1; i< costMap.size();i++) {
			boolean hasChange = false;
			for(int j =0; j< edges.length;j++) {
				Edge edge = edges[j];
				//该边起点目前总的路径大小
				int startPointCost = costMap.get(edge.getStartPoint()) == null ? 0:costMap.get(edge.getStartPoint());
				//该边终点目前总的路径大小
				int endPointCost = costMap.get(edge.getEndPoint()) == null ? Integer.MAX_VALUE : costMap.get(edge.getEndPoint());
				//如果该边终点目前的路径大小 > 该边起点的路径大小 + 该边权重 ，说明有更短的路径了
				if(endPointCost > (startPointCost + edge.getWeight())) {
					costMap.put(edge.getEndPoint(), startPointCost + edge.getWeight());
					parentMap.put(edge.getEndPoint(), edge.getStartPoint());
					hasChange = true;
				}
			}
			if (!hasChange) {
				//经常还没达到最大遍历次数便已经求出解了，此时可以优化为提前退出循环
				break;
			}
		}
		
		//在进行一次判断是否存在负环路
		boolean hasRing = false;
		for(int j =0; j< edges.length;j++) {
			Edge edge = edges[j];
			int startPointCost = costMap.get(edge.getStartPoint()) == null ? 0:costMap.get(edge.getStartPoint());
			int endPointCost = costMap.get(edge.getEndPoint()) == null ? Integer.MAX_VALUE : costMap.get(edge.getEndPoint());
			if(endPointCost > (startPointCost + edge.getWeight())) {
				System.out.print("\n图中存在负环路，无法求解\n");
				hasRing = true;
				break;
			}
		}
		
		if(!hasRing) {
			//打印出到各个节点的最短路径
			for(String key : costMap.keySet()) {
				System.out.print("\n到目标节点"+key+"最低耗费:"+costMap.get(key));
				if(parentMap.containsKey(key)) {
					List<String> pathList = new ArrayList<String>();
					String parentKey = parentMap.get(key);
					while (parentKey!=null) {
						pathList.add(0, parentKey);
						parentKey = parentMap.get(parentKey);
					}
					pathList.add(key);
					String path="";
					for(String k:pathList) {
						path = path.equals("") ? path : path + " --> ";
						path = path +  k ;
					}
					System.out.print("，路线为"+path);
				} 
			}
		}

		
	}
	

	
	/**
	 * 	代表"一条边"的信息对象
	 * 
	 * @author Administrator
	 *
	 */
	static class Edge{
		//起点id
		private String startPoint;
		//结束点id
		private String endPoint;
		//该边的权重
		private int weight;
		public Edge(String startPoint,String endPoint,int weight) {
			this.startPoint = startPoint;
			this.endPoint = endPoint;
			this.weight = weight;
		}
		public String getStartPoint() {
			return startPoint;
		}
		
		public String getEndPoint() {
			return endPoint;
		}
		
		public int getWeight() {
			return weight;
		}
	}
}
复制代码

执行完main方法打印信息如下:
到目标节点B最低耗费:-1，路线为A --> B
到目标节点C最低耗费:2，路线为A --> B --> C
到目标节点D最低耗费:-2，路线为A --> B --> E --> D
到目标节点E最低耗费:1，路线为A --> B --> E