负权值最短路径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是边数
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)