零基础学算法100天第2天——bellman-ford（边数限制最短路算法）

⭐️目录⭐️

?1.什么是bellman-ford算法？

? 2.bellman-ford和Dijkstra有什么区别？

? 3.什么是松弛操作？

 ?4.bellman-ford的基本思路和注意事项

 ?5.模板代码以及例题训练

        ?K站中转内最便宜的航班

?6.课后总结

?1.什么是bellman-ford算法？

        首先我们从百度百科来了解一下bellman-ford

            贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的，求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。

         bellman-ford使用场景：

        1.bellman-ford适用于解决带有负权边的单源最短路问题。

        2.bellman-ford可用于判断图中是否存在负权环（但我们一般不使用该算法进行判断）

 3.bellman-ford可用于有边数限制的情况(使用bellman-ford最重要的标志)

? 2.bellman-ford和Dijkstra有什么区别？

       首先从适用场景上来说：Dijkstra值只能用于只有正权边的单源最短路问题，而bellman-ford算法不仅能适用于带正权边而且适用于带负权边的情况。而且当题目对边数有限制要求时，别犹豫，一定要使用bellman-ford算法。

       其次我们最关心的应该是算法的时间复杂度，朴素版的Dijkstra的时间复杂度是O（n^2），n是点的数量（和边无关系），而堆优化版的Dijkstra的时间复杂度为O（mlongn），m是边数，n是点的数量。而bellman-ford算法的时间复杂度是O（mn），这个复杂度还是比较高的。所以一般使用bellman-ford算法时，一定要注意题目中给定的点数和边数，如果不是非常明显具有使用bellman-ford的提示，对于bellman-ford算法一定要慎用。

? 3.什么是松弛操作？

           这个词语会经常出现在每一个最短路算法中，大家也会经常看见。上篇Dijkstra中我并没有认真的说清楚它的意思，只是有简略的语言带过了一下，这篇文章我们来细讲一下。

          首先，松弛操作是Dijkstra和bellman-ford能找到最短路径的核心操作，两种算法都是基于它来实现的。         

         我们以上面的简图为例，首先提高松弛操作那就一定要提到dist[]数组，它是保存从起点到每个点的最短距离，比如dist[j]表示从起点i到j的最短距离，更详细的解释在Dijkstra说明了，不太明白的建议去看看。

        上面的图中，A是起点，C是终点。我们在对B点做松弛操作时，要去遍历所有除去起点和本身的其他点，当然这个图里只有C点，然后判断dist[c]是否大于dist[b]+g[b][c]（此处的g数组是邻接矩阵数组，g[i][j]表示i点到j点这条边的距离）。上图中dist[c]本来是25，dist[b]是5，而g[b][c]是15，因为dist[c]>dist[b]+g[b][c]，所以我们将dist[c]更新为20，也就表示我们找到了一条到达C点更近的线路，这就是松弛操作。

        其实松弛操作非常好理解，就是判断，在已有的到达某点X的最短线路中，能否通过其他的点去更新这个最短路径，核心操作就是判断dist[c]是否大于dist[b]+g[b][c]。

 ?4.bellman-ford的基本思路和注意事项

          1.图的存边方式

           bellman-ford算法是基于边来进行遍历迭代的，所以我们需要保存去保存每条边和它的权值，我们可以才取最简单的方式，也就是结构体存边即可，Java用一个Node类表示，属性有int类型的a，b，w。表示为有一条从a到b权值为w的边。

