Minimum Cost Path in a directed graph via given set of intermediate nodes | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; pair ( int f , int s ) { this . first = f ; this . second = s ; } } static int minSum = Integer . MAX_VALUE ; static void getMinPathSum ( Map < Integer , ArrayList < pair > > graph , boolean [ ] visited , ArrayList < Integer > necessary , int source , int dest , int currSum ) { if ( src == dest ) { boolean flag = true ; for ( int i : necessary ) { if ( ! visited [ i ] ) { flag = false ; break ; } } if ( flag ) minSum = Math . min ( minSum , currSum ) ; return ; } else { visited [ src ] = true ; for ( pair node : graph . get ( 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 ; } } public static void main ( String [ ] args ) { Map < Integer , ArrayList < pair > > graph = new HashMap < > ( ) ; for ( int i = 0 ; i <= 6 ; i ++ ) graph . put ( i , new ArrayList < pair > ( ) ) ; graph . get ( 0 ) . add ( new pair ( 1 , 2 ) ) ; graph . get ( 0 ) . add ( new pair ( 2 , 3 ) ) ; graph . get ( 0 ) . add ( new pair ( 3 , 2 ) ) ; graph . get ( 1 ) . add ( new pair ( 4 , 4 ) ) ; graph . get ( 1 ) . add ( new pair ( 0 , 1 ) ) ; graph . get ( 2 ) . add ( new pair ( 4 , 5 ) ) ; graph . get ( 2 ) . add ( new pair ( 5 , 6 ) ) ; graph . get ( 3 ) . add ( new pair ( 5 , 7 ) ) ; graph . get ( 3 ) . add ( new pair ( 0 , 1 ) ) ; graph . get ( 4 ) . add ( new pair ( 6 , 4 ) ) ; graph . get ( 5 ) . add ( new pair ( 4 , 2 ) ) ; graph . get ( 6 ) . add ( new pair ( 7 , 11 ) ) ; int n = 7 ; int source = 0 ; int dest = 6 ; boolean [ ] visited = new boolean [ n ] ; ArrayList < Integer > necessary = new ArrayList < > ( Arrays . asList ( 2 , 4 ) ) ; getMinPathSum ( graph , visited , necessary , source , dest , 0 ) ; if ( minSum == Integer . MAX_VALUE ) System . out . println ( - 1 ) ; else System . out . println ( minSum ) ; } }