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≤N≤3×105,1≤m≤106,1≤ui,vi≤N,0≤wi≤1091\\le N\\le 3\\times10^5,1\\le m\\le10^6,1\\le u_i,v_i\\le N,0\\le w_i \\le 10^9 1≤N≤3×105,1≤m≤106,1≤ui​,vi​≤N,0≤wi​≤109
输出描述

  输出仅一行，共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->{// distSystem.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的前驱，知道前驱节点为startSystem.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了，这个不重要。