图论】(单源最短路径)Bellman-Ford算法

图论】(单源最短路径)Bellman-Ford算法

Dijkstra 算法虽然好,但是他不能解决带有负权边的(边的权值为负数)的图,下面我们就来说一下几乎完妹求最短路径的算法Bellman-ford。Bellman-ford算法也非常简单,核心代码只有几行,并且可以完美的解决带有负权的图,先来看看这个核心代码吧

for(int k = 1 ; k <= n - 1 ; k ++)
{
    for(int i = 1 ; i < m ; i ++)
    {
        if(dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i] ;
    }
}

这个算法的名字叫做

中文名   贝尔曼-福特算法

外文名   Bellman – Ford algorithm

上边的代码外循环共循环了n – 1 次(n为顶点的个数),内循环共循环了m次(m代表边的个数)即枚举每一条边, dis 数组是的作用和dijkstra 算法一样,也是用来记录源点到其余各个顶点的最短路径,u,v,w 三个数组用来记录边的信息。例如第i条边存储在u[i]、v[i]、w[i]中,表示从顶点u[i]到顶点v[i]这条边(u[i] –> v[i])权值为w[i]。

两层for循环的意思是:看看能否通过u[i]—>v[i] (权值为w[i])这条边,使的1号顶点的距离变短。即1号顶点到u[i]号顶点的距离(dis[u[i]]) 加上 u[i] —> v[i]这条边(权值为w[i])的值是否比原来1号顶点到v[i]号距离(dis[v[i]])要小。这点感觉和迪杰斯特拉的松弛操作有点儿像。。。

我们把每一条边都松弛一遍后会怎么样呢?我们来举个例子,求下图1号顶点到其余所有顶点的最短路径。

图论】(单源最短路径)Bellman-Ford算法
 

我们还是用一个dis数组来存储1号顶点到所有顶点的距离。

我们先来初始化:

图论】(单源最短路径)Bellman-Ford算法

上方右图中每个顶点旁的值为该定点的最短路的“估计值”(当前1号顶点到他的距离),即dis中对应的值。根据边给出的顺序,先来处理一下第一条边“2-3-2”(2–2–>3通过这条边进行松弛)即判断dis[3]是否大于dis[2]+2。此时的dis[3]是∞,dis[2]的值也是∞,因此dis[2] + 2也是∞,所以这条边松弛失败。

同时我们继续处理第二条边“1–2 —       -3” (1–“-3”–>2 ) 我们发现dis[2] > dis[1] + (-3) ,通过这条边可以使dis[2]的值从∞变为 -3 ,所以这个点松弛成功。我们可以用同样的方法来处理剩下的一条边,对所有的边进行一遍松弛操作后的结果如下。

图论】(单源最短路径)Bellman-Ford算法

 

我们能发现,在对每一条边都进行一次松弛操作后,已经使dis[2]和dis[5]的值变小,即1号顶点到2号顶点和1号顶点到5号顶点的距离都变短了。

接下来我们要对所有边再进行一轮松弛操作,操作过程大致和上边的一样,再看看会有什么变化。

图论】(单源最短路径)Bellman-Ford算法

      在这一-轮松弛时,我们发现,现在通过“2 3 2”(2→3)这条边,可以使1号顶点到3号顶点的距离(dis[3]) 变短了。爱思考的同学就会问了,这条边在上一一轮也松弛过啊,为什么上一一轮松弛失败了,这一”轮却成功了呢?因为在第一 轮松弛过后,1号顶点到2号顶点的距离(dis[2]) 已经发生了变化,这一-轮再通过“232”(2-→3)这条边进行松弛的时候,已经可以使1号顶点到3号顶点的距离(dis[3]) 的值变小。
    换句话说,第1轮在对所有的边进行松弛之后,得到的是从1号顶点“只能经过一条边”到达其余各顶点的最短路径长度。第2轮在对所有的边进行松弛之后,得到的是从1号顶点“最多经过两条边”到达其余各顶点的最短路径长度。如果进行k轮的话,得到的就是1号顶点“最多经过k条边”到达其余各顶点的最短路径长度。现在又有一一个新问题:需要进行多少轮呢?

图论】(单源最短路径)Bellman-Ford算法  

  只要进行n – 1 轮就可以了,因为在一个含有n个顶点的图中,任意两点之间的最短路径最多包含n-1条边。
   我们这个算法真的就只能包含n-1条边吗?最短路径中不能包含回路吗?
   答案是:不可能!最短路径肯定是一个不包含回路的简单路径。回路分为正权回路(即回路权值之和为正)和负权回路(即回路权值之和为负)。我们分别来讨论一下为什么这两种回路都不可能有。如果最短路径中包含正权回路,那么去掉这个回路,一定可以得到更短的路径。如果最短路径中包含负权回路,那么肯定没有最短路径,因为每多走一次 负权回路就可以得到更短的路径。  因此,最短路径肯定是-一个不包含回路的简单路径,即最多包含n-1条边,所以进行n-1轮松弛就可以了。
  扯了半天,回到之前的例子,继续进行第3轮和第4轮松弛操作,这里只需进行4轮就可以了,因为这个图一共只有5个顶点。

这里看似貌似不需要第四轮,因为执行完第四轮没有任何变化!没错,其实就是最多进行  n – 1 轮松弛。

