算法-贝尔曼-福特算法_bellman鈥榮 algorithm

算法-贝尔曼-福特算法

注：该文是本博主记录学习之用，没有太多详细的讲解，敬请谅解！

一、简介

贝尔曼-福特算法(Bellman–Ford algorithm )用于计算出起点到各个节点的最短距离，支持存在负权重的情况

• 它的原理是对图进行最多V-1次松弛操作，得到所有可能的最短路径。其优于狄克斯特拉算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。

• 贝尔曼-福特算法每次对所有的边进行松弛，每次松弛都会得到一条最短路径，所以总共需要要做的松弛操作是V - 1次。在完成这么多次松弛后如果还是可以松弛的话，那么就意味着，其中包含负环。

二、场景

• 从起点出发是否存在到达各个节点的路径。
• 从起点出发到达各个节点最短路径。
• 是否存在负环路。

三、实现思路

• 初始化时将起点s到各个顶点v的距离dist(s->v)赋值为∞，dist(s->s)赋值为0

• 后续进行最多n-1次遍历操作，对所有的边进行松弛操作,假设:

  所谓的松弛，以边ab为例，若dist(a)代表起点s到达a点所需要花费的总数，
  dist(b)代表起点s到达b点所需要花费的总数,weight(ab)代表边ab的权重， 若存在:

  (dist(a) +weight(ab)) < dist(b)

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

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

四、java实现

如下图，求出A到各节点的最短路径

public class BellmanFord {

    /**
     * 实现思路：
     * 1、初始化时将起点起点到各个顶点的距离赋值为（无穷大）∞,当前起点距离赋值为0
     * 2、后续进行最多n-1次遍历操作
     * @param args
     */
    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;
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

五、小结

1、贝尔曼-福特算法Bellman–Ford主要用于存在负权重的方向图中(没有负权重也可以用，但是效率比狄克斯特拉算法低很多)，搜索出源点到各个节点的最短路径

2、Bellman–Ford可以判断出图是否存在负环路，但存在负环路的情况下不支持计算出各个节点的最短路径。只需要在结束(节点数目-1)次遍历后，再执行一次遍历，若还可以更新数据则说明存在负环路