当前位置：首页 > news >正文

从1号点到n号点最多经过k条边的最短距离

news 来源：原创 2025/5/16 6:36:58

- 解析
- 方法思路
- 代码解释
- 代码逐行注释
- - - 1. 头文件和常量定义：
    - 2.边的结构体：
    - 3.全局变量：
    - 4.Bellman-Ford算法实现：
    - 5.主函数：
- 注意事项
- - 代码含义
  - 为什么需要 backup[a]？
  - 举例说明
  - 关键点
- 总结

解析

要实现从1号点到n号点最多经过k条边的最短距离，可以使用Bellman-Ford算法的变种，限制松弛操作的次数为k次。通过备份距离数组确保每次松弛操作仅基于上一轮的结果，避免路径边数超过限制。具体步骤如下：

方法思路

初始化距离数组：将源点1的距离设为0，其余点设为无穷大。
松弛操作：进行k次迭代，每次遍历所有边，使用备份数组确保每次仅更新上一步的结果。
负权处理：允许负权边，但不处理负权环，因为边数被限制为k次。
结果判断：若目标点的距离仍为初始无穷大值，则不可达，否则输出结果。

解决代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 510, M = 10010; // 定义最大点数和边数
const int INF = 0x3f3f3f3f;   // 定义无穷大值struct Edge {int a, b, w; // 边的起点、终点和权重
} edges[M];      // 存储所有边的数组int n, m, k;     // n: 点数，m: 边数，k: 最多经过的边数
int dist[N];     // 存储从起点到每个点的最短距离
int backup[N];   // 备份数组，用于保存上一轮迭代的距离// Bellman-Ford算法实现
void bellman_ford() {memset(dist, 0x3f, sizeof dist); // 初始化距离数组为无穷大dist[1] = 0; // 起点到自身的距离为0// 进行k次松弛操作for (int i = 0; i < k; ++i) {memcpy(backup, dist, sizeof dist); // 将当前距离数组复制到备份数组for (int j = 0; j < m; ++j) {      // 遍历所有边int a = edges[j].a, b = edges[j].b, w = edges[j].w;if (backup[a] != INF) { // 如果上一轮中a是可达的dist[b] = min(dist[b], backup[a] + w); // 更新b的距离}}}
}int main() {// 输入点数、边数和最多经过的边数scanf("%d%d%d", &n, &m, &k);// 输入每条边的信息for (int i = 0; i < m; ++i) {int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w}; // 存储边}// 调用Bellman-Ford算法bellman_ford();// 输出结果if (dist[n] == INF) puts("impossible"); // 如果终点不可达，输出impossibleelse printf("%d\n", dist[n]);           // 否则输出最短距离return 0;
}

代码解释

数据结构：使用结构体Edge存储边的起点、终点和权重。
距离初始化：dist数组初始化为无穷大，源点距离为0。
松弛操作：进行k次迭代，每次使用备份数组确保仅基于上一步结果更新。
可达性判断：若目标点距离仍为初始无穷大，则不可达，否则输出最短距离。

该方法确保在最多k条边的限制下找到最短路径，同时正确处理负权边，避免负权环的干扰。

代码逐行注释

1. 头文件和常量定义：

#include <iostream>
#include <cstring>
#include <algorithm>

包含输入输出、字符串操作和算法库。

const int N = 510, M = 10010;
const int INF = 0x3f3f3f3f;

N：最大点数。
M：最大边数。
INF：表示无穷大的值。

2.边的结构体：

struct Edge {int a, b, w; // 边的起点、终点和权重
} edges[M];      // 存储所有边的数组

a：边的起点。
b：边的终点。
w：边的权重。

3.全局变量：

int n, m, k;     // n: 点数，m: 边数，k: 最多经过的边数
int dist[N];     // 存储从起点到每个点的最短距离
int backup[N];   // 备份数组，用于保存上一轮迭代的距离

dist：存储从起点到每个点的最短距离。
backup：备份数组，用于保存上一轮迭代的结果。

4.Bellman-Ford算法实现：

