Bellman-Ford算法--解决负权边问题

1、算法简介

  前阵子备考蓝桥杯的时候碰到了这个算法，感觉还挺有意思的，实现起来也非常简单。

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

  贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共$|V|-1$次，其中$|V|$是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

来源于百度百科

2、算法伪代码实现

  Bellman-Ford算法的时间复杂度为$O(NE)$，N是顶点数，M是边的数量

  算法实现：

  设s为起点，$dis[v]$为s到v的最短距离，$pre[v]$为v的前驱,$w[j]$是边j的长度，且j链接u、v。

  初始化：$dis[s]=0,dis[v]=\infty ,pres[s]=0$

for(i=1;i<=n-1;j++){	//松弛n-1次
	for(j=1;j<=M;j++){//枚举所有边
		if(dis[u[j]]+w[j]<dis[v[j]]){
            dis[v[j]]=dis[u[j]]+w[j];
            pre[v[j]]=u[j];
        }
	}
}

  核心思想：看能否用过$w[j]$这条边让1号顶点到$v[j]$号顶点的距离变短。

3、算法实例

  假设我们现在知道了一些边的权值如下：

2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3

  先初始化：$dis[s]=0,dis[v]=\infty ,pres[s]=0$

  第一次松弛，由于是遍历边，我们直接按照上边边的顺序遍历就好

  输入2 3 2，由于$dis[2]+2=dis[3]=\infty$，不更新

  输入1 2 -3,由于$dis[1]+(-3)=-3<\infty ,则dis[2]=-3$,

  输入1 5 5,由于$dis[1]+5=5<dis[5]$,则$dis[5]=5$

  输入4 5 2,不更新

  输入3 4 3，不更新

  第一次松弛的结果如下：

第二次松弛：

  输入2 3 2，由于$dis[2]+2=-3+2=-1<dis[3]$,更新$dis[3]=-1$

  输入1 2 -3，不更新

  输入1 5 5,不更新

  输入4 5 2,不更新

  输入3 4 3,由于$dis[3]+3=-1+3=2<dis[4]$,更新$dis[4]=2$

  第二次松弛结果如下:

第三次松弛：

  输入2 3 2，不更新

  输入1 2 -3,不更新

  输入1 5 5，不更新

  输入4 5 2,由于$dis[4]+2=2+2=4<dis[5]$,更新$dis[5]=4$

  输入3 4 3，不更新

  第三次松弛的结果如下：

第四次松弛

  输入2 3 2，不更新

  输入1 2 -3,不更新

  输入1 5 5，不更新

  输入4 5 2,不更新

  输入3 4 3，不更新

  我们发现，至多松弛n-1遍，因为一条最短路径的长度最多为n-1条。

  在实际操作中，该算法井场会在未达到n-1次松弛前就已经计算出最短路径，所以就有响应的优化算法,SPFA。

  此时的dis数组如下：

4、代码实现

4.1 题目描述

  小明是蓝桥王国的王子，今天是他登基之日。

  在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。

  题目的内容如下：

  蓝桥王国一共有N个建筑和M条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为$1\sim N$。(其中皇宫的编号为1).

  国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。

输入描述

  输入第一行包含两个正整数N,M。

  第2到M+1行每行包含三个正整数u,v,w，表示$u\to v$之间存在一条距离为w的路。
$$1\le N\le 3\times 10^5,1\le m\le 10^6,1\le u_i,v_i\le N,0\le w_i\le 10^9$$
输出描述

  输出仅一行，共N个数，粉笔表示从皇宫到编号为$1\sim N$建筑的最短距离，两两之间用空格隔开。(如果无法到达则输出-1)

输入输出样例

输入

3 3
1 2 1
1 3 5
2 3 2

输出

0 1 3

这道题目我以前用Dijkstra写过，链接：Dijkstra-单源最短路径算法

4.2 完整代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Bellman-Ford算法求解最短路径：可以解决负边权问题
 * 但是不能解决负权回路问题
 */
public class BellmanFord {
    public static List<int[]> edges=new ArrayList<>();
    public static int[] dist;
    public static int[] prev;//记录节点前驱
    public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int m = nextInt();
        dist=new int[m+1];
        prev=new int[m+1];
        for (int i = 0; i <m; i++) {
            int u = nextInt();
            int v = nextInt();
            int w = nextInt();
            edges.add(new int[]{u,v,w});
            edges.add(new int[]{v,u,w});
        }
        //初始化
        Arrays.fill(dist,Integer.MAX_VALUE>>1);
        Arrays.fill(prev,-1);
        int s=1;    //设置起点
        dist[s]=0;  //起点的dist设置为0,其他设置为无穷大
        for (int i = 1; i <=n-1; i++) {//最多执行n-1次松弛
            for (int[] edge : edges) {  //枚举边
                int u = edge[0];
                int v = edge[1];
                int w = edge[2];
                if(dist[u]+w<dist[v]){
                    dist[v]=dist[u]+w;
                    prev[v]=u;  //记录v的前驱为u
                }
            }
        }
        Arrays.stream(dist).skip(1).forEach(x->{// dist
            System.out.print(x+" ");
        });
        System.out.println();
        System.out.println(Arrays.toString(prev));//[-1,-1,1,2]

        //输出从起点出发到每个点的最短路径
        for (int i = 1; i <=n; i++) {
            print(s,i);
            System.out.println();
        }

    }
    //Bellmen-sord输出路径:倒着往回找路径，正着输出
    public static void print(int start,int end){
        if(start==end){
            System.out.print(start+" ");
            return;
        }
        print(start,prev[end]);//不断查找end的前驱，知道前驱节点为start
        System.out.print(end+" ");
    }
    public static int[] bellmanFord(int n,int s,int[][] edges){
        //dist[v]为s到v的最短距离
        int[] dist=new int[n];
        //pre[v]为v的前驱
        int[] prev=new int[n];

        for (int i = 0; i < n; i++) {
            dist[i]=Integer.MAX_VALUE>>1;
            prev[i]=-1;
        }
        dist[s]=0;

        for (int i = 0; i < n - 1; i++) {   //最多进行n-1次松弛操作
            for (int[] edge : edges) {  //枚举所有边
                int u = edge[0];
                int v= edge[1];
                int w = edge[2];
                //dist[v]=Math.min(dist[v],dist[u]+w)
                if(dist[u]+w<dist[v]){
                    dist[v]=dist[u]+w;
                    prev[v]=u;
                }
            }
        }
        //检测是否存在负权回路
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            if(dist[u]+w<dist[v]){
                System.out.println("图中存在负权回路");
            }
        }
        return dist;
    }
    public static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }
}

  这里我将$pre[v]$全部初始化为-1了，这个不重要。