文档章节

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

没有更多内容

加载失败,请刷新页面

加载更多

枚举 创建/获取key,name,list

创建枚举 public enum MessageTypeEnum { // 类型:0.一般消息,1.公告消息,2交易消息,3.活动消息,4.其他消息 type_general("一般消息", "0"), type_ann("公告消息", "1")......

龘游戏人生龘
12分钟前
0
0
Linus 本尊来了!为什么 KubeCon 越来越火?

阿里妹导读: 从200人的小会议到3500 多位云原生和开源领域工程师齐聚一堂的大会,KubeCon 只用了四年,昨天,在KubeCon China 2019 上阿里巴巴宣布开源 OpenKruise,今天,Linus 本尊竟然现...

阿里云云栖社区
48分钟前
3
0
五小时构建云原生电商平台 | KubeCon SOFAStack Workshop 详解

本文根据 KubeCon China 2019 同场活动 SOFAStack Cloud Native Workshop 内容整理, 文末包含文档、PPT 地址,欢迎试用和提出建议。 2019 年 6 月 25 日,在 KubeCon China 2019,全球知名开...

SOFAStack
49分钟前
6
0
跨平台开发框架DevExtreme v19.1.4正式发布|附下载

DevExtreme Complete Subscription是性能最优的 HTML5,CSS 和 JavaScript 移动、Web开发框架,可以直接在Visual Studio集成开发环境,构建iOS,Android,Tizen和Windows Phone 8应用程序。D...

FILA6666
50分钟前
2
0
数据库链接断开 Cause: com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure

报错信息如下: Cause: com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failureThe last packet successfully received from the server was 97,130 mill......

为了美好的明天
57分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部