Shortest path with exactly k edges in a directed and weighted graph | Set 2 | Javascript implementation of the above approach ; Function to find the smallest path with exactly K edges ; Array to store dp ; Initialising the array ; 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
let inf = 100000000 ; function smPath ( s , d , ed , n , k ) { let dis = new Array ( n + 1 ) ; for ( let i = 0 ; i < ( n + 1 ) ; i ++ ) { dis [ i ] = inf ; } dis [ s ] = 0 ; for ( let i = 0 ; i < k ; i ++ ) { let dis1 = new Array ( n + 1 ) ; for ( let i = 0 ; i < ( n + 1 ) ; i ++ ) { dis1 [ i ] = inf ; } for ( let it = 0 ; it < ed . length ; it ++ ) dis1 [ ed [ it ] [ 1 ] ] = Math . min ( dis1 [ ed [ it ] [ 1 ] ] , dis [ ed [ it ] [ 0 ] ] + ed [ it ] [ 2 ] ) ; document . write ( ) for ( let j = 0 ; j <= n ; j ++ ) dis [ j ] = dis1 [ j ] ; } if ( dis [ d ] == inf ) return - 1 ; else return dis [ d ] ; } let n = 4 ; let ed = [ [ 0 , 1 , 10 ] , [ 0 , 2 , 3 ] , [ 0 , 3 , 2 ] , [ 1 , 3 , 7 ] , [ 2 , 3 , 7 ] ] ; let s = 0 , d = 3 ; let k = 2 ; document . write ( smPath ( s , d , ed , n , k ) ) ;