void bellman_ford() {memset(dist, 0x3f, sizeof dist); // 初始化距离数组为无穷大dist[1] = 0; // 起点到自身的距离为0

初始化dist数组，所有点的距离设为无穷大，起点的距离设为0。

    for (int i = 0; i < k; ++i) { // 进行k次松弛操作memcpy(backup, dist, sizeof dist); // 将当前距离数组复制到备份数组for (int j = 0; j < m; ++j) {      // 遍历所有边int a = edges[j].a, b = edges[j].b, w = edges[j].w;if (backup[a] != INF) { // 如果上一轮中a是可达的dist[b] = min(dist[b], backup[a] + w); // 更新b的距离}}}
}

进行k次松弛操作。
每次迭代前，将dist数组复制到backup数组。
遍历所有边，基于backup数组更新dist数组。

5.主函数：

int main() {scanf("%d%d%d", &n, &m, &k); // 输入点数、边数和最多经过的边数for (int i = 0; i < m; ++i) { // 输入每条边的信息int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w}; // 存储边}bellman_ford(); // 调用Bellman-Ford算法if (dist[n] == INF) puts("impossible"); // 如果终点不可达，输出impossibleelse printf("%d\n", dist[n]);           // 否则输出最短距离return 0;
}

输入点数、边数和最多经过的边数。
输入每条边的信息并存储。
调用bellman_ford函数计算最短距离。
根据结果输出impossible或最短距离。

注意事项

dist[b] = min(dist[b], backup[a] + w); 是Bellman-Ford算法中的松弛操作，它的作用是尝试通过边a → b来缩短从起点到点 b 的最短距离。下面详细解释这行代码的含义：

代码含义

dist[b]：当前从起点到点 b 的最短距离。
backup[a]：上一轮迭代中从起点到点 a 的最短距离。
w：边 a → b 的权重。
backup[a] + w：通过边 a → b 到达点 b 的路径距离。
min(dist[b], backup[a] + w)：比较当前的最短距离和通过边 a → b 的新路径距离，取较小值。

这行代码的意思是：如果通过边 a → b 可以缩短从起点到点 b 的距离，则更新 dist[b]。

为什么需要 backup[a]？

backup 数组保存的是上一轮迭代的结果。
在 Bellman-Ford 算法中，每次迭代只能增加一条边到路径中。如果直接使用 dist[a] 更新 dist[b]，可能会导致在同一轮迭代中多次更新同一条路径，从而违反边数限制。
通过使用 backup[a]，我们确保每次更新都基于上一轮的结果，而不是当前轮次中已经更新过的值。

举例说明

假设有以下图：

起点：1
边：1 → 2 (权重 1)2 → 3 (权重 1)1 → 3 (权重 3)

限制边数k = 2。

初始状态

dist 数组：[0, INF, INF]（起点到自身的距离为 0，其余为无穷大）。
backup 数组：与 dist 相同。

第一轮迭代（k=1）

遍历所有边：
- 边 1 → 2：dist[2] = min(INF, 0 + 1) = 1。
- 边 2 → 3：dist[3] = min(INF, INF + 1) = INF（因为 backup[2] = INF，不可达）。
- 边 1 → 3：dist[3] = min(INF, 0 + 3) = 3。
更新后的 dist 数组：[0, 1, 3]。

第二轮迭代（k=2）

将 dist 复制到 backup：backup = [0, 1, 3]。
遍历所有边：
- 边 1 → 2：dist[2] = min(1, 0 + 1) = 1（无变化）。
- 边 2 → 3：dist[3] = min(3, 1 + 1) = 2（通过路径 1 → 2 → 3 更新）。
- 边 1 → 3：dist[3] = min(2, 0 + 3) = 2（无变化）。
更新后的 dist 数组：[0, 1, 2]。

结果

从起点到点 3 的最短距离为 2，路径为 1 → 2 → 3。

关键点

松弛操作：通过边 a → b 尝试缩短从起点到点 b 的距离。
backup 的作用：确保每次更新都基于上一轮的结果，避免在同一轮迭代中多次更新同一条路径。
边数限制：通过限制迭代次数 k，确保路径的边数不超过 k。

总结

backup数组的作用：保存上一轮迭代的结果，确保每次更新都基于上一轮的结果，避免路径边数超过限制。
时间复杂度：O(k * m)，其中k是限制的边数，m是边数。
适用场景：适用于有向图，允许负权边，限制路径边数的最短路径问题。

从1号点到n号点最多经过k条边的最短距离

目录解析方法思路代码解释代码逐行注释1. 头文件和常量定义：2.边的结构体：3.全局变量：4.Bellman-Ford算法实现：5.主函数： 注意事项代码含义为什么需要 backup[a]？举例说明关键点总结解析要实现从1号点…...

编程日记 2025/5/16 6:36:58

模拟实战-用CompletableFuture优化远程RPC调用

实战场景这是广州某500-900人互联网厂的面试原题手写并发优化解决思路我们要调用对方的RPC接口，我们的RPC接口每调用一次对方都会阻塞50ms 但是我们的业务要批量调用RPC，例如我们要批量调用1k次，我们不可能在for循环里面写1k次远程调用…...

编程日记 2025/5/12 15:18:43

【pinia状态管理配置】

pinia状态管理配置安装main.ts引入自定义user仓库使用自定义仓库安装 pnpm add piniamain.ts引入 // createPinia() 函数调用创建了一个新的 Pinia 实例。 // 这个实例是状态管理的核心，它将管理应用中所有的 store。 import { createPinia } from pinia app.us…...

编程日记 2025/5/12 16:07:46

SpringBoot 引⼊MybatisGenerator 1. 引入插件2. 添加generator.xml并修改3. 生成文件 1. 引入插件 <plugin><groupId>org.mybatis.generator</groupId><artifactId>mybatis-generator-maven-plugin</artifactId><version>1.3.5</vers…...

编程日记 2025/5/7 7:31:27

在线销售数据集分析：基于Python的RFM数据分析方法实操训练

一、前言个人练习，文章用于记录自己的学习练习过程，分享出来和大家一起学习。数据集：在线销售数据集分析方法：RFM分析方法二、过程 1.1 库的导入与一些必要的初始设置 import pandas as pd import datetime import matplo…...

编程日记 2025/5/7 7:05:28

LeetCode - #197 Swift 实现找出温度更高的日期

网罗开发 （小红书、快手、视频号同名） 大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等…...

编程日记 2025/5/13 5:38:37

分析哲学：从语言解剖到思想澄清的哲学探险

分析哲学：从语言解剖到思想澄清的哲学探险第一节：分析哲学的基本概念与公式解释【通俗讲解，打比方来讲解！】分析哲学，就像一位 “语言侦探”，专注于 “解剖语言”，揭示我们日常使用的语…...

编程日记 2025/5/16 2:17:10

C++【iostream】数据库的部分函数功能介绍

在 C 编程世界中，iostream 库扮演着举足轻重的角色，它是 C 标准库的核心组成部分，为程序提供了强大的输入输出功能。无论是简单的控制台交互，还是复杂的文件操作，iostream 库都能提供便捷高效的解决方案。本文将深入剖…...

编程日记 2025/5/15 13:48:14

金山打字游戏2010绿色版，Win7-11可用DxWnd完美运行

金山打字游戏2010绿色版，Win7-11可用DxWnd完美运行链接：https://pan.xunlei.com/s/VOIAYCzmkbDfdASGJa_uLjquA1?pwd67vw# 进入游戏后，如果输入不了英文字母（很可能是中文输入状态），就按一下“Shift”键…...

编程日记 2025/5/12 2:46:13

洛谷[USACO08DEC] Patting Heads S

题目传送门题目难度：普及/提高一题面翻译今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。贝茜让 N N N ( 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1≤N≤105) 头奶牛坐成一个圈。除了 1 1 1 号与 N N N 号奶牛外&#xff0…...

编程日记 2025/5/16 6:25:26

讲清逻辑回归算法，剖析其作为广义线性模型的原因

1、逻辑回归算法介绍逻辑回归(Logistic Regression)是一种广义线性回归分析模型。虽然名字里带有“回归”两字，但其实是分类模型，常用于二分类。既然逻辑回归模型是分类模型，为什么名字里会含有“回归”二字呢？这是因为其算法原…...

编程日记 2025/5/13 6:31:01

基于STM32的智能安防监控系统

1. 引言随着物联网技术的普及，智能安防系统在家庭与工业场景中的应用日益广泛。本文设计了一款基于STM32的智能安防监控系统，集成人体感应、环境异常检测、图像识别与云端联动功能，支持实时报警、远程监控与数据回溯。该系统采用边缘计算与…...

编程日记 2025/5/15 22:31:41

八. Spring Boot2 整合连接 Redis(超详细剖析)

八. Spring Boot2 整合连接 Redis(超详细剖析) 文章目录八. Spring Boot2 整合连接 Redis(超详细剖析)2. 注意事项和细节3. 最后： 在 springboot 中 , 整合 redis 可以通过 RedisTemplate 完成对 redis 的操作, 包括设置数据/获取数据比如添加和读取数据具体整…...

编程日记 2025/5/13 5:03:38

220.存在重复元素③

目录一、题目二、思路三、解法四、收获一、题目给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。找出满足下述条件的下标对 (i, j)： i ! j, abs(i - j) < indexDiff abs(nums[i] - nums[j]) < valueDiff 如果存在，返回 true &a…...

编程日记 2025/5/12 17:55:38

【Linux】从硬件到软件了解进程

个人主页~ 从硬件到软件了解进程一、冯诺依曼体系结构二、操作系统三、操作系统进程管理1、概念2、PCB和task_struct3、查看进程4、通过系统调用fork创建进程（1）简述（2）系统调用生成子进程的过程〇提出问题①fork函数②父子进程关…...

编程日记 2025/5/14 8:43:29

volatile变量需要减少读取次数吗

问题说明本人在前期读Netty源码时看到这样一段源码和注释： private boolean invokeHandler() {// Store in local variable to reduce volatile reads.int handlerState this.handlerState;return handlerState ADD_COMPLETE || (!ordered && handlerS…...

编程日记 2025/5/13 17:16:43

红黑树的封装

一、封装思路在 STL 中 map set 的底层就是封装了一棵红黑树。其中连接红黑树和容器的是迭代器，map set 暴露出的接口都不是自己写的，而是红黑树写的，外部接口封装红黑树接口。所以写出红黑树为 map set 写的接口，再在上层的…...

编程日记 2025/5/12 12:19:59

Java 泛型＜? extends Object＞

在 Java 泛型中，<? extends Object> 和 <?> 都表示未知类型，但它们在某些情况下有细微的差异。泛型的引入是为了消除运行时错误并增强类型安全性，使代码更具可读性和可维护性。在 JDK 5 中引入了泛型，以消除编译时…...

编程日记 2025/5/15 4:23:34

TensorFlow简单的线性回归任务

如何使用 TensorFlow 和 Keras 创建、训练并进行预测 1. 数据准备与预处理 2. 构建模型 3. 编译模型 4. 训练模型 5. 评估模型 6. 模型应用与预测 7. 保存与加载模型 8.完整代码 1. 数据准备与预处理我们将使用一个简单的线性回归问题，其中输入特征 x 和标…...

编程日记 2025/5/14 16:52:34

解码大数据的四个V：体积、速度、种类与真实性

解码大数据的四个V：体积、速度、种类与真实性在大数据领域，有一个大家耳熟能详的概念——“四个V”：Volume（体积）、Velocity（速度）、Variety（种类）、Veracity&#xff…...

编程日记 2025/5/14 13:20:24

【单层神经网络】基于MXNet的线性回归实现（底层实现）

写在前面基于亚马逊的MXNet库本专栏是对李沐博士的《动手学深度学习》的笔记，仅用于分享个人学习思考以下是本专栏所需的环境（放进一个environment.yml，然后用conda虚拟环境统一配置即可）刚开始先从普通的寻优算法开始&#xff…...

编程日记 2025/5/15 12:16:41

深入解析 posix_spawn()：高效的进程创建方式（中英双语）

深入解析 posix_spawn()：高效的进程创建方式 1. 引言在 Unix/Linux 系统中，传统的进程创建方式主要依赖 fork() 和 exec() 组合。但 fork() 在某些情况下可能存在性能瓶颈，特别是当父进程占用大量内存时，fork() 仍然需要复制整…...

编程日记 2025/5/16 2:33:29

2024-我的学习成长之路

因为热爱，无畏山海...

编程日记 2025/5/15 8:20:13

【Java异步编程】基于任务类型创建不同的线程池

文章目录一. 按照任务类型对线程池进行分类1. IO密集型任务的线程数2. CPU密集型任务的线程数3. 混合型任务的线程数二. 线程数越多越好吗三. Redis 单线程的高效性使用线程池的好处主要有以下三点： 降低资源消耗：线程是稀缺资源，如果无限…...

编程日记 2025/5/15 8:36:13

前缀和多种基础

前缀和加法 #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int n; const int N 1e310; int arr[N]; int pre[N]; int org[N]; int main(void) {cin >> n;for(int i 1 ; i < n ; i){cin >> arr[i];pre[i] …...

编程日记 2025/5/15 3:12:09

关于贪心学习的文笔记录

贪心，顾名思义就是越贪越好，越多越有易，他给我的感觉是，通常是求最大或最小问题，相比于动态规划贪心让人更加琢磨不透，不易看出方法，为此在这记录我所见过的题型和思维方法，以便回头…...

编程日记 2025/5/15 12:46:57

蓝桥杯思维训练营(三）

文章目录题目详解680.验证回文串 II30.魔塔游戏徒步旅行中的补给问题观光景点组合得分问题题目详解 680.验证回文串 II 680.验证回文串 II 思路分析：这个题目的关键就是，按照正常来判断对应位置是否相等，如果不相等，那么就判…...

编程日记 2025/5/11 21:19:01

农历2025开始笔记

2/3 Hey everyone! The Chinese New Year holiday is over. I spent over ten days back home, and honestly, I feel even more exhausted than when I’m working. Yesterday, I drove for 13 hours straight and finally made it back. In a couple of days, I’ll officia…...

编程日记 2025/5/15 14:05:07

目录

解析