边数有限，如何求最短路径？

49.Acwing基础课第853题-简单-有边数限制的最短路 题目描述 给定一个 n个点 m条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出从 1号点到 n号点的最多经过 k条边的最短距离，如果无法从 1 号点走到 n号点，输出 impossible。 注意：图中可能 存在负权回路 。 输入格式 第一行包含三个整数 n,m,k。 接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的有向边，边长为 z。 点的编号为 1∼n。 输出格式 输出一个整数，表示从 1号点到 n 号点的最多经过 k条边的最短距离。 如果不存在满足条件的路径，则输出 impossible。 数据范围 1≤n,k≤500， 1≤m≤10000 1≤x,y≤n 任意边长的绝对值不超过 10000。 输入样例： 3 3 1 1 2 1 2 3 1 1 3 3 输出样例： 3 代码： #include <iostream> // 用于memset（初始化数组）和memcpy（数组拷贝）的头文件 #include <cstring> // 用于min函数（更新最短路径时的最小值比较） #include <algorithm> // 使用std命名空间，避免cin/cout/scanf等加std::前缀 using namespace std; // 常量定义： // N=510：适配题目中顶点数≤500的限制，留少量冗余 // M=10010：适配题目中边数≤10000的限制 // INF=0x3f3f3f3f：代表无穷大（值为1061109567，远大于题目最大可能路径和） const int N = 510, M = 10000 + 10, INF = 0x3f3f3f3f; // 结构体定义：存储有向边的信息 struct Edge { int a, b, w; // a：边的起点，b：边的终点，w：边的权重（可正可负） } edges[M]; // edges数组存储所有m条有向边 // 全局变量： // dist[N]：dist[i]表示从1号点到i号点的最短路径长度 // backup[N]：备份数组，存储上一轮迭代后的dist值，防止串联更新 int dist[N], backup[N]; // n：顶点总数，m：有向边总数，k：题目要求的最多经过的边数 int n, m, k; // 核心函数：实现带边数限制的Bellman-Ford算法 // 返回值：从1号点到n号点最多经过k条边的最短路径长度（不可达时返回INF） int bellman_ford() { // 初始化dist数组：所有点的初始距离设为INF（表示初始不可达） memset(dist, 0x3f, sizeof dist); // 起点（1号点）到自身的距离为0（最短路径的初始条件） dist[1] = 0; // 外层循环k次：每轮迭代对应“路径最多增加1条边”，保证最终路径边数≤k for (int i = 0; i < k; i++) { // 关键操作：将当前dist数组完整拷贝到backup数组 // 目的：切断同一轮迭代内的“串联更新”（避免一轮内走多条边） memcpy(backup, dist, sizeof dist); // 内层循环：遍历所有m条有向边，执行松弛操作 for (int j = 0; j < m; j++) { // 取出第j条边的起点、终点、权重 int a = edges[j].a, b = edges[j].b, w = edges[j].w; // 优化判断：仅当起点a可达时才执行松弛 // 原因：backup[a]≥INF/2时，a不可达，backup[a]+w无意义（甚至可能溢出） // INF/2是安全阈值，避免负权边导致backup[a]略小于INF的误判 if (backup[a] < INF/2) { // 松弛操作：更新1号点到b点的最短路径 // 逻辑：如果“1→a的路径 + a→b的边权”比当前“1→b的路径”更短，则更新 // 注意：用backup[a]（上一轮结果）而非dist[a]，保证每轮只加1条边 dist[b] = min(dist[b], backup[a] + w); } } } // 返回1号点到n号点的最短路径长度（不可达时返回INF） return dist[n]; } int main() { // 输入：顶点数n、边数m、最多经过的边数k（scanf效率高于cin，避免大数据超时） scanf("%d%d%d", &n, &m, &k); // 循环读取m条有向边的信息 for (int i = 0; i < m; i++) { int x, y, z; // x：边的起点，y：边的终点，z：边的权重 scanf("%d%d%d", &x, &y, &z); // 将第i条边存入edges数组 edges[i] = {x, y, z}; } // 调用Bellman-Ford算法，获取1号点到n号点的最短路径长度 int t = bellman_ford(); // 结果输出： // 判定不可达：t>INF/2时，说明路径长度远超合理范围，输出"impossible" // 可达则直接输出最短路径长度 if (t > INF / 2) cout << "impossible" << endl; else cout << t << endl; return 0; } 需要松弛多少次？ 至多n-1遍，因为一条最短路径的长度最多为n-1条边。所以，在实际操作中，该算法经常会在未达到n-1轮松弛前就已经计算出最短路径。 backup[j]表示每次进入第2重循环的dist数组的备份。 如果不加这个备份的话有可能会发生节点最短距离的串连 串联：就是多条边的值加到了一起。导致第k层循环之后找到一个边数大于k的路径。 算法分析 （1）代码整体功能 　　这段代码实现了带边数限制的 Bellman-Ford 算法变种，核心目标是求解：在有向图中，从固定起点（1 号顶点）到终点（n 号顶点）的路径中，经过的边数不超过 k 条 的最短路径长度。 与标准 Bellman-Ford 算法的核心区别： 标准 Bellman-Ford：无边界数限制，可检测图中的负权回路； 本变种：聚焦 “边数限制”，不检测负权回路（边数限制天然避免了负权回路的无限松弛问题）。 （2）核心逻辑逐行解析 ①初始化部分 memset(dist, 0x3f, sizeof dist); dist[1] = 0; dist[] 数组定义：dist[x] 表示 “从起点 1 到顶点 x，满足‘边数不超过当前迭代轮次’的最短路径长度”； 初始化规则： 起点 1 到自身的距离设为 0（最短路径的基础条件）； 其余顶点初始化为 INF（0x3f3f3f3f，值为 1061109567，远大于实际路径和，代表 “初始不可达”）； 选用 0x3f3f3f3f 作为无穷大的优势：数值足够大（满足 “不可达” 语义）、按字节初始化（memset）方便、两个 INF 相加不会溢出。 ②核心迭代（k 次循环） // 内层循环：遍历所有m条有向边，执行松弛操作 for (int j = 0; j < m; j++) { // 取出第j条边的起点、终点、权重 int a = edges[j].a, b = edges[j].b, w = edges[j].w; // 优化判断：仅当起点a可达时才执行松弛 // 原因：backup[a]≥INF/2时，a不可达，backup[a]+w无意义（甚至可能溢出） // INF/2是安全阈值，避免负权边导致backup[a]略小于INF的误判 if (backup[a] < INF/2) { // 松弛操作：更新1号点到b点的最短路径 // 逻辑：如果“1→a的路径 + a→b的边权”比当前“1→b的路径”更短，则更新 // 注意：用backup[a]（上一轮结果）而非dist[a]，保证每轮只加1条边 dist[b] = min(dist[b], backup[a] + w); } } 这是整个算法的核心，拆解为两个关键要点： A.k 次迭代的意义（边数限制的核心） 第 i 次迭代（i 从 0 开始）完成后，dist 数组存储的是：从起点 1 出发，最多经过 i+1 条边 到达各顶点的最短路径。 例如： i=0（第 1 轮）：最多用 1 条边到达各点； i=k-1（第 k 轮）：最多用 k 条边到达各点（正好满足题目 “边数不超过 k” 的限制）。 B.backup 数组的关键作用（避免 “串联更新”） 为什么需要备份？ 如果直接用 dist[a] 去更新 dist[b]，可能出现 “同一轮迭代中，刚更新的 dist[b] 立刻被用来更新 dist[c]”（比如边 a→b 更新后，马上用 dist[b] 更新边 b→c），这相当于 “在一轮里用了两条边”，违反 “每轮最多增加 1 条边” 的规则。 核心逻辑：backup 保存上一轮迭代结束后的 dist 数组，本轮所有松弛操作都基于 “最多 i 条边” 的结果（backup），保证每轮迭代只增加 1 条边的路径长度。 C.松弛操作 if (backup[a] < INF/2) { // 松弛操作：更新1号点到b点的最短路径 // 逻辑：如果“1→a的路径 + a→b的边权”比当前“1→b的路径”更短，则更新 // 注意：用backup[a]（上一轮结果）而非dist[a]，保证每轮只加1条边 dist[b] = min(dist[b], backup[a] + w); } 前置条件 backup[a] < INF/2： ✅ 避免 “不可达的 a 点” 参与计算（backup [a]≥INF/2 时，a 不可达，backup [a]+w 无意义）； ✅ 规避负权边导致 backup [a] 略小于 INF 的误判（比如 INF-5，实际仍不可达）； 核心逻辑：如果 “从 1 到 a 的路径长度 + a→b 的边权” 比 “当前从 1 到 b 的路径长度” 更短，则更新 dist [b]。 ③结果判断与返回 int t = bellman_ford(); if (t > INF / 2) cout << "impossible" << endl; else cout << t << endl; 为什么不用 t == INF 判断不可达？ 若图中有负权边，可能将 dist [n] 更新为 “INF - 某个小值”（比如 INF-3），此时 t≠INF 但实际仍不可达；用 t > INF/2 作为阈值，能精准规避这种误判（INF/2 仍是远大于实际路径的数）； 输出规则：不可达输出 “impossible”，可达则输出最短路径长度。 ④主函数部分 输入：用scanf读取顶点数 n、边数 m、边数限制 k（scanf 效率高于 cin，避免大数据输入超时）； 存储边：遍历读取 m 条有向边的起点、终点、权重，存入 edges 数组； 调用算法：执行 bellman_ford 函数，获取 1→n 的最短路径长度； 结果输出：按上述规则输出结果。 （3）算法特性与适用场景 ①时间复杂度 外层循环 k 次，内层遍历 m 条边 → 时间复杂度为 O(k×m)。 对比标准 Bellman-Ford（O(n×m)）：当 k < n 时，此变种更高效（比如 k=5，n=500，效率提升 100 倍）。 ②适用场景 专门解决 “有边数限制的单源最短路径” 问题，例如： 从城市 1 到城市 n，最多换乘 k 次公交，求最短耗时； 网络数据包传输，最多经过 k 个路由器，求最小延迟； 所有需要限制 “路径边数” 的最短路径问题（标准 Dijkstra 无法处理此类限制）。 ③局限性 不检测负环：因为 “边数限制 k” 本身限制了路径长度，即使有负环，也无法无限绕环缩短路径（最多绕 k 条边）； 只能处理 “单源”（从固定起点 1 出发）的最短路径。 总结 边数限制的实现：通过k 轮迭代严格控制路径边数，每轮迭代对应 “最多增加 1 条边”； backup 数组的意义：避免同一轮迭代的 “串联更新”，是保证边数限制有效的核心； 无穷大的技巧：用0x3f3f3f3f作为无穷大，结果判断用> INF/2而非== INF，规避负权边的误判； 适用边界：专解 “边数受限的单源最短路径”，支持负权边，不处理负权回路。