整个算法用一句话概括就是:对所有的边进行n-1次松弛操作。核心代码就只有几行,如下:

 我们来总结一下。因为最短路径上最多有n-1条边,所以Bellman-Ford算法最多有n-1个阶段。在每-一个阶段,我们对每一条边 都要执行松弛操作。其实每实施一次松弛操作, 就会有一些顶点已经求得其最短路,即这些顶点的最短路的“估计值”变为“确定值”。此后这些顶点的最短路的值就会一直保持不变,不再受后续松弛操作的影响(但是,每次还是会判断是否需要松弛,这里浪费了时间,是否可以优化呢? )。在前k个阶段结束后,就已经找出了从源点发出“最多经过k条边”到达各个顶点的最短路。直到进行完n-1个阶段后,便得出了最多经过n-1条边的最短路。
  Bellman-Ford算法的完整的代码如下。

#include<bits/stdc++.h>
const int INF = 99999999;
using namespace std;
int main()
{
    int u[100] , v[100] , w[100] , dis[100] , n , m ;
    cin>>n>>m;
    for(int i = 1 ; i <= m ; i ++)
    {
        cin>>u[i] >> v[i] >> w[i];
    }
    for(int i = 1 ; i  <= n ; i ++)
    dis[i] = INF;
    dis[1] = 0;
    for(int k = 1 ; k <= n - 1 ; k ++)
        for(int i = 1 ; i <= m ; i ++)
            if(dis[v[i]] > dis[u[i]] + w[i])
                dis[v[i]] = dis[u[i]] + w[i];
            for(int i = 1 ; i <= n ; i ++)
                cout<<dis[i]<<" ";
    return 0 ;
}
 
 
/*
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
*/

部分借鉴于这位大佬

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114871.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • PDAF原理简介_pfc电路工作原理图

    PDAF原理简介_pfc电路工作原理图PDAF原理原理及分类原理:是在感光芯片上预留出一些规律性对称的遮蔽像素点,专门用来进行相位检测,通过像素之间的距离及变化来决定对焦的偏移量即相位差(PD值)从而实现快速对焦。SP(shieledpixel)屏蔽掉像素一般的感光区域(黑色部分),值获得一半信号。需要另外的像素屏蔽掉另一半信号,得到完整的相位差信息。SP越多,对焦越快,但信号损失越严重,目前SP密度控制在1%~3%。屏蔽掉像素一般的感光区域(黑色部分),值获得一半信号。需要另外的像素屏蔽掉另一半信号,得到完整的相位差信息。S

  • 用matlab画三维图实例_cad绘制3d图形的教程

    用matlab画三维图实例_cad绘制3d图形的教程文章目录一、引言二、绘制三维空间曲线三、绘制三维空间曲面1.基本概念2.示例(1)3.示例(2)4.等高线的曲面图5.被光照射带阴影的曲面6.图形修饰方法四、绘制等高线一、引言一图胜前言,本篇文章的目的就是绘制这样的三维图形二、绘制三维空间曲线plot3——基本的三维曲线绘制命令调用格式:plot3(x,y,z)——x,y,z是长度相同的向量plot3(X,Y,Z)——X,Y,Z是维数相同的矩阵plot3(x,y,z,’s’)——开关量字符串s用来设定曲线颜色和

    2022年10月11日
  • “找不到VMware Tools 安装包”的解决办法——安装VMware Tools

    “找不到VMware Tools 安装包”的解决办法——安装VMware Tools最近刚接触虚拟机,在VMware下安装的是Ubuntu16.04.4。在安装完Ubuntu以后,想安装一个VMwareTools来解决文件在win10和虚拟机之间的拖拽问题,但是按照网上的教程左键点击“虚拟机——安装VMwareTools”选项卡以后没有找到VMwareTools的压缩包。VMwareTools的好处在于可以直接将win10下的文件拖拽或者复制粘贴到ubuntu中,而且…

  • 彻底解决Qt中文乱码以及汉字编码的问题(UTF-8/GBK)

    彻底解决Qt中文乱码以及汉字编码的问题(UTF-8/GBK)一、Qt环境设置QtCreator,菜单->工具->选项->文本编辑器->行为->文件编码:默认编码:System(简体中文windows系统默认指的是GBK编码,即下拉框选项里的GBK/windows-936-2000/CP936/MS936/windows-936)二、编码知识科普Qt常见的两种编码是:UTF-8和GBK★UTF-8:UnicodeTransformat

  • HandlerSocket简介及安装及卸载

    HandlerSocket简介及安装及卸载HandlerSocket是日本人akirahiguchi写的一个MySql的插件。通过这个插件,你可以直接跟MySQL后端的存储引擎做key-value式的交互,省去了MySQL上层的SQL解释、打开关闭表、创建查询计划等CPU开销。按照作者给出的数据可以在数据全部在内存的情况下可以达到75W的QPS查询。总之,它对mysql数据库的操作比mysql本身的操作语句快很多。  适用场景

  • GROUP BY语句详解

    GROUP BY语句详解一、groupby的意思为分组汇总。使用了groupby后,要求Select出的结果字段都是可汇总的,否则就会出错。groupby有一个原则,就是select后面的所有列中,没有使用聚合函数的列,必须出现在groupby后面。比如,有:{学号,姓名,性别,年龄,成绩}字段这样写:SELECT学号,姓名,性别,年龄,sum(成绩)FROM学生表GROUPB…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号