最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)_bellman-ford算法的实现-程序员宅基地

技术标签: 算法  C++  

相关文章:

1.Dijkstra算法:

http://www.wutianqi.com/?p=1890

2.Floyd算法:

http://www.wutianqi.com/?p=1903

Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。这时候,就需要使用其他的算法来求解最短路径,Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。Bellman-Ford算法的流程如下:
给定图G(V, E)(其中V、E分别为图G的顶点集与边集),源点s,

  • 数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n]为, Distant[s]为0;
  •  
    以下操作循环执行至多n-1次,n为顶点数:
    对于每一条边e(u, v),如果Distant[u] + w(u, v) < Distant[v],则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值;
    若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;
  • 为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如果存在Distant[u] + w(u, v) < Distant[v]的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

可知,Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).

首先介绍一下松弛计算。如下图:


 

松弛计算之前,点B的值是8,但是点A的值加上边上的权重2,得到5,比点B的值(8)小,所以,点B的值减小为5。这个过程的意义是,找到了一条通向B点更短的路线,且该路线是先经过点A,然后通过权重为2的边,到达点B。
当然,如果出现一下情况


 

则不会修改点B的值,因为3+4>6。
 
Bellman-Ford算法可以大致分为三个部分
第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
第三,遍历途中所有的边(edge(u,v)),判断是否存在这样情况:
d(v) > d (u) + w(u,v)
则返回false,表示途中存在从源点可达的权为负的回路。
 
之所以需要第三部分的原因,是因为,如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。
考虑如下的图:
 

经过第一次遍历后,点B的值变为5,点C的值变为8,这时,注意权重为-10的边,这条边的存在,导致点A的值变为-2。(8+ -10=-2)
 
 

第二次遍历后,点B的值变为3,点C变为6,点A变为-4。正是因为有一条负边在回路中,导致每次遍历后,各个点的值不断变小。
 
在回过来看一下bellman-ford算法的第三部分,遍历所有边,检查是否存在d(v) > d (u) + w(u,v)。因为第二部分循环的次数是定长的,所以如果存在无法收敛的情况,则肯定能够在第三部分中检查出来。比如
 

此时,点A的值为-2,点B的值为5,边AB的权重为5,5 > -2 + 5. 检查出来这条边没有收敛。
 
所以,Bellman-Ford算法可以解决图中有权为负数的边的单源最短路径问。

个人感觉算法导论讲解很不错,把这一章贴出来和大家分享:

24.1 The Bellman-Ford algorithm

The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (VE) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.

The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(sv). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source.

BELLMAN-FORD(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  for i1 to |V[G]| - 1
3       do for each edge (u, v) ∈ E[G]
4              do RELAX(u, v, w)
5  for each edge (u, v) ∈ E[G]
6       do if d[v] > d[u] + w(u, v)
7             then return FALSE
8  return TRUE

Figure 24.4 shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the dand π values of all vertices in line 1, the algorithm makes |V| – 1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We’ll see a little later why this check works.)

(单击图片可以放大)

Figure 24.4: The execution of the Bellman-Ford algorithm. The source is vertex s. The d values are shown within the vertices, and shaded edges indicate predecessor values: if edge (u, v) is shaded, then π[v] = u. In this particular example, each pass relaxes the edges in the order (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y). (a) The situation just before the first pass over the edges. (b)-(e) The situation after each successive pass over the edges. The d and π values in part (e) are the final values. The Bellman-Ford algorithm returns TRUE in this example.

The Bellman-Ford algorithm runs in time O(V E), since the initialization in line 1 takes Θ(V) time, each of the |V| – 1 passes over the edges in lines 2-4 takes Θ(E) time, and the for loop of lines 5-7 takes O(E) time.

/*
* About:  Bellman-Ford算法
* Author: Tanky Woo
* Blog:   www.WuTianqi.com
*/
 
#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 99999;
 
// 边,
typedef struct Edge{
    int u, v;    // 起点,重点
    int weight;  // 边的权值
}Edge;
 
