【代码随想录训练营第42期 Day60打卡 - 图论Part10 - Bellman_ford算法系列运用

目录

一、Bellman_ford算法的应用

二、题目与题解

题目一:卡码网 94. 城市间货物运输 I

题目链接

题解:队列优化Bellman-Ford算法(SPFA)

题目二:卡码网 95. 城市间货物运输 II

题目链接

题解: 队列优化Bellman-Ford算法(SPFA)

题目三:卡码网 96. 城市间货物运输 III

题目链接

题解: Bellman-Ford算法

 三、小结


一、Bellman_ford算法的应用

Bellman-Ford算法是一种用于解决单源最短路径问题的算法,它能够处理含有负权边的图,并且能够检测图中是否存在负权回路

其应用一般分为以下几个方面:

1、最短路径问题:在图论中,Bellman - Ford算法是解决单源最短路径问题的有效工具。它可以找到从一个顶点到所有其他顶点的最短路径。

2、负权边:与Dijkstra算法不同,Bellman - Ford算法能够处理含有负权边的图。这意味着它可以解决那些包含负权重边的图的最短路径问题。

3、运输问题:在运输问题中,需要找到从一个供应点(源)到多个需求点(汇)的最小成本运输路径。Bellman - Ford算法可以用来解决这个问题,尤其是在存在负权边的情况下。

4、流网络问题:在流网络中,Bellman - Ford算法可以用来找到从一个节点到另一个节点的最大流。这是因为在某些流网络问题中,边的权重可以表示为流量的限制。

5、网络流问题:在网络流问题中,Bellman - Ford算法可以用来找到从一个源点到汇点的最小费用流。这涉及到在网络中传输物质或信息,并需要最小化成本。

6、动态最短路径问题:在某些情况下,图的结构可能会发生变化,例如添加或删除边。Bellman - Ford算法可以用来动态地更新最短路径信息。

7、多源最短路径问题:Bellman - Ford算法可以扩展为解决多源最短路径问题,即找到多个源点到其他所有顶点的最短路径。

8、网络路由问题:在网络路由问题中,需要找到从一个网络节点到另一个网络节点的最佳路径。Bellman - Ford算法可以用来解决包含负权边的网络路由问题。

Bellman-Ford算法的主要优点是它能够处理负权边,这是其他最短路径算法(如Dijkstra算法)所不能做到的。然而,它的主要缺点是时间复杂度较高,为O(VE),其中V是顶点数,E是边数。在实际应用中,如果图中的边数远大于顶点数,Bellman-Ford算法可能不如Dijkstra算法高效。 

二、题目与题解

题目一:卡码网 94. 城市间货物运输 I

题目链接

94. 城市间货物运输 I (kamacoder.com)

题目描述

某国为促进城市间经济交流,决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。

网络中的道路都有各自的运输成本和政府补贴,道路的权值计算方式为:运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用;权值为负则表示政府的补贴超过了支出的运输成本,实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中,综合政府补贴后的最低运输成本。如果最低运输成本是一个负数,它表示在遵循最优路径的情况下,运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况,同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数,第一个正整数 n 表示该国一共有 n 个城市,第二个整数 m 表示这些城市中共有 m 条道路。 

接下来为 m 行,每行包括三个整数,s、t 和 v,表示 s 号城市运输货物到达 t 号城市,道路权值为 v (单向图)。

输出描述

如果能够从城市 1 到连通到城市 n, 请输出一个整数,表示运输成本。如果该整数是负数,则表示实现了盈利。如果从城市 1 没有路径可达城市 n,请输出 "unconnected"。

输入示例

6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5

输出示例

1

提示信息

示例中最佳路径是从 1 -> 2 -> 5 -> 6,路上的权值分别为 1 2 -2,最终的最低运输成本为 1 + 2 + (-2) = 1。

示例 2:

4 2
1 2 -1
3 4 -1

在此示例中,无法找到一条路径从 1 通往 4,所以此时应该输出 "unconnected"。

数据范围:

1 <= n <= 1000;
1 <= m <= 10000;

-100 <= v <= 100;

题解:队列优化Bellman-Ford算法(SPFA)

这题在昨天的打卡中已经有提到一般实现的Bellman-Ford算法,今天这里将用队列优化后的Bellman-Ford算法进行实现。

Bellman - Ford算法实现

1、创建一个队列q,先将源点加入队列。

