Shortest path with exactly k edges in a directed and weighted graph | Define number of vertices in the graph and inifinite value ; A naive recursive function to count walks from u to v with k edges ; Base cases ; Initialize result ; Go to all adjacents of u and recur ; Driver Code ; 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 if k == 0 and u == v : NEW_LINE INDENT return 0 NEW_LINE DEDENT if k == 1 and graph [ u ] [ v ] != INF : NEW_LINE INDENT return graph [ u ] [ v ] NEW_LINE DEDENT if k <= 0 : NEW_LINE INDENT return INF NEW_LINE DEDENT res = INF NEW_LINE for i in range ( V ) : NEW_LINE INDENT if graph [ u ] [ i ] != INF and u != i and v != i : NEW_LINE INDENT rec_res = shortestPath ( graph , i , v , k - 1 ) NEW_LINE if rec_res != INF : NEW_LINE INDENT res = min ( res , graph [ u ] [ i ] + rec_res ) NEW_LINE DEDENT DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT INF = 999999999999 NEW_LINE 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 DEDENT