Minimum Cost Path in a directed graph via given set of intermediate nodes | Javascript program to implement the above approach ; Stores minimum - cost of path from source ; Function to Perform BFS on graph g starting from vertex v ; If destination is reached ; Set flag to true ; Visit all the intermediate nodes ; If any intermediate node is not visited ; If all intermediate nodes are visited ; Update the minSum ; Mark the current node visited ; Traverse adjacent nodes ; Mark the neighbour visited ; Find minimum cost path considering the neighbour as the source ; Mark the neighbour unvisited ; Mark the source unvisited ; Stores the graph ; Number of nodes ; Source ; Destination ; Keeps a check on visited and unvisited nodes ; Stores intemediate nodes ; If no path is found
class pair { constructor ( f , s ) { this . first = f ; this . second = s ; } } var minSum = 100000000 ; function getMinPathSum ( graph , visited , necessary , src , dest , currSum ) { if ( src == dest ) { var flag = true ; for ( var i of necessary ) { if ( ! visited [ i ] ) { flag = false ; break ; } } if ( flag ) minSum = Math . min ( minSum , currSum ) ; return ; } else { visited [ src ] = true ; for ( var node of graph [ src ] ) { if ( ! visited [ node . first ] ) { visited [ node . first ] = true ; getMinPathSum ( graph , visited , necessary , node . first , dest , currSum + node . second ) ; visited [ node . first ] = false ; } } visited [ src ] = false ; } } var graph = Array . from ( Array ( 7 ) , ( ) => Array ( ) ) ; graph [ 0 ] . push ( new pair ( 1 , 2 ) ) ; graph [ 0 ] . push ( new pair ( 2 , 3 ) ) ; graph [ 0 ] . push ( new pair ( 3 , 2 ) ) ; graph [ 1 ] . push ( new pair ( 4 , 4 ) ) ; graph [ 1 ] . push ( new pair ( 0 , 1 ) ) ; graph [ 2 ] . push ( new pair ( 4 , 5 ) ) ; graph [ 2 ] . push ( new pair ( 5 , 6 ) ) ; graph [ 3 ] . push ( new pair ( 5 , 7 ) ) ; graph [ 3 ] . push ( new pair ( 0 , 1 ) ) ; graph [ 4 ] . push ( new pair ( 6 , 4 ) ) ; graph [ 5 ] . push ( new pair ( 4 , 2 ) ) ; graph [ 6 ] . push ( new pair ( 7 , 11 ) ) ; var n = 7 ; var source = 0 ; var dest = 6 ; var visited = Array ( n ) . fill ( false ) ; var necessary = [ ] ; necessary . push ( 2 ) ; necessary . push ( 4 ) ; getMinPathSum ( graph , visited , necessary , source , dest , 0 ) ; if ( minSum == 100000000 ) document . write ( - 1 ) ; else document . write ( minSum ) ;