2、进入循环,当队列非空时,继续执行以下操作:

         (1)从队列中取出队头节点node;

         (2)标记该节点已从队列中取出;

         (3)遍历当前节点的所有邻接边:

                 a.如果通过当前节点到达邻接节点的距离更短,则更新最短距离;

                 b.如果邻接节点不在队列中,则将其加入队列,并标记为已加入。

完整代码如下:

#include <bits/stdc++.h>
using namespace std;struct Edge // 邻接表
{int to;                               // 边的指向节点(边链接的节点 -- 邻接节点)int val;                              // 边的权重Edge(int t, int w) : to(t), val(w) {} // 构造函数,初始化边的指向节点和权重
};int main()
{int n, m, p1, p2, val;cin >> n >> m;vector<list<Edge>> grid(n + 1); // 创建一个邻接表,存储图的信息,大小为n+1,因为节点编号从1开始vector<bool> inQueue(n + 1); // 用于标记节点是否已经在队列中(避免重复添加)// 将所有边保存起来,构建邻接表for (int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1].push_back(Edge(p2, val)); // p1指向p2,边权重为val,将边添加到邻接表中}int start = 1; // 起点int end = n;   // 终点vector<int> minDist(n + 1, INT_MAX); // 初始化最短距离数组,所有节点到源点的最短距离初始为无穷大minDist[start] = 0;                  // (除外)源点到自己的距离为0// 队列优化Bellman-Ford算法queue<int> q;q.push(start);  //先将起点加入队列while (!q.empty()){int node = q.front(); // 取出队头节点 -- 作为后续邻接边的起始节点q.pop();inQueue[node] = false; // 标记该节点已从队列中取出// 遍历当前节点的所有邻接边 -- 当前节点即是这些边的起始节点for (Edge edge : grid[node]){int from = node;int to = edge.to;int value = edge.val;if (minDist[to] > minDist[from] + value) // 开始松弛:如果通过当前节点到达邻接节点to的距离更短,则更新邻接节点to到源点的最短距离{ minDist[to] = minDist[from] + value;if (inQueue[to] == false) // 如果该节点不在队列中,则加入队列,并标记为已加入{ q.push(to);inQueue[to] = true;}}}}if (minDist[end] == INT_MAX)cout << "unconnected" << endl; // 不能到达终点elsecout << minDist[end] << endl; // 到达终点最短路径
}

题目二:卡码网 95. 城市间货物运输 II

题目链接

95. 城市间货物运输 II (kamacoder.com)

题目描述

某国为促进城市间经济交流,决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。

网络中的道路都有各自的运输成本和政府补贴,道路的权值计算方式为:运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用;权值为负则表示政府的补贴超过了支出的运输成本,实际表现为运输过程中还能赚取一定的收益。

然而,在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时,存在一种情况:图中可能出现负权回路。负权回路是指一系列道路的总权值为负,这样的回路使得通过反复经过回路中的道路,理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴,算法还需检测这种特殊情况。

请找出从城市 1 到城市 n 的所有可能路径中,综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

城市 1 到城市 n 之间可能会出现没有路径的情况

输入描述

第一行包含两个正整数,第一个正整数 n 表示该国一共有 n 个城市,第二个整数 m 表示这些城市中共有 m 条道路。 

接下来为 m 行,每行包括三个整数,s、t 和 v,表示 s 号城市运输货物到达 t 号城市,道路权值为 v。

输出描述

如果没有发现负权回路,则输出一个整数,表示从城市 1 到城市 n 的最低运输成本(包括政府补贴)。如果该整数是负数,则表示实现了盈利。如果发现了负权回路的存在,则输出 "circle"。如果从城市 1 无法到达城市 n,则输出 "unconnected"。

输入示例

4 4
1 2 -1
2 3 1
3 1 -1 
3 4 1

输出示例

circle

提示信息

路径中存在负权回路,从 1 -> 2 -> 3 -> 1,总权值为 -1,理论上货物运输商可以在该回路无限循环赚取政府补贴,所以输出 "circle" 表示已经检测出了该种情况。

数据范围:

1 <= n <= 1000;
1 <= m <= 10000;

-100 <= v <= 100;

题解: 队列优化Bellman-Ford算法(SPFA)

这题是bellman-ford算法判断负权回路的应用

和上一题相比较,区别也就在于对负权回路的判断,其余思路保持一致。

故这里有一个关键,即如何判断负权回路:

我们用计数器记录每个节点加入队列的次数。如果某个节点的计数器达到了n(即所有节点的数量),那么这个节点在经过V-1次松弛操作后,仍然可以通过负权边继续进行松弛。这违反了Bellman-Ford算法的假设,即在V-1次松弛操作后,最短路径应该已经被找到。因此,可以判断出图中存在负权回路。

 完整代码如下:

