数据结构 —— BellmanFord算法

数据结构 —— BellmanFord算法

  • BellmanFord算法
  • 检测负权值环
  • BellmanFord和Dijkstra思想上的区别
      • Dijkstra算法的思想
      • Bellman-Ford算法的思想
      • 思想上的对比

我们今天来看一个算法BellmanFord算法，我们之前的Dijkstra算法只能用来解决正权图的单源最短路径问题。

Bellman-Ford算法是一种用于计算单源最短路径问题的算法，也就是说，它能找出一个图中某个特定顶点到所有其他顶点的最短路径。与Dijkstra算法不同，Bellman-Ford算法可以处理含有负权边的图，但不能处理包含负权环的图（因为从源点到包含负权环的任意点的距离可以无限减小）。

以下是Bellman-Ford算法的基本步骤：

  1. 初始化：将源点到自身的距离设为0，源点到其他所有顶点的距离设为无穷大。
  2. 放松操作：对图中的每条边进行V-1次放松操作，其中V是顶点的数量。在每次放松操作中，对于每条边(u, v)，如果dist[v] > dist[u] + weight(u, v)，则更新dist[v] = dist[u] + weight(u, v)。其中，dist[v]表示源点到v的当前最短路径长度，weight(u, v)表示边(u, v)的权重。
  3. 检测负权环：再进行一次边的放松操作。如果此时仍存在某条边(u, v)满足dist[v] > dist[u] + weight(u, v)，则说明图中存在负权环。

我们先构建一个这样的图：
在这里插入图片描述在这里插入图片描述

BellmanFord算法

BellmanFord算法是站在全局的角度来思考问题，如果这条边可以通过另一条边得到一个更小的结果，就更新，基于这样的思想，我们可以暴力循环来解决：

		bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath){//结点转化size_t srcIndex = FindSrci(srci);parentPath.resize(_vertex.size(), -1);dest.resize(_vertex.size(), MAX_W);dest[srcIndex] = W();for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){if (_matrix[i][j] != MAX_W &&dest[j] > _matrix[i][j] + dest[i]){dest[j] = _matrix[i][j] + dest[i];parentPath[j] = i;}}}return true;}

	void TestGraphBellmanFord(){const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 6);g.AddEdge('s', 'y', 7);g.AddEdge('y', 'z', 9);g.AddEdge('y', 'x', -3);g.AddEdge('z', 's', 2);g.AddEdge('z', 'x', 7);g.AddEdge('t', 'x', 5);g.AddEdge('t', 'y', 8);g.AddEdge('t', 'z', -4);g.AddEdge('x', 't', -2);g.Print();vector<int> dist;vector<int> parentPath;g.BellmanFord('s', dist, parentPath);g.PrintShortestPath('s', dist, parentPath);}

在这里插入图片描述

我们发现路径是对的，但是权值不对：
在这里插入图片描述
这是为什么呢？我们把选边过程挑出来：

bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath){//结点转化size_t srcIndex = FindSrci(srci);parentPath.resize(_vertex.size(), -1);dest.resize(_vertex.size(), MAX_W);dest[srcIndex] = W();cout << "开始选边: " << endl;for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){if (_matrix[i][j] != MAX_W &&dest[j] > _matrix[i][j] + dest[i]){cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]<< endl;dest[j] = _matrix[i][j] + dest[i];parentPath[j] = i;}}}return true;}

在这里插入图片描述

问题就出在这两个地方：
在这里插入图片描述

在这里插入图片描述
我们之后的结果会对之前的结果有影响，所以我们还有套一层循环来保证我们的每条边都进行了更新：

			for (size_t k = 0; k < _vertex.size(); k++){for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){if (_matrix[i][j] != MAX_W &&dest[j] > _matrix[i][j] + dest[i]){cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]<< endl;dest[j] = _matrix[i][j] + dest[i];parentPath[j] = i;}}}}cout << endl;return true;}

