Shortest path with exactly k edges in a directed and weighted graph | Set 2 | Python3 implementation of the above approach ; Function to find the smallest path with exactly K edges ; Array to store dp ; Loop to solve DP ; Initialising next state ; Recurrence relation ; Returning final answer ; Driver code ; Input edges ; Source and Destination ; Number of edges in path ; Calling the function
inf = 100000000 NEW_LINE def smPath ( s , d , ed , n , k ) : NEW_LINE INDENT dis = [ inf ] * ( n + 1 ) NEW_LINE dis [ s ] = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT dis1 = [ inf ] * ( n + 1 ) NEW_LINE for it in ed : NEW_LINE INDENT dis1 [ it [ 1 ] ] = min ( dis1 [ it [ 1 ] ] , dis [ it [ 0 ] ] + it [ 2 ] ) NEW_LINE DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT dis [ i ] = dis1 [ i ] NEW_LINE DEDENT DEDENT if ( dis [ d ] == inf ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return dis [ d ] NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 4 NEW_LINE ed = [ [ 0 , 1 , 10 ] , [ 0 , 2 , 3 ] , [ 0 , 3 , 2 ] , [ 1 , 3 , 7 ] , [ 2 , 3 , 7 ] ] NEW_LINE s = 0 NEW_LINE d = 3 NEW_LINE k = 2 NEW_LINE print ( smPath ( s , d , ed , n , k ) ) NEW_LINE DEDENT