1

I came across this problem of finding the shortest path with exactly k edges. After some searching, I found the code below. It uses a 3D DP. States are there for number of edges used, source vertex and destination vertex. It seems like they have used something like a Floyd Warshall algorithm here. In that case, shouldn't we use the loop order : e {a {i {j {} } } } ? Where a is the loop for the intermediate vertex.

Dynamic Programming based C++ program to find shortest path with exactly k edges
#include <iostream>
#include <climits>
using namespace std;

// Define number of vertices in the graph and inifinite value
#define V 4
#define INF INT_MAX

// A Dynamic programming based function to find the shortest path from
// u to v with exactly k edges.
int shortestPath(int graph[][V], int u, int v, int k)
{
    // Table to be filled up using DP. The value sp[i][j][e] will store
    // weight of the shortest path from i to j with exactly k edges
    int sp[V][V][k+1];

    // Loop for number of edges from 0 to k
    for (int e = 0; e <= k; e++)
    {
        for (int i = 0; i < V; i++)  // for source
        {
            for (int j = 0; j < V; j++) // for destination
            {
                // initialize value
                sp[i][j][e] = INF;

                // from base cases
                if (e == 0 && i == j)
                    sp[i][j][e] = 0;
                if (e == 1 && graph[i][j] != INF)
                    sp[i][j][e] = graph[i][j];

                //go to adjacent only when number of edges is more than 1
                if (e > 1)
                {
                    for (int a = 0; a < V; a++)
                    {
                        // There should be an edge from i to a and a 
                        // should not be same as either i or j
                        if (graph[i][a] != INF && i != a &&
                            j!= a && sp[a][j][e-1] != INF)
                          sp[i][j][e] = min(sp[i][j][e], graph[i][a] +
                                                   sp[a][j][e-1]);
                }
            }
       }
    }
}
return sp[u][v][k];
}

1 Answer 1

1

In a standard Floyd-Warshall implementation that order does indeed matter ( the loops need to be intermediate{source{destination}} ). This question has already been answered here

Floyd Warshall optimizes cost by trying to optimize the cost from i to j through another vertex k. so esentially it's also doing it in an ascending way in terms of the number of edges.

Here however, the order does not really matter because you already have the information for e-1 edges already calculated so you have all the information you need in order to calculate the optimal cost.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.