c++directed-graphweighted-graph

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


Lets say I have following graph: enter image description here

Now what I want is to get shortest path between every node in graph(or have -1 at that place in matrix if it is not possible to get from 1 node to other) , but that path need to have lenght less or same as K.

Now I tried using floyd-warshall algorithm replacing automatically path from 1 node to other if its length is less then K ,but that algorithm did not work on any test cases(not Time limit exceeded but Wrong answer).

This is how I did it:

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

for same number(like 3 and 3) I know it is wrong but later when outputing I puted that just print 0.


Solution

  • l[i][j][1]+=1; it's wrong it should actually be l[i][j][1]=l[i][k][1]+l[k][j][1]; but this brakes your solution logic. So i recommend you do like this: count log(K) matrices: i-th matrix means length from j to k in no more than 2^i moves. Look at K in binary and when it-s 1 on i-th place you should recalc your ~current~ matrix with i-th matrix like this (not tested just for show the idea but seems that it would works. maybe should do --K for strict inequality):

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