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

- 解析
- 方法思路
- 代码解释
- 代码逐行注释
- - - 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"); // 如果终点不可达，输出impossible
    else 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"); // 如果终点不可达，输出impossible
    else 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]。

结果