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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minSum = INT_MAX ; void getMinPathSum ( unordered_map < int , vector < pair < int , int > > > & graph , vector < bool > & visited , vector < int > necessary , int src , int dest , int currSum ) { if ( src == dest ) { bool flag = true ; for ( int i : necessary ) { if ( ! visited [ i ] ) { flag = false ; break ; } } if ( flag ) minSum = min ( minSum , currSum ) ; return ; } else { visited [ src ] = true ; for ( auto node : 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 ; } } int main ( ) { unordered_map < int , vector < pair < int , int > > > graph ; graph [ 0 ] = { { 1 , 2 } , { 2 , 3 } , { 3 , 2 } } ; graph [ 1 ] = { { 4 , 4 } , { 0 , 1 } } ; graph [ 2 ] = { { 4 , 5 } , { 5 , 6 } } ; graph [ 3 ] = { { 5 , 7 } , { 0 , 1 } } ; graph [ 4 ] = { { 6 , 4 } } ; graph [ 5 ] = { { 6 , 2 } } ; graph [ 6 ] = { { 7 , 11 } } ; int n = 7 ; int source = 0 ; int dest = 6 ; vector < bool > visited ( n , false ) ; vector < int > necessary { 2 , 4 } ; getMinPathSum ( graph , visited , necessary , source , dest , 0 ) ; if ( minSum == INT_MAX ) cout << " - 1 STRNEWLINE " ; else cout << minSum << ' ' ; return 0 ; }