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

解析

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

方法思路

1. 初始化距离数组：将源点1的距离设为0，其余点设为无穷大。

2. 松弛操作：进行k次迭代，每次遍历所有边，使用备份数组确保每次仅更新上一步的结果。

3. 负权处理：允许负权边，但不处理负权环，因为边数被限制为k次。

4. 结果判断：若目标点的距离仍为初始无穷大值，则不可达，否则输出结果。

解决代码

#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;
}

代码解释

1. 数据结构：使用结构体Edge存储边的起点、终点和权重。

2. 距离初始化：dist数组初始化为无穷大，源点距离为0。

3. 松弛操作：进行k次迭代，每次使用备份数组确保仅基于上一步结果更新。

4. 可达性判断：若目标点距离仍为初始无穷大，则不可达，否则输出最短距离。

该方法确保在最多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]。

结果

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

关键点

1. 松弛操作：通过边 a → b 尝试缩短从起点到点 b 的距离。

2. backup 的作用：确保每次更新都基于上一轮的结果，避免在同一轮迭代中多次更新同一条路径。

3. 边数限制：通过限制迭代次数 k，确保路径的边数不超过 k。

总结

• backup数组的作用：保存上一轮迭代的结果，确保每次更新都基于上一轮的结果，避免路径边数超过限制。

• 时间复杂度：O(k * m)，其中k是限制的边数，m是边数。

• 适用场景：适用于有向图，允许负权边，限制路径边数的最短路径问题。