在这里插入图片描述
这下权值就是对的，但是在更新过程中有些边是不用更新的，所以我们可以设计一个标志位来提高效率：

		bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath){//结点转化size_t srcIndex = FindSrci(srci);parentPath.resize(_vertex.size(), -1);dest.resize(_vertex.size(), MAX_W);dest[srcIndex] = W();for (size_t k = 0; k < _vertex.size(); k++){bool exchange = false;cout << "开始选边: " << endl;for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){if (_matrix[i][j] != MAX_W &&dest[j] > _matrix[i][j] + dest[i]){cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]<< endl;dest[j] = _matrix[i][j] + dest[i];parentPath[j] = i;exchange = true;}}}if (exchange == false){break;}}cout << endl;return true;}

在这里插入图片描述

检测负权值环

如果这个图中有负权值环就会导致距离可以无限减小：
在这里插入图片描述
所以我们的还有能力检测负权值环：

		bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath){//结点转化size_t srcIndex = FindSrci(srci);parentPath.resize(_vertex.size(), -1);dest.resize(_vertex.size(), MAX_W);dest[srcIndex] = W();for (size_t k = 0; k < _vertex.size(); k++){bool exchange = false;cout << "开始选边: " << endl;for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){if (_matrix[i][j] != MAX_W &&dest[j] > _matrix[i][j] + dest[i]){cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]<< endl;dest[j] = _matrix[i][j] + dest[i];parentPath[j] = i;exchange = true;}}}if (exchange == false){break;}}for (size_t i = 0; i < _vertex.size(); ++i){for (size_t j = 0; j < _vertex.size(); ++j){// 检查有没有负权回路if (_matrix[i][j] != MAX_W&& dest[i] + _matrix[i][j] < dest[j]){return false;}}}return true;}

我们这里举个例子：

	void TestGraphBellmanFord(){const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 6);g.AddEdge('s', 'y', 7);g.AddEdge('y', 'z', 9);g.AddEdge('y', 'x', -3);g.AddEdge('z', 's', 2);g.AddEdge('z', 'x', 7);g.AddEdge('t', 'x', 5);g.AddEdge('t', 'y', -8); //修改g.AddEdge('t', 'z', -4);g.AddEdge('x', 't', -2);g.AddEdge('y', 's', 1); // 新增g.Print();vector<int> dist;vector<int> parentPath;if(g.BellmanFord('s', dist, parentPath))g.PrintShortestPath('s', dist, parentPath);elsecout << "存在负权回路" << endl;}

在这里插入图片描述

BellmanFord和Dijkstra思想上的区别

Bellman-Ford算法和Dijkstra算法在思想上的主要区别在于它们处理最短路径问题的方式以及它们对图中边权重的假设。下面详细解释这两种算法在思想上的差异：

Dijkstra算法的思想

Dijkstra算法基于贪心策略，它维护一个顶点集合S，其中包含了已经确定了从源点到这些顶点的最短路径的所有顶点。算法的核心思想是每次从未确定最短路径的顶点中选取距离源点最近的那个顶点加入集合S，并更新与之相邻的顶点的距离。

  1. 初始化：从源点开始，将其距离设为0，其他所有顶点的距离设为无穷大。
  2. 迭代过程：每次迭代选择未被访问过的、距离源点最近的顶点u，将u标记为已访问（加入S集合），并尝试通过u更新其所有未访问邻居的距离。如果通过u到达邻居v的总距离小于v当前记录的距离，则更新v的距离。
  3. 终止条件：当所有顶点都被访问过，或者当前最小距离的顶点距离为无穷大时，算法结束。

Bellman-Ford算法的思想

Bellman-Ford算法则采用了动态规划的思想，它通过逐步松弛所有的边，来逼近最短路径的正确解。算法的核心是重复执行“松弛”操作，直到不再有路径可以改进为止。

  1. 初始化：同样地，从源点开始，将其距离设为0，其他所有顶点的距离设为无穷大。
  2. 松弛操作：算法会遍历图中的所有边多次，每次遍历都尝试通过边的两端点更新路径距离。如果通过某条边可以得到更短的路径，就更新这条路径的距离。这个过程会重复V-1次（V为顶点数量），因为在任何无环图中，从源点到任意顶点的最短路径至多包含V-1条边。
  3. 负权重循环检测：在进行了V-1轮的松弛操作后，如果再次遍历所有边时还能进一步更新某个顶点的距离，那就意味着图中存在负权重循环。

思想上的对比

  • 适应性：Dijkstra算法假设所有边的权重都是非负的，而Bellman-Ford算法可以处理负权重边（只要不存在负权重循环）。
  • 效率：Dijkstra算法在处理无负权重边的图时通常比Bellman-Ford算法更高效，尤其是在使用优先队列优化的情况下。
  • 动态规划vs贪心策略：Bellman-Ford算法通过重复松弛所有边来逐渐逼近最短路径，体现了动态规划的思想；而Dijkstra算法通过每次选择局部最优解来逐步构建全局最优解，体现了贪心策略。

总体来说，Dijkstra算法和Bellman-Ford算法各自适用于不同的场景，选择哪个算法取决于图的特性和你对时间和空间效率的需求。

附上源码：

bool BellmanFord(const V& srci, vector<W>& dest, vector<int>& parentPath)
{// 将源点名称转换为其在顶点列表中的索引size_t srcIndex = FindSrci(srci);// 初始化parentPath向量，用于存储最短路径上的前驱顶点parentPath.resize(_vertex.size(), -1);// 初始化dest向量，用于存储源点到各顶点的最短距离dest.resize(_vertex.size(), MAX_W); // MAX_W代表无穷大// 设置源点到自身的距离为0dest[srcIndex] = W(); // W()应为权重类型的默认构造函数，通常为0// 开始Bellman-Ford算法的V-1轮松弛操作for (size_t k = 0; k < _vertex.size(); k++){bool exchange = false; // 用于检测本轮是否有路径更新cout << "开始选边: " << endl;// 遍历图中所有的边for (size_t i = 0; i < _vertex.size(); i++){for (size_t j = 0; j < _vertex.size(); j++){// 如果边(i, j)存在且通过边(i, j)可以得到更短的路径if (_matrix[i][j] != MAX_W && dest[j] > _matrix[i][j] + dest[i]){cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j]<< endl; // 输出更新的边信息dest[j] = _matrix[i][j] + dest[i]; // 更新dest[j]的值parentPath[j] = i; // 更新parentPath[j]，记录前驱顶点exchange = true; // 标记发生了路径更新}}}// 如果一轮迭代中没有发生路径更新，则提前退出循环if (exchange == false){break;}}// 检查是否存在负权重循环for (size_t i = 0; i < _vertex.size(); ++i){for (size_t j = 0; j < _vertex.size(); ++j){// 如果通过边(i, j)可以进一步缩短路径，说明存在负权重循环if (_matrix[i][j] != MAX_W &&dest[i] + _matrix[i][j] < dest[j]){return false;}}}// 如果没有发现负权重循环，返回true，表示算法成功return true;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/375275.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

06浅谈大语言模型可调节参数TopP和TopK

06浅谈大语言模型可调节参数TopP和TopK

浅谈大模型参数TopP和TopK 大语言模型中的temperature、top_p和top_k参数是用来控制模型生成文本时的随机性和创造性的。下面分享一下topP和topK两个参数的意义及逻辑&#xff1b; top K&#xff08;Top-K Sampling&#xff09; 作用&#xff1a;只从模型认为最可能的k个词中选…
阅读更多...
Nodejs 第八十四章（ElasticSearch搜索）

Nodejs 第八十四章（ElasticSearch搜索）

ElasticSearch基本用法在之前的篇章介绍过了 这里不在过多阐述 模拟假数据 安装库 faker-js/faker 模拟假数据的一个库非常好用支持中文使用中文 locale: [zh_CN], 设置即可生成名字&#xff0c;邮箱&#xff0c;手机号&#xff0c;id&#xff0c;年龄&#xff0c;性别生成完成…
阅读更多...
Python功能制作之获取CSDN所有发布文章的对应数据

Python功能制作之获取CSDN所有发布文章的对应数据

大家好&#xff0c;今天我要分享的是一个实用的Python脚本&#xff0c;它可以帮助你批量获取CSDN博客上所有发布文章的相关数据&#xff0c;并将这些数据保存到Excel文件中。此外&#xff0c;脚本还会为每篇文章获取一个质量分&#xff0c;并将这个分数也记录在Excel中。让我们…
阅读更多...
LLM-阿里云 DashVector + ModelScope 多模态向量化实时文本搜图实战总结

LLM-阿里云 DashVector + ModelScope 多模态向量化实时文本搜图实战总结

文章目录 前言步骤图片数据Embedding入库文本检索 完整代码 前言 本文使用阿里云的向量检索服务&#xff08;DashVector&#xff09;&#xff0c;结合 ONE-PEACE多模态模型&#xff0c;构建实时的“文本搜图片”的多模态检索能力。整体流程如下&#xff1a; 多模态数据Embedd…
阅读更多...
HTML5新增的input元素类型：number、range、email、color、date等

HTML5新增的input元素类型：number、range、email、color、date等

HTML5 大幅度地增加与改良了 input 元素的种类&#xff0c;可以简单地使用这些元素来实现 HTML5 之前需要使用 JavaScript 才能实现的许多功能。 到目前为止&#xff0c;大部分浏览器都支持 input 元素的种类。对于不支持新增 input 元素的浏览器&#xff0c;input 元素被统一…
阅读更多...
采购订单列表根据条件设置行背景色

采购订单列表根据条件设置行背景色

文章目录 采购订单列表根据条件设置行背景色Python实现Bos配置实现-列表条件格式化 采购订单列表根据条件设置行背景色 Python实现 python脚本 import clr clr.AddReference(System) clr.AddReference(Kingdee.BOS) clr.AddReference(Kingdee.BOS.Core) clr.AddReference(Sy…
阅读更多...
spark shuffle写操作——SortShuffleWriter

spark shuffle写操作——SortShuffleWriter

写入的简单流程&#xff1a; 1.生成ExternalSorter对象 2.将消息都是插入ExternalSorter对象中 3.获取到mapOutputWriter&#xff0c;将中间产生的临时文件合并到一个临时文件 4.生成最后的data文件和index文件 可以看到写入的重点类是ExternalSorter对象 ExternalSorter 基…
阅读更多...
高创新 | CEEMDAN-VMD-GRU-Attention双重分解+门控循环单元+注意力机制多元时间序列预测

高创新 | CEEMDAN-VMD-GRU-Attention双重分解+门控循环单元+注意力机制多元时间序列预测

目录 效果一览基本介绍模型设计程序设计参考资料 效果一览 基本介绍 高创新 | CEEMDAN-VMD-GRU-Attention双重分解门控循环单元注意力机制多元时间序列预测 本文提出一种基于CEEMDAN 的二次分解方法&#xff0c;通过样本熵重构CEEMDAN 分解后的序列&#xff0c;复杂序列通过VMD…
阅读更多...
算法日常练习

算法日常练习

对于这个题&#xff0c;如何处理同一个方向的问题&#xff0c;且对于同一组的如果间隔太大如何实现离散化 #include<bits/stdc.h> using namespace std;#define int long long typedef long long ll; map<pair<int,int>,vector<pair<ll,ll>>> mp…
阅读更多...
小程序做自定义分享封面图，Canvas base64图片数据真机上不显示？【已解决】

小程序做自定义分享封面图，Canvas base64图片数据真机上不显示？【已解决】

首选说一下需求&#xff0c;做一个小程序分享&#xff0c;但是封面图要自定义&#xff0c;除了要有对应商品还有有背景图&#xff0c;商品名。类似这种 实现逻辑&#xff0c;把商品图和背景图&#xff0c;再加上价格和商品名用canvas 渲染出来 这是弄好之后的效果图&#xff0…
阅读更多...
【简历】兰州某大学一本硕士：面试通过率基本是为0

【简历】兰州某大学一本硕士：面试通过率基本是为0

注&#xff1a;为保证用户信息安全&#xff0c;姓名和学校等信息已经进行同层次变更&#xff0c;内容部分细节也进行了部分隐藏 简历说明 这是一个一本硕士的Java简历&#xff0c;那这个简历因为学校本身&#xff0c;它是一个一本的硕士&#xff0c;我们一般认为这一本硕士&a…
阅读更多...
Riscv 架构的合规测试

Riscv 架构的合规测试

为啥直接关注riscv-arch-test&#xff0c;是因为RISCOF 测试框架使用的是riscv-arch-test 1. The architectural test 架构测试是一个单一的测试&#xff0c;代表了可编译和运行的最小测试代码。它是用汇编代码编写的&#xff0c;其产品是test signature。一个架构测试可能由…
阅读更多...
体育资讯小程序的设计

体育资讯小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;球员管理&#xff0c;教练管理&#xff0c;赛事日程管理&#xff0c;赛事类型管理&#xff0c;联赛积分榜管理 开发系统&#xff1a;Windows 架构模式&#xff1a;SSM JDK版本&am…
阅读更多...
【前端项目笔记】10 项目优化上线

【前端项目笔记】10 项目优化上线

项目优化上线 目标&#xff1a;优化Vue项目部署Vue项目&#xff08;上线提供使用&#xff09; 项目优化 项目优化策略&#xff1a; 生成打包报告&#xff1a;根据生成的报告发现问题并解决第三方库启用CDN&#xff1a;提高首屏页面的加载效率Element-UI组件按需加载路由懒加…
阅读更多...
java算法day12

java算法day12

java算法day12 199二叉树的右视图637二叉树的层平均值515 在每个树行中找最大值429 N叉树的层序遍历116 填充每个节点的下一个右侧节点指针 199 二叉树的右视图 这题还是层序遍历的板子&#xff0c;但是在处理上略有差异 这个题我一开始的想法就有误&#xff0c;因为我一开始…
阅读更多...
通过手机供网、可修改WIFI_MAC的网络设备

通过手机供网、可修改WIFI_MAC的网络设备

一、修改WIFI mac&#xff08;bssid&#xff09; 取一根网线&#xff0c;一头连着设备黄色网口、一头连着电脑按住设备reset按键&#xff0c;插入电源线&#xff0c;观察到蓝灯闪烁后再松开reset按键 打开电脑浏览器&#xff0c;进入192.168.1.1&#xff0c;选择“MAC 地址修改…
阅读更多...
彻底开源，免费商用，上海AI实验室把大模型门槛打下来

彻底开源，免费商用，上海AI实验室把大模型门槛打下来

终于&#xff0c;业内迎来了首个全链条大模型开源体系。 大模型领域&#xff0c;有人探索前沿技术&#xff0c;有人在加速落地&#xff0c;也有人正在推动整个社区进步。 就在近日&#xff0c;AI 社区迎来首个统一的全链条贯穿的大模型开源体系。 虽然社区有LLaMA等影响力较大…
阅读更多...
uniapp实现光标闪烁（配合自己的键盘）

uniapp实现光标闪烁（配合自己的键盘）

前言 因为公司业务需要&#xff0c;所以我们... 演示 其实就是Chat自动打字效果 代码 键盘请看这篇文件 <template> <view class"list"><view class"title"><text>手机号码</text></view><view class"ty…
阅读更多...
C#使用异步方式调用同步方法的实现方法

C#使用异步方式调用同步方法的实现方法

使用异步方式调用同步方法&#xff0c;在此我们使用异步编程模型&#xff08;APM&#xff09;实现 1、定义异步委托和测试方法 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.Threading.Task…
阅读更多...
centos安装数据库同步工具sqoop并导入数据,导出数据,添加定时任务

centos安装数据库同步工具sqoop并导入数据,导出数据,添加定时任务

目录 1.安装jdk 1.1上传jdk安装包到/opt目录下并解压 1.2解压 1.3配置环境变量 2.安装hadoop 2.1.下载hadoop 2.2.解压hadoop 2.3配置环境变量 3.安装sqoop 3.1下载 3.2解压 3.3下载依赖包并复制到指定位置 3.3.1下载commons-lang-2.6-bin.tar.gz 3.3.2将mysql-c…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023