Minimum cost path from source node to destination node via K intermediate nodes | Function to find the minimum cost path from the source vertex to destination vertex via K intermediate vertices ; Initialize the adjacency list ; Generate the adjacency list ; Initialize the minimum priority queue ; Stores the minimum cost to travel between vertices via K intermediate nodes ; Push the starting vertex , cost to reach and the number of remaining vertices ; Pop the top element of the stack ; If destination is reached ; Return the cost ; If all stops are exhausted ; Find the neighbour with minimum cost ; Pruning ; Update cost ; Update priority queue ; If no path exists ; Driver Code ; Function Call to find the path from src to dist via k nodes having least sum of weights
function leastWeightedSumPath ( n , edges , src , dst , K ) { var graph = new Map ( ) ; for ( var edge of edges ) { if ( ! graph . has ( edge [ 0 ] ) ) graph . set ( edge [ 0 ] , new Array ( ) ) var tmp = graph . get ( edge [ 0 ] ) ; tmp . push ( [ edge [ 1 ] , edge [ 2 ] ] ) ; graph . set ( edge [ 0 ] , tmp ) ; } var pq = [ ] ; var costs = Array . from ( Array ( n + 1 ) , ( ) => Array ( K + 2 ) . fill ( 1000000000 ) ) ; costs [ src ] [ K + 1 ] = 0 ; pq . push ( [ 0 , src , K + 1 ] ) ; while ( pq . length != 0 ) { var top = pq [ pq . length - 1 ] ; pq . pop ( ) ; if ( top [ 1 ] == dst ) return top [ 0 ] ; if ( top [ 2 ] == 0 ) continue ; if ( graph . has ( top [ 1 ] ) ) { for ( var neighbor of graph . get ( top [ 1 ] ) ) { if ( costs [ neighbor [ 0 ] ] [ top [ 2 ] - 1 ] < neighbor [ 1 ] + top [ 0 ] ) { continue ; } costs [ neighbor [ 0 ] ] [ top [ 2 ] - 1 ] = neighbor [ 1 ] + top [ 0 ] ; pq . push ( [ neighbor [ 1 ] + top [ 0 ] , neighbor [ 0 ] , top [ 2 ] - 1 ] ) ; } } pq . sort ( ( a , b ) => { if ( a [ 0 ] == b [ 0 ] ) return b [ 1 ] - a [ 1 ] return b [ 0 ] - a [ 0 ] ; } ) ; } return - 1 ; } var n = 3 , src = 0 , dst = 2 , k = 1 ; var edges = [ [ 0 , 1 , 100 ] , [ 1 , 2 , 100 ] , [ 0 , 2 , 500 ] ] ; document . write ( leastWeightedSumPath ( n , edges , src , dst , k ) ) ;