如何在K步以内求解图中所有节点间的最短路径？

你的思路方向是对的，但代码里有几个核心逻辑错误，导致结果不正确。咱们一步步拆解问题：

原代码的关键错误 #

1. 步数计算完全错误
   你代码里写的l[i][j][1]+=1完全不符合路径步数的计算逻辑。比如从i到k用了2步，k到j用了3步，那i→k→j的总步数应该是l[i][k][1] + l[k][j][1]，而不是原i→j路径的步数加1。如果原i→j没有路径，l[i][j][1]的初始值可能是0，这时候加1得到1，和实际步数5完全不符，这直接导致后续所有依赖步数的判断都失效。

2. 更新条件逻辑混乱
   你判断的是l[i][j][1]<K，但这是原路径的步数，不是新路径的步数。正确的逻辑应该是：新路径的总步数（i→k的步数 + k→j的步数）≤K，同时新路径的长度更短，或者原路径不存在。

3. 传统Floyd不适合直接修改步数限制
   传统Floyd的中间节点循环是用来找任意步数的最短路径，它不追踪步数的累积。当有步数限制时，我们需要用按步数迭代的动态规划，而不是硬套Floyd的三层循环结构。

正确的实现思路 #

我们可以定义dist[t][i][j]表示从i到j最多用t步的最短路径长度。然后通过递推来更新这个状态：

• 初始状态：t=0时，只有i到自己的路径长度为0，其他都是-1（0步只能留在原地）；t=1时，要么是直接边的长度，要么是0（自己到自己），没有边的话是-1。
• 递推过程：对于t>1，dist[t][i][j]的取值有两种可能：要么沿用t-1步的结果（不增加步数），要么通过某个中间节点k，先走t-1步到k，再走1步到j，取这两种情况的最小值。

为了节省空间，我们可以用滚动数组，只保留前一步的状态，不需要存储所有t的结果。

修正后的代码示例 #

假设你有一个原始邻接矩阵graph，其中graph[i][j]表示i到j的直接边长度，没有边则为-1：

int N = ...; // 节点数量
int K = ...; // 最大步数限制
vector<vector<int>> graph(N, vector<int>(N, -1));
// 这里先初始化graph，比如设置直接边的长度，graph[i][i] = 0;

// 滚动数组：prev_dist存储最多t-1步的最短路径，curr_dist存储最多t步的
vector<vector<int>> prev_dist(N, vector<int>(N, -1));
vector<vector<int>> curr_dist(N, vector<int>(N, -1));

// 初始化0步的情况：只能到自己
for (int i = 0; i < N; ++i) {
    prev_dist[i][i] = 0;
}

// 初始化1步的情况：直接边或自己到自己
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        if (i == j) {
            curr_dist[i][j] = 0;
        } else {
            curr_dist[i][j] = graph[i][j];
        }
    }
}

// 从2步迭代到K步
for (int t = 2; t <= K; ++t) {
    // 先继承上一步的结果（不使用新步数的情况）
    curr_dist = prev_dist;
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < N; ++k) {
            if (prev_dist[i][k] == -1) continue; // i到k最多t-1步不可达
            for (int j = 0; j < N; ++j) {
                if (graph[k][j] == -1) continue; // k到j没有直接边（无法走这一步）
                int new_dist = prev_dist[i][k] + graph[k][j];
                // 如果当前路径不存在，或者新路径更短，就更新
                if (curr_dist[i][j] == -1 || new_dist < curr_dist[i][j]) {
                    curr_dist[i][j] = new_dist;
                }
            }
        }
    }
    // 更新前一步的状态为当前步
    prev_dist = curr_dist;
}

// 确保同节点的结果为0（如果初始化没问题的话这一步可以省略）
for (int i = 0; i < N; ++i) {
    curr_dist[i][i] = 0;
}

// curr_dist就是最终的最多K步的最短路径矩阵

额外说明 #

• 如果你的原始输入不是邻接矩阵，而是边列表，需要先把它转换成邻接矩阵再用上面的代码。
• 这个实现的时间复杂度是O(K*N²)，如果N和K都不是特别大（比如N≤100，K≤1000），这个效率是完全可以接受的。

内容的提问来源于stack exchange，提问作者User813291452