Shortest path with exactly k edges in a directed and weighted graph | Dynamic Programming based C ++ program to find shortest path with exactly k edges ; Define number of vertices in the graph and inifinite value ; A Dynamic programming based function to find the shortest path from u to v with exactly k edges . ; 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 ; Loop for number of edges from 0 to k ; for source ; for destination ; initialize value ; from base cases ; go to adjacent only when number of edges is more than 1 ; There should be an edge from i to a and a should not be same as either i or j ; driver program to test above function ; Let us create the graph shown in above diagram
#include <iostream> NEW_LINE #include <climits> NEW_LINE using namespace std ; #define V  4 NEW_LINE #define INF  INT_MAX NEW_LINE int shortestPath ( int graph [ ] [ V ] , int u , int v , int k ) { int sp [ V ] [ V ] [ k + 1 ] ; for ( int e = 0 ; e <= k ; e ++ ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { sp [ i ] [ j ] [ e ] = INF ; if ( e == 0 && i == j ) sp [ i ] [ j ] [ e ] = 0 ; if ( e == 1 && graph [ i ] [ j ] != INF ) sp [ i ] [ j ] [ e ] = graph [ i ] [ j ] ; if ( e > 1 ) { for ( int a = 0 ; a < V ; a ++ ) { 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 ] ; } int main ( ) { int graph [ V ] [ V ] = { { 0 , 10 , 3 , 2 } , { INF , 0 , INF , 7 } , { INF , INF , 0 , 6 } , { INF , INF , INF , 0 } } ; int u = 0 , v = 3 , k = 2 ; cout << shortestPath ( graph , u , v , k ) ; return 0 ; }