#include <bits/stdc++.h>
using namespace std;struct Edge // 邻接表
{int to;                               // 边的指向节点(边链接的节点 -- 邻接节点)int val;                              // 边的权重Edge(int t, int w) : to(t), val(w) {} // 构造函数,初始化边的指向节点和权重
};int main()
{int n, m, p1, p2, val;cin >> n >> m;vector<list<Edge>> grid(n + 1); // 创建一个邻接表,存储图的信息,大小为n+1,因为节点编号从1开始vector<bool> inQueue(n + 1); // 用于标记节点是否已经在队列中(避免重复添加)// 将所有边保存起来,构建邻接表for (int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid[p1].push_back(Edge(p2, val)); // p1指向p2,边权重为val,将边添加到邻接表中}int start = 1; // 起点(源点)int end = n;   // 终点vector<int> minDist(n + 1, INT_MAX);minDist[start] = 0;queue<int> q;q.push(start); // 队列里放入起点vector<int> count(n + 1, 0); // 创建一个计数器数组,用于记录每个节点加入队列的次数count[start]++;              // 刚放入一次起点,计数+1bool flag = false; // 设置一个标志,用于标记是否找到了负权回路,初始化为falsewhile (!q.empty()){int node = q.front();q.pop();for (Edge edge : grid[node]){int from = node;int to = edge.to;int value = edge.val;if (minDist[to] > minDist[from] + value) // 开始松弛:如果通过当前节点到达邻接节点to的距离更短,则更新邻接节点to到源点的最短距{minDist[to] = minDist[from] + value;q.push(to);count[to]++;if (count[to] == n) // 关键:如果加入队列次数超过n-1次,就说明该图与负权回路{flag = true;while (!q.empty())q.pop();break;}}}}if (flag) // 如果存在负权回路,输出"circle"cout << "circle" << endl;else if (minDist[end] == INT_MAX)cout << "unconnected" << endl;elsecout << minDist[end] << endl;
}

题目三:卡码网 96. 城市间货物运输 III

题目链接

96. 城市间货物运输 III (kamacoder.com)

题目描述

某国为促进城市间经济交流,决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。

网络中的道路都有各自的运输成本和政府补贴,道路的权值计算方式为:运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用;权值为负则表示政府的补贴超过了支出的运输成本,实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下,从城市 src 到城市 dst 的最低运输成本。

输入描述

第一行包含两个正整数,第一个正整数 n 表示该国一共有 n 个城市,第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行,每行包括三个整数,s、t 和 v,表示 s 号城市运输货物到达 t 号城市,道路权值为 v。

最后一行包含三个正整数,src、dst、和 k,src 和 dst 为城市编号,从 src 到 dst 经过的城市数量限制。

输出描述

输出一个整数,表示从城市 src 到城市 dst 的最低运输成本,如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径,则输出 "unreachable",表示不存在符合条件的运输方案。

输入示例

6 7
1 2 1
2 4 -3
2 5 2
1 3 5
3 5 1
4 6 4
5 6 -2
2 6 1

输出示例

0

提示信息

从 2 -> 5 -> 6 中转一站,运输成本为 0。 

1 <= n <= 1000; 

1 <= m <= 10000; 

-100 <= v <= 100;

题解: Bellman-Ford算法

这题是bellman_ford算法解决单源有限最短路问题的应用。

这题Bellman - Ford算法实现的关键在于:

使用minDist_copy来保留上一次迭代的结果,从而避免重复计算和比较,提高算法的效率。如果在当前迭代中没有发现新的更短路径,那么在接下来的迭代中,可以只检查minDist_copy是否已经包含了一条更短的路径,如果没有,那么就不需要更新minDist数组。

通过进行k + 1次松弛操作,每次迭代开始时,将当前的minDist数组的内容复制到minDist_copy中。 遍历所有边,进行松弛操作。如果在松弛过程中发现通过某个节点到达某个邻接节点的距离更短,则更新最短距离。

