# Dynamic Programming: Shortest path with exactly k edges in a directed and weighted graph

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];
}
``````