数据结构 —— 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);
		else
			cout << "存在负权回路" << 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代表无穷大

    // 设置源点到自身的距离为0
    dest[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;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

linux_进程概念——理解冯诺依曼体系结构

linux_进程概念——理解冯诺依曼体系结构

前言&#xff1a; 本篇内容是为了让友友们较好地理解进程的概念&#xff0c; 而在真正了解进行概念之前&#xff0c; 要先了解一下冯诺依曼体系结构。 所以博主会先对冯诺伊曼体系结构进行解释&#xff0c; 然后再讲解进程的概念。 ps&#xff1a; 本篇内容适合了解一些linux指…
阅读更多...
新兴市场游戏产业爆发 传音以技术抢抓机遇 ​

新兴市场游戏产业爆发 传音以技术抢抓机遇 ​

随着年轻人口的增加以及互联网的普及,非洲、中东等新兴市场正迎来游戏产业的大爆发,吸引着全球游戏企业玩家在此开疆辟土。中国出海企业代表传音以新兴市场需求为中心,秉持本地化创新理念不断加强游戏等关键领域技术攻关凭借移动终端设备为全球玩家带来极致游戏体验,收获了消费…
阅读更多...
变位齿轮的齿高好像不变

变位齿轮的齿高好像不变

通过这个软件的计算&#xff0c;变位尺寸的大小径都会同时变化&#xff0c;从而整个齿高好像没有变化。 下面百度答案
阅读更多...
文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《计及负荷时空特性的高速公路链式微网光-储-充容量优化配置方法》

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《计及负荷时空特性的高速公路链式微网光-储-充容量优化配置方法》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…
阅读更多...
【C++报错已解决】Invalid Use of Incomplete Type

【C++报错已解决】Invalid Use of Incomplete Type

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 引言&#xff1a;一、问题描述1.2 报错分析1.3 解决思路 二、解决方法2.1 方法一&#xff1a;完整类型定义2.2 方法二…
阅读更多...
【云岚到家】-day05-4-项目迁移-商品搜索

【云岚到家】-day05-4-项目迁移-商品搜索

【云岚到家】-day05-4-项目迁移-商品搜索 2 项目迁移-商品搜索2.1 迁移目标2.2 能力基础2.2.1 索引同步方案设计能力2.2.2 Elasticsearch全文检索应用能力 2.3 需求分析2.3.1 界面原型2.3.2 功能列表梳理 2.4 系统设计2.4.1 索引结构2.4.2 索引同步方案2.4.3 搜索自动补全2.4.4…
阅读更多...
Java---数组

Java---数组

乐观学习&#xff0c;乐观生活&#xff0c;才能不断前进啊&#xff01;&#xff01;&#xff01; 我的主页&#xff1a;optimistic_chen 我的专栏&#xff1a;c语言 欢迎大家访问~ 创作不易&#xff0c;大佬们点赞鼓励下吧~ 前言 无论c语言还是java数组都是重中之重&#xff0…
阅读更多...
解决keil调试遇到的hardlfault问题

解决keil调试遇到的hardlfault问题

在程序开发过程中遇到的程序死机问题 导致死机的原因&#xff1a;内存溢出&#xff0c;堆栈溢出&#xff0c;数组越界&#xff0c;中断错误。。。。。。 出现这个问题&#xff0c;首先查看线程的调度关系 看最后是在哪个位置死机&#xff0c;如果rt_current_thread在main_thre…
阅读更多...
视图库对接系列(GA-T 1400)十五、视图库对接系列(本级)删除、取消订阅

视图库对接系列(GA-T 1400)十五、视图库对接系列(本级)删除、取消订阅

说明 之前说了订阅和修改订阅，今天我们来实现删除和取消订阅二个接口。删除订阅 逻辑： 请求下级的接口成功我们就删除数据库的对应数据视图库接口定义 实现 service接口层 //删除订阅ResponseStatusListModeObject deleteSubscribes(String idList, HttpServletRequest re…
阅读更多...
MongoDB - 集合和文档的增删改查操作

MongoDB - 集合和文档的增删改查操作

文章目录 1. MongoDB 运行命令2. MongoDB CRUD操作1. 新增文档1. 新增单个文档 insertOne2. 批量新增文档 insertMany 2. 查询文档1. 查询所有文档2. 指定相等条件3. 使用查询操作符指定条件4. 指定逻辑操作符 (AND / OR) 3. 更新文档1. 更新操作符语法2. 更新单个文档 updateO…
阅读更多...
土壤分析仪：解密土壤之奥秘的科技先锋

土壤分析仪：解密土壤之奥秘的科技先锋

在农业生产和生态保护的道路上&#xff0c;土壤的质量与状况一直是我们关注的焦点。土壤分析仪&#xff0c;作为现代科技在农业和环保领域的杰出代表&#xff0c;以其高效、精准的分析能力&#xff0c;为我们揭示了土壤的奥秘&#xff0c;为农业生产提供了科学指导&#xff0c;…
阅读更多...
（Windows环境）FFMPEG编译，包含编译x264以及x265

（Windows环境）FFMPEG编译，包含编译x264以及x265

本文使用 MSYS2 来编译 ffmpeg 一、安装MSYS2 MSYS2 是 Windows 下的一组编译套件&#xff0c;它可以在 Windows 系统中模拟 Linux 下的编译环境&#xff0c;如使用 shell 运行命令、使用 pacman 安装软件包、使用 gcc (MinGW) 编译代码等。 MSYS2 的安装也非常省心&#x…
阅读更多...
深度探讨：无法恢复主文件表的困境与解救之道

深度探讨：无法恢复主文件表的困境与解救之道

在数据存储与管理的复杂世界中&#xff0c;主文件表&#xff08;Master File Table, MFT&#xff09;作为文件系统的核心组件&#xff0c;承载着至关重要的角色。一旦遭遇无法恢复主文件表的困境&#xff0c;用户将面临数据访问受限、文件丢失等严重后果。这通常是由于硬件故障…
阅读更多...
leetcode 1421 净现值查询(postgresql)

leetcode 1421 净现值查询(postgresql)

需求 表: NPV ---------------------- | Column Name | Type | ---------------------- | id | int | | year | int | | npv | int | ---------------------- (id, year) 是该表主键. 该表有每一笔存货的年份, id 和对应净现值的信息. 表: Queries ---------------------- …
阅读更多...
C语言 | Leetcode C语言题解之第227题基本计算题II

C语言 | Leetcode C语言题解之第227题基本计算题II

题目&#xff1a; 题解&#xff1a; int calculate(char* s) {int n strlen(s);int stk[n], top 0;char preSign ;int num 0;for (int i 0; i < n; i) {if (isdigit(s[i])) {num num * 10 (int)(s[i] - 0);}if (!isdigit(s[i]) && s[i] ! || i n - 1) {s…
阅读更多...
机器学习筑基篇，容器调用显卡计算资源，Ubuntu 24.04 快速安装 NVIDIA Container Toolkit！...

机器学习筑基篇，容器调用显卡计算资源，Ubuntu 24.04 快速安装 NVIDIA Container Toolkit！...

[ 知识是人生的灯塔，只有不断学习，才能照亮前行的道路 ] Ubuntu 24.04 安装 NVIDIA Container Toolkit 什么是 NVIDIA Container Toolkit? 描述：NVIDIA Container Toolkit(容器工具包)使用户能够构建和运行 GPU 加速的容器，该工具包括一个容器运行时库和实用程序，用于自动…
阅读更多...
Django项目创建的基本准备工作【4】

Django项目创建的基本准备工作【4】

【 一 】软件开发模式 官话下面 人话 瀑布开发就是将什东西都定义好了在进行开发对吧 敏捷就是进行模块化一样 分批进行 规定一个时间段完成什么样的功能。 总结来说&#xff0c;瀑布开发强调在项目开始之前进行详细的计划和准备&#xff0c;并按照预定的顺序逐步进行&#x…
阅读更多...
ScrapySharp框架：小红书视频数据采集的API集成与应用

ScrapySharp框架：小红书视频数据采集的API集成与应用

引言 随着大数据时代的到来&#xff0c;数据采集成为了互联网企业获取信息的重要手段。小红书作为一个集社交和电商于一体的平台&#xff0c;其丰富的用户生成内容&#xff08;UGC&#xff09;为数据采集提供了丰富的资源。本文将介绍如何使用ScrapySharp框架进行小红书视频数…
阅读更多...
aws sap认证考试如何轻松通过

aws sap认证考试如何轻松通过

如何高效备考AWS SAP (Solutions Architect Professional) 认证? AWS SAP认证是AWS认证体系中难度最高的认证之一,要通过这个考试确实需要下一番功夫。但通过合理规划和有效准备,你可以提高通过的几率。以下是一些建议: 评估起点 首先诚实地评估自己的AWS知识水平和实践经验。…
阅读更多...
科普文：Java对象在堆中的内存结构

科普文：Java对象在堆中的内存结构

概叙 今天来讲些抽象的东西 -- 对象头&#xff0c;因为我在学习的过程中发现很多地方都关联到了对象头的知识点&#xff0c;例如JDK中的 synchronized锁优化 和 JVM 中对象年龄升级等等。 对象内存构成# Java 中通过 new 关键字创建一个类的实例对象&#xff0c;对象存于内存的…
阅读更多...
最新文章

Copyright @ 2022~2023