#include <bits/stdc++.h>
using namespace std;int main()
{int src, dst, k, p1, p2, val, m, n; // 起点src,终点dst,松弛次数kcin >> n >> m;vector<vector<int>> grid; // 创建一个二维向量grid,用于存储图的信息:每个元素都是一条边(包含起始点,终止点,权值)// 读取所有边,并添加到grid中for (int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid.push_back({p1, p2, val});}cin >> src >> dst >> k;vector<int> minDist(n + 1, INT_MAX); // 用于存储从起点到每个节点的最短距离,都初始化为最大值INT_MAXminDist[src] = 0;                    // 起点除外,起点到本身的距离为0vector<int> minDist_copy(n + 1);     // 用来记录上一次遍历的结果// 进行k次松弛操作for (int i = 1; i <= k + 1; i++){minDist_copy = minDist; // 将上一次计算的结果赋值给minDist_copy:即将当前的minDist数组的内容复制到一个新的数组minDist_copy中// 遍历所有边,进行松弛操作for (vector<int> &side : grid){int from = side[0];int to = side[1];int price = side[2];// 注意使用 minDist_copy 来计算 minDistif (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price){minDist[to] = minDist_copy[from] + price;}}}if (minDist[dst] == INT_MAX) // 不能到达终点cout << "unreachable" << endl;elsecout << minDist[dst] << endl; // 到达终点最短路径
}

 三、小结

Bellman_ford算法的打卡到此结束,后边会继续加油!

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Untangle电脑上网行为管理软件有哪些?(一口气看完,第一款建议收藏!)

控制上网的软件通常被称为上网行为管理软件或上网行为监控软件。 这类软件主要用于管理网络用户的上网行为&#xff0c;帮助企业或组织提升网络使用效率和工作效率&#xff0c;同时最大限度地避免不当上网行为带来的潜在风险和损失。 以下是一些值得推荐的电脑上网行为管理软件…

【C++】——继承与虚继承

文章目录 继承继承的概念继承的定义继承类模版基类与派生类的赋值转换继承的作用域派生类的默认成员函数构造函数与析构函数拷贝构造 不能被继承的类继承与友元继承与静态成员多继承与菱形继承 虚继承继承与组合 继承 什么是继承&#xff1f; 继承其实就是胆码复用的一种手段&…

江科大笔记—OLED显示屏

OLED显示屏 OLED的GND接到负极&#xff0c;OLED的VCC接正极&#xff0c;同时也会接到stm32上的PB6和PB7 SCL接PB8 SDA接PB9 在Hardware文件夹里面放3个文件&#xff1a;OLED.c、OLED.h、OLED_Font.h OLED_Font.h:存的是OLED的字库数据&#xff0c;因OLED是不带字库的&#xf…

APP测试--含【学车不】项目实战

本文参考黑马程序员以下课程; 1-002-App应用架构_哔哩哔哩_bilibili 1. APP环境 1.1 app应用系统架构 json是一种轻量级的数据交换格式&#xff0c;采用完全独立于编程语言的文本格式来储存和表示数据 1.2 app 后台开发测试环境 预发布环境&#xff1a; 使用后端的测试代码&a…

Meta-Learning数学原理

文章目录 什么是元学习元学习的目标元学习的类型数学推导1. 传统机器学习的数学表述2. 元学习的基本思想3. MAML 算法推导3.1 元任务设置3.2 内层优化&#xff1a;任务级别学习3.3 外层优化&#xff1a;元级别学习3.4 元梯度计算3.5 最终更新规则 4. 算法合并5. 理解 MAML 的优…

钢索缺陷检测系统源码分享

钢索缺陷检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…

在线制作PPT组织架构图!这个AI工具简单又好用!

ppt组织架构图如何制作&#xff0c;用哪个软件好&#xff1f; 在现代商业世界中&#xff0c;组织架构图是展示公司结构和层级关系的重要工具&#xff0c;譬如内部沟通或者对外展示等场合下&#xff0c;一个精美且清晰的组织架构图都能有效传达信息&#xff0c;提升企业形象。 …

高精度加法和减法

高精度加法 在C/C中&#xff0c;我们经常会碰到限定数据范围的情况&#xff0c;我们先来看看常用的int和long long两种数据类型的范围吧。 C标准规定&#xff1a;int占一个机器字长。在32位系统中int占32位&#xff0c;即4个字节&#xff0c;所以int的范围是[-2的31次方&#…

独立站技能树之建站33项自检清单 1.0丨出海笔记

很多时候大家建好站之后很嗨&#xff0c;但过一会就开始担忧各种纠结我是不是还有什么点没做好&#xff0c;或者我的站漏了什么东西&#xff0c;那么接下来以下这个独立站自检清单能很好的帮到你。其实对于新手我还是建议大家直接用一些模板&#xff0c;因为模板上面基本该有的…

