Minimum Cost Path in a directed graph via given set of intermediate nodes | 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
minSum = 1000000000 NEW_LINE def getMinPathSum ( graph , visited , necessary , source , dest , currSum ) : NEW_LINE INDENT global minSum NEW_LINE if ( src == dest ) : NEW_LINE INDENT flag = True ; NEW_LINE for i in necessary : NEW_LINE INDENT if ( not visited [ i ] ) : NEW_LINE INDENT flag = False ; NEW_LINE break ; NEW_LINE DEDENT DEDENT if ( flag ) : NEW_LINE INDENT minSum = min ( minSum , currSum ) ; NEW_LINE DEDENT return ; NEW_LINE DEDENT else : NEW_LINE INDENT visited [ src ] = True ; NEW_LINE for node in graph [ src ] : NEW_LINE INDENT if not visited [ node [ 0 ] ] : NEW_LINE INDENT visited [ node [ 0 ] ] = True ; NEW_LINE getMinPathSum ( graph , visited , necessary , node [ 0 ] , dest , currSum + node [ 1 ] ) ; NEW_LINE visited [ node [ 0 ] ] = False ; NEW_LINE DEDENT DEDENT visited [ src ] = False ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT graph = dict ( ) NEW_LINE graph [ 0 ] = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 3 , 2 ] ] ; NEW_LINE graph [ 1 ] = [ [ 4 , 4 ] , [ 0 , 1 ] ] ; NEW_LINE graph [ 2 ] = [ [ 4 , 5 ] , [ 5 , 6 ] ] ; NEW_LINE graph [ 3 ] = [ [ 5 , 7 ] , [ 0 , 1 ] ] ; NEW_LINE graph [ 4 ] = [ [ 6 , 4 ] ] ; NEW_LINE graph [ 5 ] = [ [ 6 , 2 ] ] ; NEW_LINE graph [ 6 ] = [ [ 7 , 11 ] ] ; NEW_LINE n = 7 ; NEW_LINE source = 0 ; NEW_LINE dest = 6 ; NEW_LINE visited = [ False for i in range ( n + 1 ) ] NEW_LINE necessary = [ 2 , 4 ] ; NEW_LINE getMinPathSum ( graph , visited , necessary , source , dest , 0 ) ; NEW_LINE if ( minSum == 1000000000 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( minSum ) NEW_LINE DEDENT DEDENT