文档章节

Bellman-Ford算法

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 780
阅读 6
收藏 0

概述:

Bellman - ford算法是求含负权图的单源最短路径算法,效率很低,但代码很容易写。其原理为持续地进行松弛(原文是这么写的,为什么要叫松弛,争议很大),在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。Bellman - ford算法有一个小优化:每次松弛先设一个标识flag,初值为FALSE,若有边更新则赋值为TRUE,最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间去做没有必要的松弛,而SPFA算法用队列进行了优化,效果十分显著,高效难以想象。SPFA还有SLF,LLL,滚动数组等优化。

介绍

Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权,在没有负权回路存在时(负权回路的含义是,回路的权值和为负。)即便有负权的边,也可以采用Bellman - Ford算法正确求出最短路径。
Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图 G=(V,E), 其源点为s,加权函数 w是 边集 E 的映射。对图G运行Bellman - Ford算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。

适用条件

1.单源最短路径(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
4.差分约束系统;

思想:

Bellman-Ford 算法描述:

1.创建源顶点 v 到图中所有顶点的距离的集合 distSet,为图中的所有顶点指定一个距离值,初始均为 Infinite,源顶点距离为 0;

2.计算最短路径,执行 V - 1 次遍历;

3.对于图中的每条边:如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d,则更新终点 v 的距离值 d;

4.检测图中是否有负权边形成了环,遍历图中的所有边,计算 u 至 v 的距离,如果对于 v 存在更小的距离,则说明存在环;

注意:

上面的最后一步用于检测闭环的存在

步骤:

这里写图片描述

检测步骤:

这里写图片描述

实例:

这里写图片描述
参考:
http://www.voidcn.com/blog/u010087886/article/p-4529113.html
http://baike.baidu.com/view/1712262.htm?fromtitle=Dijkstra%E7%AE%97%E6%B3%95&fromid=215612&type=syn
http://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
图算法-最小生成树之Bellman-ford

#include <iostream> include <map> include <vector> include <stdexcept> include <memory> namespace{ enum : int{ MAXVALUE = 9999 };} template<typename T>struct Node{ T key_; Node(......

SHIHUAMarryMe
2016/01/17
108
0
加权有向图----一般性单源最短路径问题(Bellman-Ford算法)

Dijkstra算法无法判断含负权边的图的最短路径,如果遇到负权,在没有负权回路(回路的权值和为负)存在时,可以采用Bellman - Ford算法正确求出最短路径。 当且仅当加权有向图中至少存在一条...

Superheros
2017/12/22
7
0
最短路径算法

单源最短路径问题 问题描述:给你一个顶点做源点,你想要知道,如何从源点到达其他所有点的最短路径。 OK,这个问题看起来没什么用。我们一般想知道的是A点到B点的最短路径,这个单源最短路径...

Hosee
2016/01/14
2.2K
0
加权有向图问题1--单源最短路径问题(Dijkstra算法和Bellman - Ford算法)

加权有向图实现 我们实现两个类,权重边类和有向图类。有向图类中组合权重边类来实现加权有向图。 权重边类实现: 加权有向图实现: Dijkstra算法 Dijkstra算法可以解决边的权重非负的最短路...

SuperHeroes
2017/12/21
0
0
HAWQ + MADlib 玩转数据挖掘之(十)——图算法之单源最短路径

一、图算法简介 1. 定义 在计算中,常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图,称为“算图”。计算时根据已知条件,从有关线段上一点开始,连结相关线段上的点,连线与表示...

wzy0623
2017/08/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux中shell if 判断总结

UNIX Shell 里面比较字符写法 -eq 等于; -ne 不等于; -gt 大于; -lt 小于 ; -le 小于等于; -ge 大于等于; -z 空串; -n 非空串; = 两个字符相等; != 两个字符不等 无论什么编程语言都离不开条...

linuxprobe16
26分钟前
0
0
我是如何将博客转成PDF的

前言 只有光头才能变强 之前有读者问过我:“3y你的博客有没有电子版的呀?我想要份电子版的”。我说:“没有啊,我没有弄过电子版的,我这边有个文章导航页面,你可以去文章导航去找来看呀”...

Java3y
29分钟前
1
0
nginx的一些总结

Linux下安装Nginx完整教程及常见错误解决方案 1.Nginx安装环境 Nginx是C语言开发,建议在linux上运行,本教程使用Centos7.0作为安装环境. 1)gcc 安装nginx需要先将官网下载的源码进行编译,编译...

Yao--靠自己
35分钟前
1
0
Predicate函数式接口

Predicate接口主要用于流的筛选,比如在filter方法中传入Predicate判断。 作为函数式接口,这里居然有三个default方法,一个static方法,子孙满堂! 正统的接口方法,就是boolean test(T t)...

woshixin
36分钟前
1
0
sql 开窗函数

开窗函数:在开窗函数出现之前存在着很多用 SQL 语句很难解决的问题,很多都要通过复杂的相关子查询或者存储过程来完成。为了解决这些问题,在 2003 年 ISO SQL 标准加入了开窗函数,开窗函数...

hblt-j
47分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部