前阵子备考蓝桥杯的时候碰到了这个算法,感觉还挺有意思的,实现起来也非常简单。
贝尔曼-福特算法(Bellman-Ford)是由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特 创立的,求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法,因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行V-1次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达O(VE)。但算法可以进行若干种优化,提高了效率。
贝尔曼-福特算法与迪科斯彻算法类似,都以松弛操作为基础,即估计的最短路径值渐渐地被更加准确的值替代,直至得到最优解。在两个算法中,计算时每个边之间的估计距离值都比真实值大,并且被新找到路径的最小长度替代。 然而,迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点,然后对其的出边进行松弛操作;而贝尔曼-福特算法简单地对所有边进行松弛操作,共
次,其中
是图的点的数量。在重复地计算中,已计算得到正确的距离的边的数量不断增加,直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。
来源于百度百科
Bellman-Ford算法的时间复杂度为
,N是顶点数,M是边的数量
算法实现:
设s为起点,
为s到v的最短距离,
为v的前驱,
是边j的长度,且j链接u、v。
初始化:
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];
}
}
}
核心思想:看能否用过
这条边让1号顶点到
号顶点的距离变短。
假设我们现在知道了一些边的权值如下:
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
先初始化:
第一次松弛,由于是遍历边,我们直接按照上边边的顺序遍历就好
输入2 3 2
,由于
,不更新
输入1 2 -3
,由于
,
输入1 5 5
,由于
,则
输入4 5 2
,不更新
输入3 4 3
,不更新
第一次松弛的结果如下:
第二次松弛:
输入2 3 2
,由于
,更新
输入1 2 -3
,不更新
输入1 5 5
,不更新
输入4 5 2
,不更新
输入3 4 3
,由于
,更新
第二次松弛结果如下:
第三次松弛:
输入2 3 2
,不更新
输入1 2 -3
,不更新
输入1 5 5
,不更新
输入4 5 2
,由于
,更新
输入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数组如下:
小明是蓝桥王国的王子,今天是他登基之日。
在即将成为国王之前,老国王给他出了道题,他想要考验小明是否有能力管理国家。
题目的内容如下:
蓝桥王国一共有N个建筑和M条单向道路,每条道路都连接着两个建筑,每个建筑都有自己编号,分别为
。(其中皇宫的编号为1).
国王想让小明回答从皇宫到每个建筑的最短路径是多少,但紧张的小明此时已经无法思考,请你编写程序帮助小明回答国王的考核。
输入描述
输入第一行包含两个正整数N,M。
第2到M+1行每行包含三个正整数u,v,w,表示
之间存在一条距离为w的路。
输出描述
输出仅一行,共N个数,粉笔表示从皇宫到编号为
建筑的最短距离,两两之间用空格隔开。(如果无法到达则输出-1)
输入输出样例
输入
3 3
1 2 1
1 3 5
2 3 2
输出
0 1 3
这道题目我以前用Dijkstra写过,链接:Dijkstra-单源最短路径算法
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;
}
}
这里我将
全部初始化为-1了,这个不重要。