class Node{
    int a,b,w;
    public Node(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
    }
}

       2.for循环n次，每次遍历所有的边（所以时间复杂度是O（nm）） 

        算法流程只需要循环n次，每次用所有的边去进行松弛操作即可，bellman-ford就是如此的简单，模板也非常容易记忆。只要知道松弛操作是如何，这个算法就是一个非常简单算法，因为它本身就是一个偏暴力的算法，所以时间复杂度比较高。

       3.对于图中可能存在负权回路的情况

        如图这种情况，如果计算从A点到E点的距离，由于BCD是形成了一个负环，每循环一次权值就-1，所以如果循环无数圈就是负无穷，结果得到到E的最短距离是负无穷。但是大家不要担心，一般题目都不会出现这种情况，会说明，只不过大家要知道有这种情况产生。

        那是不是有负环就一定不能得到解呢？

        那也不一定，如果负环在我们走的路径上，那就会产生影响，否则是不会影响我们的最短路径的。

       4.如何去利用bellman-ford解决有边数限制的情况

        其实我们前面就已经提过，在bellman-ford中我们先需要循环n次，代表了走了n条边的最短路径，我们现在限制只能走k条边，所以我们只需要让循环只走k次，以此来限制走的边数即可，其余的代码不需要改变。

       5.backup作为备份数组的必要性

        在bellman-ford和Dijkstra算法中，都有dist数组记录最短路径，而bellman-ford中还有一个 backup 数组，它作为的是我们的备份数组。它的存在为的是防止前面的边松弛影响到后面的边的松弛操作。我们每次松弛的的时候利用的是上一次的结果来。

       比如在如图，边数限制为1的情况下，从1到3的最短路径应该为3。初始的时候dist[]数组应该是被初始化为正无穷的。如果此时我们对1~2这边进行操作以后使得dist[2]=1以后，再松弛2~3这条边的时候，就会导致dist[3]变成了2，也就没有无法保证只有1条边了。

       说白了其实就是bellman-ford的dist数组并不是实时更新，每一次循环m次都用的是上一次循环的dist数组，所以我们用backup备份上一次的dist数组。

 ?5.模板代码以及例题训练

       代码转换：模板为bellman_ford函数，函数的每个操作我都搭配上了讲解。

import java.util.*;
public class Main {
    static int N=510;
    static int M=10010;
    static List<Node> list=new ArrayList<>();
    static int[] dist=new int[N];
    static int[] backup=new int[N];
    static int n,m,k;
    static boolean flag=false;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        k=sc.nextInt();
        for (int i = 0; i <m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int w=sc.nextInt();
            list.add(new Node(a,b,w));
        }
        int t=bellman_ford();
        if(t==-1&&flag) System.out.println("impossible");
        else System.out.println(t);
    }
    static int bellman_ford(){
        //和Dijkstra一样的初始化步骤
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1]=0;
        //限制k条边，所以只循环K次
        for (int i = 0; i < k; i++) {
            //每次松弛操作前先备份一下
            backup=Arrays.copyOfRange(dist,0,N);
            //开始松弛操作
            for (int j = 0; j < m; j++) {
                int a=list.get(j).a;
                int b=list.get(j).b;    
                int w=list.get(j).w;
                //和Dijkstra的差不多，只不过一定要使用backup进行松弛
                dist[b]=Math.min(dist[b],backup[a]+w);
            }
        }
        //注意这里是除以2，因为有负数的情况，在无解的情况下不一定刚好等于0x3f3f3f3f
        if (dist[n]>0x3f3f3f3f/2){
            flag=true;
            return -1;
        }else return dist[n];
}
}
class Node{
    int a,b,w;
    public Node(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
    }
}

        ?K站中转内最便宜的航班

        有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

        现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

         这是一道bellman-ford的模板题，从题目的名字就已经告诉我们要使用该算法了。K站中转——限制边数，最便宜航班——最短路问题。在这里我们要注意一个问题，K次中转是K条边吗？当然不是，转了一次车说明做了两种不同的车，所以K次中转我们应该是K+1条边。

        在这里我们直接使用上面的模板即可：

class Solution {
    //有边数限制使用贝尔曼夫算法
    int N=100;
    int M=5010;
    List<Node> list=new ArrayList<>();
    int[] dist=new int[N];
    int[] backup=new int[N];
    int n,m,k,src,dst;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        this.n=n;
        this.m=flights.length;
        //k次中转是k条边
        this.k=k+1;
        this.src=src;
        this.dst=dst;
        for(int[] s:flights){
            int a=s[0];
            int b=s[1];
            int w=s[2];
            list.add(new Node(a,b,w));
        }
        int t=bellman_ford();
        return t;
    }
    int bellman_ford(){
        Arrays.fill(dist,0x3f3f3f3f);
        dist[src]=0;
        for(int i=0;i<k;++i){
            backup=Arrays.copyOfRange(dist,0,N);
            for(int j=0;j<m;++j){
                int a=list.get(j).a;
                int b=list.get(j).b;
                int w=list.get(j).w;
                dist[b]=Math.min(dist[b],backup[a]+w);
            }
        }
        if(dist[dst]>0x3f3f3f3f/2) return -1;
        else return dist[dst];
    }
}
class Node{
    int a,b,w;
    public Node(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
    }
}