贝尔曼-福特算法极限情况及java代码实现

贝尔曼-福特算法（Bellman–Ford算法）用于计算从起点到每个节点的最短距离，并支持存在‘负权重

• 其概念就是画一个图做大部分的V-1平滑工作来得到最短路径。 Dijkstra算法的优点是边权可以为负且实现简单。缺点是时间复杂度太高，可达O(VE)。然而，该算法可以执行许多优化来提高性能。
• 贝尔曼福特算法稳定了所有的边，每次松弛都会得到一条最短路径，所以总共需要的松弛功是V - 1倍。如果多次休假后仍能放松，则说明出现了不良循环。
• 与Dijkstra算法（Dijkstra's Algorithm）相比，主要优点是Bellman-Ford支持负权值的存在，而且代码实现简单。缺点是时间复杂度较高，达到O(V*E)，其中V表示顶点数，E表示边数。？至少等）
• 图中是否存在负环（权重之和为负数）

思路是：

1. 开始时，给出区间（s->v）从起始点s到每个顶点v为∞，dist(s->s)给定值为0
2. ，然后进行最大n-1操作（n为顶点数，上标插入方法v...)，并且所有边缘都是光滑的。用法、假设：

   所谓休息，以边ab为例，而dist(a)表示从s点到达a点的总时间，dist(b)表示到a点的总时间长度从点s到达点b，weight(ab)表示边ab的权重。如果：

   (dist(a) +weight(ab)) ，则表示有一条更短的路径到达b，s->。 ..->a->b，更新b点的总成本为(dist(a) +weight(ab))，父节点为a