基于SpringBoot+Vue+MySQL的在线招投标系统

系统展示 用户前台界面 管理员后台界面 系统背景 在当今商业环境中&#xff0c;招投标活动是企业获取项目、资源及合作伙伴的重要途径。然而&#xff0c;传统招投标过程往往繁琐复杂&#xff0c;涉及众多文件交换、信息审核与沟通环节&#xff0c;不仅效率低下&#xff0c;还易…

车市状态喜人,国内海外“两开花”

文/王俣祺 导语&#xff1a;随着中秋假期告一段落&#xff0c;“金九”也正式过半&#xff0c;整体上这个销售旺季的数据可以说十分喜人&#xff0c;各家车企不是发布新车、改款车就是推出了一系列购车权益&#xff0c;充分刺激了消费者的购车热情。再加上政府政策的鼎力支持&a…

动态线程池实战(一)

动态线程池 对项目的认知 为什么需要动态线程池 DynamicTp简介 接入步骤 功能介绍 模块划分 代码结构介绍

中、美、德、日制造业理念差异

合格的产品依赖稳定可靠的人机料法环&#xff0c;要求减少变量因素&#xff0c;增加稳定因素&#xff0c;避免“熵”增&#xff1b;五个因素中任何一个不可控&#xff0c;批次产品的一致性绝对差&#xff1b; 日本汽车企业&#xff0c;侧重“人”和“环”&#xff0c; 倚重是人…

828华为云征文|华为云Flexus云服务器X实例之openEuler系统下部署SQLite数据库浏览器sqlite-web

828华为云征文&#xff5c;华为云Flexus云服务器X实例之openEuler系统下部署SQLite数据库浏览器sqlite-web 前言一、Flexus云服务器X实例介绍1.1 Flexus云服务器X实例简介1.2 Flexus云服务器X实例特点1.3 Flexus云服务器X实例使用场景 二、sqlite-web介绍2.1 sqlite-web简介2.2…

画台扇-第15届蓝桥省赛Scratch中级组真题第3题

[导读]&#xff1a;超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成&#xff0c;后续会不定期解读蓝桥杯真题&#xff0c;这是Scratch蓝桥杯真题解析第188讲。 如果想持续关注Scratch蓝桥真题解读&#xff0c;可以点击《Scratch蓝桥杯历年真题》并订阅合集&#xff0c;…

【教程】鸿蒙ARKTS 打造数据驾驶舱---前序

鸿蒙ARKTS 打造数据驾驶舱 ​ 前面2章我介绍了如何通过定义View绘制箭头以及圆形进度&#xff0c;初步了解了鸿蒙如何进行自定义View。接下来我将通过我最近在带的一个VUE的项目&#xff0c;简单实现了几个鸿蒙原生页面。帮助大家快速上手纯血鸿蒙开发. 本项目基于Api11Stage模…

揭开GPRC5D靶点的神秘面纱,助力多发性骨髓瘤药物开发

前 言 多发性骨髓瘤属于第二大常见的血液系统恶性肿瘤&#xff0c;起源于骨髓造血组织的浆细胞恶性增殖。首发症状表现为非特异性&#xff0c;如腰疼、反复感染等&#xff0c;造成误诊、漏诊率较高&#xff0c;且难治愈易复发。目前临床上的治疗有靶向治疗、放疗、化疗、干细…

C++之继承(通俗易懂版)

前言&#xff1a;我们都知道C是一门支持过程化编程&#xff0c;面向对象的高级语言&#xff0c;既然是面向对象的语言&#xff0c;那么对于对象而言&#xff0c;对象会有很多中相同的属性&#xff0c;举个例子:你和你老师&#xff0c;你们都有着共同的属性和身份&#xff0c;例…

Linux--守护进程与会话

进程组 概念 进程组就是一个或多个进程的集合。 一个进程组可以包含多个进程。 下面我们通过一句简单的命令行来展示&#xff1a; 为什么会有进程组&#xff1f; 批量操作&#xff1a;进程组允许将多个进程组织在一起&#xff0c;形成一个逻辑上的整体。当需要对多个进程…

【关联规则】【Apriori算法】理解

关联规则学习是数据挖掘中的一种技术&#xff0c;用于发现大型数据库中变量间的有趣关系&#xff0c;特别是变量之间的有意义的关联、相关和依赖关系。这种类型的规则在零售业中特别有用&#xff0c;因为它可以帮助确定哪些商品经常一起购买。 关键概念 频繁项集&#xff08;F…