负权值最短路径Bellman-Ford算法

1. 简述

在解决图中的单元最短路径时，经常使用到的算法是Dijkstra算法，但是如果图中的边的权值为负数的话，Dijkstra算法就不适用了，此时需要一种新的算法：Bellman-Ford算法

松弛操作：在Dijkstra算法中，会有一个更新距离的操作，该操作就是一个松弛操作，在Dijkstra算法中，当一个新的节点v被加入集合S时，会根据该节点来更新源点到与v可以到达的其他点的距离。

Dijkstra算法以贪心法选取未被处理的具有最小权值的节点，然后对其出边进行松弛操作

Bellman-Ford算法对所有边都进行松弛操作，共n -1次

负环：一个环路，环路上的边的权值之和为负数

当一个图中存在负环时，不存在最短路径，因此可以反复经过负环，使得权值不断减少

如和判断负环的存在？
对图G进行V-1次松弛操作，如果再进行第V次操作时还能松弛（更新），说明存在负环

2. 算法的基本实现

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class BellmanFordDemo {
	double[] dis;
	int[] pre;//保存路径上的前驱节点

	public boolean solve(ArrayList<Edge> G,int start,int n) {
		dis=new double[n];
		pre=new int[n];
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[start]=0;
		for(int i=1;i<n;i  ) {
			boolean flag=false;
			for(Edge edge:G) {//对所有的边进行松弛操作
				int from=edge.from;
				int to=edge.to;
				double weight=edge.weight;
				if(dis[to]>dis[from] weight) {//松弛操作 更新s->to的路径长度
					dis[to]=dis[from] weight;
					pre[to]=from;
					flag=true;
				}
			}
			if(!flag)//在某一轮循环中如果没有发生松弛 说明松弛操作提前结束
				return false;//松弛完毕且无环
		}
		for(Edge edge:G) {
			int from=edge.from;
			int to=edge.to;
			double weight=edge.weight;
			if(dis[to]>dis[from] weight) {
				return true;//松弛完V-1次后如果还能松弛 说明存在负权值的环
			}
		}
		return false;//无负权值的环
		
	}
	 public LinkedList<Integer> path(int start,int end)
     {
         LinkedList<Integer> st=new LinkedList<>();
         for(int x=end;x!=start;x=pre[x])
             st.push(x);
         st.push(start);
         return st;

     }
	public static void main(String[] args) {
		int V=8,E=15;
		BellmanFordDemo obj=new BellmanFordDemo();
		ArrayList<Edge> edges=new ArrayList<>();
		Edge edge1=new Edge(4,5,0.35);
		Edge edge2=new Edge(5,4,0.35);
		Edge edge3=new Edge(4,7,0.37);
		Edge edge4=new Edge(5,7,0.28);
		Edge edge5=new Edge(7,5,0.28);
		Edge edge6=new Edge(5,1,0.32);
		Edge edge7=new Edge(0,4,0.38);
		Edge edge8=new Edge(0,2,0.26);
		Edge edge9=new Edge(7,3,0.39);
		Edge edge10=new Edge(1,3,0.29);
		Edge edge11=new Edge(2,7,0.34);
		Edge edge12=new Edge(6,2,-1.20);
		Edge edge13=new Edge(3,6,0.52);
		Edge edge14=new Edge(6,0,-1.40);
		Edge edge15=new Edge(6,4,-1.25);
		edges.add(edge1);
		edges.add(edge2);
		edges.add(edge3);
		edges.add(edge4);
		edges.add(edge5);
		edges.add(edge6);
		edges.add(edge7);
		edges.add(edge8);
		edges.add(edge9);
		edges.add(edge10);
		edges.add(edge11);
		edges.add(edge12);
		edges.add(edge13);
		edges.add(edge14);
		edges.add(edge15);
		int start=0;
		boolean hasNegativeCycle=obj.solve(edges, start, V);
		if(hasNegativeCycle) {
			System.out.println("negative cycle exists");
		}else {
			for(int i=0;i<V;i  ) {
				System.out.print(start "-->" i " : " obj.dis[i]);
				System.out.println("  path:" obj.path(start, i));
			}
		}
		
	}
}
class Edge{
	int from,to;
	double weight;
	public Edge(int from, int to, double weight) {
		super();
		this.from = from;
		this.to = to;
		this.weight = weight;
	}
}
//时间复杂度  O(VE)