3. 行程结束后，如果再进行一次遍历，可以仍然得到 s 如果到某些节点有更短的路径，说明存在坏循环 它又在源点 s 处进行“fun”更新操作，Dijkstra 从源点开始，将相邻节点逐个旋转，无需多次处理。这里也可以看出Dijkstra的效率稍微高一些。

   案例

   案例1

   首先我们举一个网上的典型例子来介绍一下它的应用思路：

   如下图，最短点。根据贝尔曼-福特算法可以得到。如果每个任务中找到更短的路径，则更新相应节点

   1 的值。首先设置边缘信息需要从源点A开始，由近到远对齐。否则，如果dist(s)==Infinite不从原点开始，就会增加下面计算的难度：

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

   1。首先列出起点 A 到达各个节点所花费的时间：

   父节点	节点	初始化
   A❀‿♶❀❀♿ B	∞
   ..	C	∞
   ..	D‿ E	∞

   2.第一次下班休假。全面：

   2.1 计算边1上可达节点的AB、AC值：

   AB:-1
   AC:4
   复制代码

   父节点	节点 ”A	0
   A	B	-1
   A	C	4
   … ..	E	∞

   2.2 计算边 2 上的可达节点数 值 BC、BD 、BE：

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

   父节点	节点	成本
   A	4
   A	4
   B - 1
   B	C	2
   B D	1
   B	E	2
   B	D	1
   B	E	2
   B	D	1
   B	E	1

   例如：

   1

   节点C（但权重不是相同）（C），即-1 + 3 >4，所以C会更新为2

   2.3边3上可达节点的ED、DC值统计：

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

   父节点	节点	消费者
   A	A A	B .D	-2
   B	E	1

   3。再次尝试遍历，获取所有边，发现没有节点需要更新。此时，您可以提前结束行军，提高

   父节点	节点	消耗
   A❀♿A❀♿ B 的性能	-1
   B	C	2
   E	D	-2
   B	3

   。从上表可以看出，这个Search什么时候需要从A点到各节点

   情况2

   如下图所示，求从A点到各节点

   1的最短路径。该图中有7个节点，所有边

   2最多平滑7-1=6次。首先，创建边缘对象：

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

   3。执行第一个接地操作，您可以：

   父节点	节点	成本
   A	3

   A❀♿

   • B3D C3AD5BE2DF ❀E ❀ 进行第二次接地动作，得到： 0 节点。父节点 节点 成本AA1

     AB

     1DC A D5B E0DF4E.4进行第三次遍历操作，结果不再更新：

     父节点	节点‍ F	1

     F

     1

     F

     3

     6. 现在，在地面上 从 A 到每个节点的最短路径可能以相反的顺序 路线在

     8 处可用。这里我们假设边是同一级别的（指从A可以到达的边数相同的，如DC、CB、BE、DF、CE可以通过2条边））编辑位置分类为。不影响答案的正确性，但会影响需要遍历的次数（不同级别）：

     例如上图，AB：6，AC：5，AD：5，CB：- 2，DC：- 2 ,BE:-1,CE:1,DF:-1,EG:3,FG:3 代码需要运行3次才能确认答案（最后一次用于检查答案，不更新）；

     AB:6, AC:5, AD:5, DC:-2, CB:-2, BE:-1, CE:1, DF:-1, EG:3, FG:3 遍历 2 可以一次检查结果；

     AB:6, AC:5, AD:5, BE:-1, CE:1, DF:-1, DC:-2, CB:-2, EG:3, FG:3 做 4 次验证结果；

     有时候图的关系是由用户输入的，想要强制排序为情况1 B->D 到-2 的最佳图并不容易。使 BD 成为循环，所谓负循环，是指循环的值之和为负数。比如上图中 1 + (-2) = -1

   • 因为负循环可以执行无限步，仔细想想，可以无限循环 -设置为 B-> D->B->D...，所以B和D的值可以无限小，然后从节点B和D开始，当B和D小时，B和D的值就很小。到达任意其他节点将使其他节点的值等于无穷小。因此，在负环的情况下，Bellman-Ford只能判断图中存在负环，但不具有寻找每个节点最短路径的意义
   • 当Bellman-Ford找到最短路径时。在每个节点，可以重传以确定是否存在恶性循环。

   例如，与情况1类似，对图进行4次遍历后，得到结果：

   父节点	节点	成本
   A	A	0
   A	B	-2	A->B->B->B >B > C
   E	D	-4 A->B->D-B ->D
   B
   B♽	4
   >D->B-> > E 这个时间到了，结果就不是最短路径了。例如，再次遍历，将从源点A获取的节点 父节点 节点的值更新为5条边。 消耗 执行规则 A A 0 A B 1 A	A	0
   A	B	1

   A

   A B1

   >-B->B->B->B->B-> >D->B

   BC1A->B->D->B->C ED-44>D-41BE0A->B->D->B->E

   它结果发现节点B当前是可更新的，这证明那里存在恶性循环。图表。

   当步数无限时，找不到到达每个节点的最短路径。如果人为限制步数，则找到从源点到每个节点的最短路径

   总结

   1。广度优先算法 BFS 最适合在失重图中寻找从源点到端点的最少步数路径。当方向图有价值时，就不能再应用了

   2。 Dijkstra算法主要用于加权指令。在图中搜索最短路径，但不适用于负权值的情况。对于环图，我个人的印象和BFS是一样的。已处理的节点被标记以避免不受限制的访问。可以支持

   3。贝尔曼-福特算法Bellman –Ford主要用在有负权重的有向图中（没有负权重也可以使用，但性能比Dijkstra低很多）寻找从一个源点到每个节点的最短路径

   4 。 Bellman-Ford可以确定图是否存在负环，但是当存在负环时，无法计算到每个节点的最短路径。完成（节点数 - 1）次遍历后，只需再进行一次遍历即可。如果数据仍然可以更新，则意味着存在负线

   5。当人为限制pass数的时候，也可以计算负循环，但是好像没有意义

   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

   作者：CodeInfo
   链接：https://juejin.im / post/5b77fec1e51d4538cf53be68
   来源：掘金
   版权归作者所有。如需商业印刷，请联系作者以获得许可。非商业转载请注明来源。