Bellman-Ford求解带有负权图的单源最短路径问题

2023-10-22 15:10

本文主要是介绍Bellman-Ford求解带有负权图的单源最短路径问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文参考了书目《算法笔记》

 

 

对于一个图如果存在零环正环,利用Bellman-Ford算法不会影响到最短路径的求解;如果一个图出现了负环,则会导致恶性循环,会导致dis[u]出现负无穷,永远也求解不出来,但如果从源点出发,无法到达负环,则最短路径的求解不会收到影响(不在负环上的dis[u]可以求出确切值,在负环上的点v,标记dis[v]为不可达就行了)

 

下面是代码:

#include"stdafx.h"
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 500;
const int INF = 1e9;
int Vertexnum, Edgenum, Start;//顶点数、边数、起点
struct node {//结点结构体int v;int weight;
};
vector<node> adj[maxn];//邻接表存储图
int dis[maxn];
bool BellmanFord(int s) {//s为源点fill(dis, dis + maxn, INF);dis[s] = 0;for (int i = 0; i < Vertexnum - 1; i++) {//进行Vertexnum-1次松弛操作,以确保所有的点都松弛到最佳情况for (int u = 0; u < Vertexnum; u++) {//每轮操作都遍历所有的边for (int j = 0; j < adj[u].size(); j++) {int v = adj[u][j].v;int weight = adj[u][j].weight;if (dis[u] + weight < dis[v]) {dis[v] = dis[u] + weight;}}}}//已经松弛完毕,下面进行验证是否还能被松弛,如果还能被松弛,则说明此图存在负环for (int u = 0; u < Vertexnum; u++) {for (int j = 0; j < adj[u].size(); j++) {int v = adj[u][j].v;int weight = adj[u][j].weight;if (dis[u] + weight < dis[v]) {//如果还能被松弛return false;//则此图存在负环,返回false}}}return true;//数组d的所有值已经达到最优
}
int main() {cin >> Vertexnum >> Edgenum >> Start;int start, end, weight;//起点、终点、边权for (int i = 0; i < Edgenum; i++) {cin >> start >> end >> weight;node N;N.v = end;N.weight = weight;adj[start].push_back(N);}bool flag = BellmanFord(Start);if (flag == false) cout << "此图存在负环";else {for (int i = 0; i < Vertexnum; i++) {cout << dis[i] << " ";}}return 0;
}

分析:Bellman-Ford算法需要遍历所有的边,显然使用邻接表会比较方便,时间复杂度为O(VE),但如果使用邻接矩阵,会使时间复杂度达到O(V的三次方)。时间复杂度O(VE)难免有些高,下节将对Bellman-Ford算法进行优化(即SPFA算法)

思路:可以把源点s作为一棵树的根结点,把其它结点按照最短路径的结点顺序连接,就会生成一棵最短路径树。在短路径树中,从源点(根结点)s到达其余各顶点的路径就是原图中对应的最短路径,且原图和源点一旦确定,最短路径树也就确定了。由于在初始状态下dis[s]为0,因此在接下来的步骤中dis[s]不会被改变(也就是说最短路径树中的第一层的dis值被确定),接着,通过Bellman-Ford算法的第一轮操作之后,最短路径树中的第二层顶点的dis值也会被确定下来,然后进行第二轮操作,于是第三层顶点的dis值也被确定下来,这样计算直到最后一层顶点dis值确定,由于最短路径树的层数不超过V层,因此Bellman-Ford算法的松弛操作不会超过V-1轮

 

 

 

 

转:

 

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算法可以解决图中有权为负数的边的单源最短路径问。

以下是Bellman-Ford代码:

 

/*
* 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)//对边edge(u,v)进行松弛
{if(dist[v] > dist[u] + weight)dist[v] = dist[u] + weight;
}bool Bellman_Ford()
{for(int i=1; i<=nodenum-1; ++i)//执行nodenum-1轮松弛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;
}

补充:
考虑:为什么要循环V-1次? (V为顶点数)
答:因为最短路径肯定是个简单路径,不可能包含回路的,
如果包含回路,且回路的权值和为正的,那么去掉这个回路,可以得到更短的路径
如果回路的权值是负的,那么肯定没有解了

图有n个点,又不能有回路
所以最短路径最多n-1边

 

又因为每次循环,至少relax一边
所以最多n-1次就行了

 

 

 

个人补充:(循环n-1轮操作)

 

第一轮:对所有的边进行松弛操作,在这些松弛了的边里面,肯定能有一边已经松弛到最佳状态(其实是至少有一边)

 

第二轮:由于第一轮松弛,有一边(这里假设边的终点为u)已经松弛到最佳,那么就有可能导致从u出发使得:dis[u]+weight[u,v]<dis[v];(和dijkstra算法的思想一样—),那么就令dis[v]=dis[u]+weight[u,v],这就使得从u出发到达v的这条边松弛到了最佳

 

第三轮:,,,

 

 

,,,

(连锁反应)

 

 

 

 

 

 

这篇关于Bellman-Ford求解带有负权图的单源最短路径问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/262225

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)