Longest path between any pair of vertices | visited [ ] array to make nodes visited src is starting node for DFS traversal prev_len is sum of cable length till current node max_len is pointer which stores the maximum length of cable value after DFS traversal ; Mark the src node visited ; curr_len is for length of cable from src city to its adjacent city ; Adjacent is pair type which stores destination city and cable length ; Traverse all adjacent ; Adjacent element ; If node or city is not visited ; Total length of cable from src city to its adjacent ; Call DFS for adjacent city ; If total cable length till now greater than previous length then update it ; make curr_len = 0 for next adjacent ; n is number of cities or nodes in graph cable_lines is total cable_lines among the cities or edges in graph ; maximum length of cable among the connected cities ; call DFS for each city to find maximum length of cable ; initialize visited array with 0 ; Call DFS for src vertex i ; Driver Code ; n is number of cities ; create undirected graph first edge ; second edge ; third edge ; fourth edge ; fifth edge
def DFS ( graph , src , prev_len , max_len , visited ) : NEW_LINE INDENT visited [ src ] = 1 NEW_LINE curr_len = 0 NEW_LINE adjacent = None NEW_LINE for i in range ( len ( graph [ src ] ) ) : NEW_LINE INDENT adjacent = graph [ src ] [ i ] NEW_LINE if ( not visited [ adjacent [ 0 ] ] ) : NEW_LINE INDENT curr_len = prev_len + adjacent [ 1 ] NEW_LINE DFS ( graph , adjacent [ 0 ] , curr_len , max_len , visited ) NEW_LINE DEDENT if ( max_len [ 0 ] < curr_len ) : NEW_LINE INDENT max_len [ 0 ] = curr_len NEW_LINE DEDENT curr_len = 0 NEW_LINE DEDENT DEDENT def longestCable ( graph , n ) : NEW_LINE INDENT max_len = [ - 999999999999 ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT visited = [ False ] * ( n + 1 ) NEW_LINE DFS ( graph , i , 0 , max_len , visited ) NEW_LINE DEDENT return max_len [ 0 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 6 NEW_LINE graph = [ [ ] for i in range ( n + 1 ) ] NEW_LINE graph [ 1 ] . append ( [ 2 , 3 ] ) NEW_LINE graph [ 2 ] . append ( [ 1 , 3 ] ) NEW_LINE graph [ 2 ] . append ( [ 3 , 4 ] ) NEW_LINE graph [ 3 ] . append ( [ 2 , 4 ] ) NEW_LINE graph [ 2 ] . append ( [ 6 , 2 ] ) NEW_LINE graph [ 6 ] . append ( [ 2 , 2 ] ) NEW_LINE graph [ 4 ] . append ( [ 6 , 6 ] ) NEW_LINE graph [ 6 ] . append ( [ 4 , 6 ] ) NEW_LINE graph [ 5 ] . append ( [ 6 , 5 ] ) NEW_LINE graph [ 6 ] . append ( [ 5 , 5 ] ) NEW_LINE print ( " Maximum ▁ length ▁ of ▁ cable ▁ = " , longestCable ( graph , n ) ) NEW_LINE DEDENT