3. 优化

松弛操作必定只会发生在最短路径松弛过的前驱节点上，用一个队列记录松弛过的节点，可以避免冗余计算

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BellmanFordDemo {
	double[] dis;
	int[] pre;//保存路径上的前驱节点
	boolean[] vis;
	int[] cnt;

	public boolean solve(ArrayList<Edge>[] G,int start,int n) {
		dis=new double[n];
		pre=new int[n];
		vis=new boolean[n];
		cnt=new int[n];//记录某个节点的入队次数
		Arrays.fill(dis, Integer.MAX_VALUE);
		Queue<Integer> q=new LinkedList<>();
		q.offer(start);
		dis[start]=0;
		vis[start]=true;
		cnt[start]  ;
		while(!q.isEmpty()) {
			int x=q.poll();
			vis[x]=false;//标记x不在队列中 因为会存在a<=>b这种情况 b可以再次达到a
			for(Edge edge:G[x]) {
				int to=edge.to;
				if(dis[to]>dis[x] edge.weight) {
					dis[to]=dis[x] edge.weight;
					pre[to]=x;
					if(!vis[to]) {
						if(  cnt[to]>=n)//某个节点的入队次数如果大于等于n说明有负环
							return true;
						vis[to]=true;
						q.offer(to);//标记to在队列中
					}
				}
			}
			
		}
		
		return false;//无负权值的环
		
	}
	 public LinkedList<Integer> path(int start,int end)
     {
         LinkedList<Integer> st=new LinkedList<>();
         for(int x=end;x!=start;x=pre[x])
             st.push(x);
         st.push(start);
         return st;

     }
	public static void main(String[] args) {
		int V=8,E=15;
		BellmanFordDemo obj=new BellmanFordDemo();
		ArrayList<Edge> edges=new ArrayList<>();
		Edge edge1=new Edge(4,5,0.35);
		Edge edge2=new Edge(5,4,0.35);
		Edge edge3=new Edge(4,7,0.37);
		Edge edge4=new Edge(5,7,0.28);
		Edge edge5=new Edge(7,5,0.28);
		Edge edge6=new Edge(5,1,0.32);
		Edge edge7=new Edge(0,4,0.38);
		Edge edge8=new Edge(0,2,0.26);
		Edge edge9=new Edge(7,3,0.39);
		Edge edge10=new Edge(1,3,0.29);
		Edge edge11=new Edge(2,7,0.34);
		Edge edge12=new Edge(6,2,-1.20);
		Edge edge13=new Edge(3,6,0.52);
		Edge edge14=new Edge(6,0,-1.40);
		Edge edge15=new Edge(6,4,-1.25);
		edges.add(edge1);
		edges.add(edge2);
		edges.add(edge3);
		edges.add(edge4);
		edges.add(edge5);
		edges.add(edge6);
		edges.add(edge7);
		edges.add(edge8);
		edges.add(edge9);
		edges.add(edge10);
		edges.add(edge11);
		edges.add(edge12);
		edges.add(edge13);
		edges.add(edge14);
		edges.add(edge15);
		ArrayList<Edge>[] G=new ArrayList[V];
		for(Edge edge:edges) {
			int from=edge.from;
			if(G[from]==null) {
				G[from]=new ArrayList<>();
			}
			G[from].add(edge);
		}
		int start=0;
		boolean hasNegativeCycle=obj.solve(G, start, V);
		if(hasNegativeCycle) {
			System.out.println("negative cycle exists");
		}else {
			for(int i=0;i<V;i  ) {
				System.out.print(start "-->" i " : " obj.dis[i]);
				System.out.println("  path:" obj.path(start, i));
			}
		}
		
	}
}
class Edge{
	int from,to;
	double weight;
	public Edge(int from, int to, double weight) {
		super();
		this.from = from;
		this.to = to;
		this.weight = weight;
	}
}

修改上面的边：Edge edge2=new Edge(5,4,-0.66); 则会形成负环，运行结果如下：

时间复杂度和未优化的Bellman-Ford算法相同，为O (nm )；但在稀疏图上运行效率较高，为O (km )，其中k 是一个较小的常数，n是结点数，m是边数

这篇好文章是转载于：学新通技术网