Floyd Warshall algorithm with maximum steps allowed

Question

Is it possible to modify Floyd-Warshall algorithm when solving the shortest path problem for a directed weighted graph with n nodes, such that each shortest path have no more than m steps? More precisely, for each pair of nodes i and j, you are about to find the shortest directed path from i to j that contains no more than m nodes. Does time complexity still remain O(n³)?

Answer 1

Meanwhile, I found an O(n³logm) algorithm for finding all-pairs shortest paths (ASPP) problem for the graph with n nodes such that no path contain more than m nodes.

Given two n x n matrices, say A = [a_ij] and B = [b_ij], their distance product is n x n matrix C = [c_ij] = A x B, defined by c_ij = min_1≤k≤n {a_ik + b_kj}.

This is related to the ASPP in the following way. Given weighted matrix E of distances in the graph, Eⁿ is matrix of all-pairs shortest path. If we add constraint that no path contains more than m nodes, then matrix E^m is the solution to ASPP. Since calculating power can be found in O(logm) time, this gives us an O(n³logm) algorithm.

Here, one may find faster algorithms for calculating distance product of matrices in some special cases, but the trivial one O(n³) is enough for me, since overall time is almost as fast as Floyd-Warshall approach.

Answer 2

Yes and Yes.

• Each iteration of the algotithm adds a single unit of length of the paths you search for. So if you limit the iterations to m then you find a path of length at most m.
• The complexity will remain O(n^3) in the worst case of m -> n. However, more precise estimate would be O(m * n^2).

Answer 3

I believe that this could be done with a different data structure (one that would allow you to keep track of the number of steps)?

Since usually Floyd-Warshall is done with a connectivity matrix (where matrix [j][k] represents the distance between nodes j and k), instead of making that matrix an integer we can make it a struct that has two integers : the distance between two nodes and the number of steps between them.

I wrote up something in C++ to explain what I mean :

#define INFINITY 9999999

struct floydEdge
{
    int weight;
    int steps;
};

floydEdge matrix[10][10];

int main()
{
    //We initialize the matrix
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            matrix[j][k].weight=INFINITY;
            matrix[j][k].steps=0;
        }
    }

    //We input some weights
    for(int j=0;j<10;j++)
    {
        int a, b;
        cin>>a>>b;
        cin>>matrix[a][b].weight;
        matrix[b][a].weight=matrix[a][b].weight;
        matrix[a][b].steps=matrix[b][a].steps=1;
    }

    //We do the Floyd-Warshall, also checking for the step count as well as the weights
    for(int j=0;j<10;j++)
    {
        for(int k=0;k<10;k++)
        {
            for(int i=0;i<10;i++)
            {
                //We check if there is a shorter path between nodes j and k, using the node i. We also check if that path is shorter or equal to 4 steps.
                if((matrix[j][k].weight > matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<=4))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
                //If the path is not shorter, we can also check if the path is equal BUT requires less steps than the path we currently have.
                else if((matrix[j][k].weight == matrix[j][i].weight + matrix[i][k].weight) && (matrix[j][i].steps+matrix[i][k].steps<matrix[j][k].steps))
                {
                    matrix[j][k].weight=matrix[k][j].weight=matrix[j][i].weight + matrix[i][k].weight;
                    matrix[j][k].steps=matrix[k][j].steps=matrix[j][i].steps+matrix[i][k].steps;
                }
            }
        }
    }
    return 0;
}

I believe (but I am not completely sure) this works perfectly (always giving the shortest paths for between all nodes). Give it a try and let me know!