Minimum Cost Path in a directed graph via given set of intermediate nodes | C # 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 ; Driver code ; Stores the graph ; Number of nodes ; Source ; Destination ; Keeps a check on visited and unvisited nodes ; Stores intemediate nodes ; If no path is found
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { class pair { public int first , second ; public pair ( int f , int s ) { this . first = f ; this . second = s ; } } static int minSum = 100000000 ; static void getMinPathSum ( Dictionary < int , ArrayList > graph , bool [ ] visited , ArrayList necessary , int source , int dest , int currSum ) { if ( src == dest ) { bool flag = true ; foreach ( int i in necessary ) { if ( ! visited [ i ] ) { flag = false ; break ; } } if ( flag ) minSum = Math . Min ( minSum , currSum ) ; return ; } else { visited [ src ] = true ; foreach ( pair node in graph ) { 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 ; } } public static void Main ( string [ ] args ) { Dictionary < int , ArrayList > graph = new Dictionary < int , ArrayList > ( ) ; for ( int i = 0 ; i <= 6 ; i ++ ) graph [ i ] = new ArrayList ( ) ; graph [ 0 ] . Add ( new pair ( 1 , 2 ) ) ; graph [ 0 ] . Add ( new pair ( 2 , 3 ) ) ; graph [ 0 ] . Add ( new pair ( 3 , 2 ) ) ; graph [ 1 ] . Add ( new pair ( 4 , 4 ) ) ; graph [ 1 ] . Add ( new pair ( 0 , 1 ) ) ; graph [ 2 ] . Add ( new pair ( 4 , 5 ) ) ; graph [ 2 ] . Add ( new pair ( 5 , 6 ) ) ; graph [ 3 ] . Add ( new pair ( 5 , 7 ) ) ; graph [ 3 ] . Add ( new pair ( 0 , 1 ) ) ; graph [ 4 ] . Add ( new pair ( 6 , 4 ) ) ; graph [ 5 ] . Add ( new pair ( 4 , 2 ) ) ; graph [ 6 ] . Add ( new pair ( 7 , 11 ) ) ; int n = 7 ; int source = 0 ; int dest = 6 ; bool [ ] visited = new bool [ n ] ; ArrayList necessary = new ArrayList ( ) ; necessary . Add ( 2 ) ; necessary . Add ( 4 ) ; getMinPathSum ( graph , visited , necessary , source , dest , 0 ) ; if ( minSum == 100000000 ) Console . WriteLine ( - 1 ) ; else Console . WriteLine ( minSum ) ; } }