Edge edge[maxnum];     // 保存边的值
int  dist[maxnum];     // 结点到源点最小距离
 
int nodenum, edgenum, source;    // 结点数,边数,源点
 
// 初始化图
void init()
{
    // 输入结点数,边数,源点
    cin >> nodenum >> edgenum >> source;
    for(int i=1; i<=nodenum; ++i)
        dist[i] = maxint;
    dist[source] = 0;
    for(int i=1; i<=edgenum; ++i)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].weight;
        if(edge[i].u == source)          //注意这里设置初始情况
            dist[edge[i].v] = edge[i].weight;
    }
}
 
// 松弛计算
void relax(int u, int v, int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}
 
bool Bellman_Ford()
{
    for(int i=1; i<=nodenum-1; ++i)
        for(int j=1; j<=edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = 1;
    // 判断是否有负环路
    for(int i=1; i<=edgenum; ++i)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {
            flag = 0;
            break;
        }
    return flag;
}
int main()
{
    //freopen("input3.txt", "r", stdin);
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sinat_36412790/article/details/77721090

智能推荐

Android Material Design控件学习NavigationView和Toolbar使用_android toolbar navigation-程序员宅基地

文章浏览阅读394次。Google I/O 2015 给大家带来了Android Design Support Library,我们也可以到Android Design Support Library进行了解,下面介绍Toolbar的使用和NavigationView导航抽屉,而NavigationView的典型用途就是配合之前v4包的DrawerLayout,首先导入依赖包compile 'com.android_android toolbar navigation

FPGA初级篇①——LED的闪烁方式,FPGA新建工程,vivado使用。_fpga led闪烁-程序员宅基地

文章浏览阅读1.5k次,点赞3次,收藏12次。一、新建工程打开软件 VIVADO,选择第一个栏的Creat Project然后会出现 VIVADO 新建工程介绍,如下图所示,直接点击“Next”。此时会出现的是工程文件夹、工程名、顶层模块名设置界面,设置目录为:D:/...,设置完成后点击“Next”。选择RTL project在接下来的页面create file;下一个页面点next;再下一个根据FPGA版本选择(下图仅供参考),最后点Finish弹出界面(初始化代码的作用..._fpga led闪烁

SpringBoot实现token认证(基于缓存)_springboot中token存储到hashmap中-程序员宅基地

文章浏览阅读7.6k次,点赞3次,收藏40次。一、序言本博客基于SpringBoot,使用redis缓存实现token认证,来验证用户身份的合法性。二、什么是token?token意为令牌,为一个随机的字符串UUID生成,用来标记来访用户的身份,通过该token,可以得出是哪一个用户向我服务器访问资源。三、验证流程当用户登录成功之后,则向客户端发送token,用来标记该用户,以后每次用户向服务器访问时,则在请求头带上该to..._springboot中token存储到hashmap中

概率论总结_p(∪n i=1ai) ≤ pn i=1 p(ai)-程序员宅基地

文章浏览阅读823次,点赞2次,收藏13次。随机事件与概率基本概念随机试验试验可以在相同的条件下重复进行试验所有可能结果是明确可知道的,并且不止一个每一次试验会出现哪一个结果,事先并不确定事件随机事件A,B,C...A,B,C...A,B,C...必然事件Ω\OmegaΩ不可能事件∅\varnothing∅样本空间样本点:随机试验的每一个可能结果称为样本点,记为ω\omegaω样本空间:样本点的全体组成的集合称为样本空间,记为Ω\OmegaΩ基本事件:由一个样本点构成的事件称为基本事件随机事件AAA是由若干个基本_p(∪n i=1ai) ≤ pn i=1 p(ai)

Nuxt中使用Vuex(新版,简单入门)_nuxt vuex-程序员宅基地

文章浏览阅读8.5k次,点赞2次,收藏17次。1.前言因为我学的是后端开发,前端不是很厉害,如果有什么不对的地方请评论指出,谢谢!看这篇文章你需要对Vuex有一定的了解 官方链接做课设的时候使用到了Nuxt框架,需要做登录,也就结识了Vuex,其实以前就学过Vuex,但是一直不知道这个东西有什么优势,特点。这次我在实际使用中就用到了一个非常好用的特点,官方的解释如下:Vuex 的状态存储是响应式的。当 Vue 组件从 store ..._nuxt vuex

vue点击按钮改变按钮样式_vue点击按钮切换样式-程序员宅基地

文章浏览阅读3.7k次。【代码】vue点击按钮改变按钮样式。_vue点击按钮切换样式

随便推点

入会领京豆Python脚本_移动端领京豆脚本python-程序员宅基地

文章浏览阅读5.7k次,点赞4次,收藏29次。京东入会领京豆Python脚本代码地址:<AntonVanke/JDBrandMember: 京东自动入会获取京豆 (github.com)>_移动端领京豆脚本python

页框回收算法(PFRA)——2_bypfra-程序员宅基地

文章浏览阅读455次。页框回收中的反向映射PFRA的目的之一就是能释放共享页框,为了达到这个目的Linux2.6内核能够快速定位指向同一页框的所有页表项,这个过程就叫做反向映射。反向映射简单来说就是在页描述符中加入附加字段,这样就把某个页描述符它所确定的页框对应的全部页表项联接起来,但是这样的话一旦对该链表更新会有很大的开销。所有就有一种成熟的技术出现,Linux2.6就有叫做面向对象的反向映射的技术。实际上对于任何可以回收的用户态页面,内核保留系统中该页所在所有线性区(对象)的反向链接,每个线性区描述符存放一个指针指向一个_bypfra

JS_js数据导出excel文件_js 读取 .po文件 msgstr的值为空,就把msgstr对应的msgid,导出为xlsx文件-程序员宅基地

文章浏览阅读142次。<html> <head> <div>以Table格式导为xls文件 <button onclick='TableToExcel()'>导出</button></div> <div>导出CSV文件 <button onclick='toCSV()'>导出</button></div> <div>大量数据导出CSV <button oncli_js 读取 .po文件 msgstr的值为空,就把msgstr对应的msgid,导出为xlsx文件

如何创建一个镜像_创建镜像jx,请将代码写出来(或操作流程)-程序员宅基地

文章浏览阅读1.3k次。思路:基于官方下载的镜像,进行编辑步骤1:下载镜像docker pull或docker load&lt;hello-nginx.tar步骤2:运行镜像,得到容器docker run -d --name=容器名称 镜像名称步骤3:使用终端连接容器docker exec -it 容器名称 /bin/bash步骤4:在容器中运行命令,安装需要的软件 echo ‘hello’&gt;hello.t..._创建镜像jx,请将代码写出来(或操作流程)

BZOJ 2301 [HAOI2011]Problem b(莫比乌斯反演)_[bzoj2301][haoi2011]-程序员宅基地

文章浏览阅读139次。题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2301咱也不知道莫比乌斯函数,莫比乌斯反演怎么来的,直接用就得了...①莫比乌斯函数:else表示质因子分解后有质因子出现一次以上莫比乌斯函数跟着欧拉筛跑一遍就可以求出来②莫比乌斯反演的两种写法:其中f(i)是题目询问的东西,你发现直接求求..._[bzoj2301][haoi2011]

SpringBoot多文件压缩包下载(多附件zip格式)_springboot下载多个文件-程序员宅基地

文章浏览阅读7.4k次。文章目录前言 : 此 Demo 为 Windows 环境下演示,部署到服务器的话路径需改成服务器的路径。一、自定义工具类DownLoadZipUtil二、Dao层分析与sqlmapper层代码(DAO)三、Service层代码三、Controller层代码注意 : 文件的打包下载这里用到了临时路径,下面只需要关注方法ZipTempDownLoad即可,下面的代码实际需根据自己的逻辑需求去写。四、前端部分代码,此Demo前端用的vue五、效果展示前言 : 此 Demo 为 Windows 环境下演示,部_springboot下载多个文件

推荐文章

热门文章

相关标签