Shortest path with exactly k edges in a directed and weighted graph | 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 ; Let us create the graph shown in above diagram
V = 4 NEW_LINE INF = 999999999999 NEW_LINE def shortestPath ( graph , u , v , k ) : NEW_LINE INDENT global V , INF NEW_LINE sp = [ [ None ] * V for i in range ( V ) ] NEW_LINE for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT sp [ i ] [ j ] = [ None ] * ( k + 1 ) NEW_LINE DEDENT DEDENT for e in range ( k + 1 ) : NEW_LINE INDENT for i in range ( V ) : NEW_LINE INDENT for j in range ( V ) : NEW_LINE INDENT sp [ i ] [ j ] [ e ] = INF NEW_LINE if ( e == 0 and i == j ) : NEW_LINE INDENT sp [ i ] [ j ] [ e ] = 0 NEW_LINE DEDENT if ( e == 1 and graph [ i ] [ j ] != INF ) : NEW_LINE INDENT sp [ i ] [ j ] [ e ] = graph [ i ] [ j ] NEW_LINE DEDENT if ( e > 1 ) : NEW_LINE INDENT for a in range ( V ) : NEW_LINE INDENT if ( graph [ i ] [ a ] != INF and i != a and j != a and sp [ a ] [ j ] [ e - 1 ] != INF ) : NEW_LINE INDENT sp [ i ] [ j ] [ e ] = min ( sp [ i ] [ j ] [ e ] , graph [ i ] [ a ] + sp [ a ] [ j ] [ e - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT DEDENT return sp [ u ] [ v ] [ k ] NEW_LINE DEDENT graph = [ [ 0 , 10 , 3 , 2 ] , [ INF , 0 , INF , 7 ] , [ INF , INF , 0 , 6 ] , [ INF , INF , INF , 0 ] ] NEW_LINE u = 0 NEW_LINE v = 3 NEW_LINE k = 2 NEW_LINE print ( " Weight ▁ of ▁ the ▁ shortest ▁ path ▁ is " , shortestPath ( graph , u , v , k ) ) NEW_LINE