如何找到 K 移动中每个节点之间的最短路径？

Question

假设我有下图：

现在我想要的是获得图中每个节点之间的最短路径（或者如果不可能从 1 个节点到其他节点，则在矩阵中的那个位置有 -1），但该路径需要有长度小于或等于 K.

现在我尝试使用 floyd-warshall 算法自动替换从 1 个节点到其他节点的路径，如果它的长度小于 K ，但该算法不适用于任何测试用例（不是超过时间限制但答案错误）。

我是这样做的：

// N is number of nodes, l is matrix, in l[x][y][0] I have shortest path from x to y and in l[x][y][1] is its lenght
for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //if (this new path is shorter or there is not path yet) and current path lenght is not K(if it already reached max size) and both paths are not -1.
            if((l[i][j][0]>l[i][k][0]+l[k][j][0] || l[i][j][0]==-1) && l[i][j][1]<K && l[i][k][0]>-1 && l[k][j][0]>-1){
                //change max size
                l[i][j][0]=l[i][k][0]+l[k][j][0];
                //lenght of that path +=1
                l[i][j][1]+=1;
            }
        }
    }
}

对于相同的数字（比如 3 和 3），我知道这是错误的，但后来在输出时我只打印了 0。

Answer 1

l[i][j][1]+=1; 它实际上应该是 l[i][j][1]=l[i][k][1]+l[k][j][1]; 是错误的，但这会破坏您的解决方案逻辑。所以我建议你这样做：计算 log(K) 个矩阵： i-th 矩阵表示从 j 到 k 的长度不超过 2^i moves。以二进制形式查看 K，当 it-s 1 在 i-th 位置时，您应该使用 i-th 矩阵重新计算 ~current~ 矩阵（未测试只是为了显示想法，但似乎可行。对于严格的不等式，也许应该 --K):

#include <iostream>
#include <vector>

int my_log2(int index){
    int targetlevel = 0;
    while (index >>= 1) ++targetlevel;
    return targetlevel;
}

int main(){
    int N;
    int K;
    std::cin >> N >> K;
    std::vector < std::vector < std::vector < int > > > dist(my_log2(K), std::vector < std::vector < int > > (N, std::vector < int > (N)));
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            // assume weights are positive and -1 if no edge between vertices
            // assume that dist[0][i][i] == 0
            std::cin >> dist[0][i][j];
        }
    }
    // can be easy rewriten to negative weights with same idea
    for (int i = 1; i < my_log2(K); ++i){
        for (int j = 0; j < N; ++j){
            for (int k = 0; k < N; ++k){
                dist[i][j][k] = -1;
                for (int l = 0; l < N; ++l){
                    if (dist[i - 1][j][l] > -1 && dist[i - 1][l][k] > -1 && (dist[i][j][k] == -1 || dist[i][j][k] > dist[i - 1][j][l] + dist[i - 1][l][k])){
                        dist[i][j][k] = dist[i - 1][j][l] + dist[i - 1][l][k];
                    }
                }
            }
        }
    }
    std::vector < std::vector < int > > old_current(N, std::vector < int > (N, -1));
    
    for (int i = 0; i < N; ++i){
        old_current[i][i] = 0;
    }
    for (int i = 0; i < my_log2(K); ++i){
        std::vector < std::vector < int > > new_current(N, std::vector < int > (N, -1));
        if (((K >> i) & 1) == 1){
            for (int j = 0; j < N; ++j){
                for (int k = 0; k < N; ++k){
                    for (int l = 0; l < N; ++l){
                        if (old_current[j][l] > -1 && dist[i][l][k] > -1 && (new_current[j][k] == -1 || new_current[j][k] > old_current[j][l] + dist[i][l][k])){
                            new_current[j][k] = old_current[j][l] + dist[i][l][k];
                        }
                        if (dist[i][j][l] > -1 && old_current[l][k] > -1 && (new_current[j][k] == -1 || new_current[j][k] > dist[i][j][l] + old_current[l][k])){
                            new_current[j][k] = dist[i][j][l] + old_current[l][k];
                        }
                    }
                }
            }
        }
        old_current = new_current;
    }
    // asnwer is in old_current
}

如何找到 K 移动中每个节点之间的最短路径？

How to find shortest path between every node within K moves?

c++

directed-graph

weighted-graph