Maximum cost path in an Undirected Graph such that no edge is visited twice in a row | Javascript program for the above approach ; To store the resulting sum of the cost ; To store largest cost leaf vertex ; DFS Traversal to find the update the maximum cost of from any node to leaf ; Mark vertex as visited ; Store vertex initial cost ; Initially assuming edge not to be traversed ; Back edge found so , edge can be part of traversal ; New vertex is found ; Bitwise AND the current check with the returned check by the previous DFS Call ; Adds parent and its children cost ; Updates total cost of parent including child nodes ; Edge is part of the cycle ; push cost of vertex to the answer ; Updates the largest cost leaf vertex ; Function to find the maximum cost from source vertex such that no two edges is traversed twice ; DFS call ; Print the maximum cost ; Driver Code ; Cost Array ; Given Graph ; Given Source Node ; Function call
var N = 100000 ; var canTake = 0 ; var best = 0 ; var dp = Array ( N ) . fill ( 0 ) ; var vis = Array ( N ) . fill ( false ) ; function dfs ( g , cost , u , pre ) { vis [ u ] = true ; dp [ u ] = cost [ u ] ; var check = true ; var cur = cost [ u ] ; for ( var x of g [ u ] ) { if ( vis [ x ] && x != pre ) { check = false ; } else if ( ! vis [ x ] ) { check = dfs ( g , cost , x , u ) ? false : true ; cur = Math . max ( cur , cost [ u ] + dp [ x ] ) ; } } dp [ u ] = cur ; if ( ! check ) { canTake += cost [ u ] ; } else { best = Math . max ( best , dp [ u ] ) ; } return check ; } function FindMaxCost ( g , cost , source ) { dfs ( g , cost , source , - 1 ) ; document . write ( canTake + best ) ; } var n = 5 , m = 5 ; var cost = [ 2 , 2 , 8 , 6 , 9 ] ; var g = Array . from ( Array ( n ) , ( ) => Array ( ) ) ; g [ 0 ] . push ( 1 ) ; g [ 1 ] . push ( 0 ) ; g [ 0 ] . push ( 2 ) ; g [ 2 ] . push ( 0 ) ; g [ 0 ] . push ( 3 ) ; g [ 3 ] . push ( 0 ) ; g [ 1 ] . push ( 2 ) ; g [ 2 ] . push ( 1 ) ; g [ 1 ] . push ( 4 ) ; g [ 4 ] . push ( 1 ) ; var source = 1 ; FindMaxCost ( g , cost , source ) ;