Find Maximum Shortest Distance in Each Component of a Graph | Below dfs function will be used to get the connected components of a graph and stores all the connected nodes in the vector component ; Mark this vertex as visited ; Put this node in component vector ; For all other vertices in graph ; If there is an edge between src and dest i . e . , the value of graph [ u ] [ v ] != INT_MAX ; If we haven 't visited dest  then recursively apply  dfs on dest ; Below is the Floyd Warshall Algorithm which is based on Dynamic Programming ; For every vertex of graph find the shortest distance with other vertices ; Taking care of interger overflow ; Update distance between vertex i and j if choosing k as an intermediate vertex make a shorter distance ; Function to find the maximum shortest path distance in a component by checking the shortest distances between all possible pairs of nodes ; If the maxDistance is still INT_MIN then return 0 because this component has a single element ; Below function uses above two method to get the maximum shortest distances in each component of the graph the function returns a vector , where each element denotes maximum shortest path distance for a component ; Find the connected components ; For storing the nodes in a particular component ; Now for each unvisited node run the dfs to get the connected component having this unvisited node ; First of all clear the temp ; Now for all - pair find the shortest path distances using Floyd Warshall ; Now for each component find the maximum shortest distance and store it in result ; Driver Code ; Adjacency Matrix for the first graph in the examples ; Find the maximum shortest distances ; Printing the maximum shortest path distances for each components
function dfs ( src , visited , graph , component , N ) { visited [ src ] = true ; component . push ( src ) ; for ( let dest = 0 ; dest < N ; dest ++ ) { if ( graph [ src ] [ dest ] != Number . MAX_SAFE_INTEGER ) { if ( ! visited [ dest ] ) dfs ( dest , visited , graph , component , N ) ; } } } function floydWarshall ( graph , N ) { for ( let k = 0 ; k < N ; k ++ ) { for ( let i = 0 ; i < N ; i ++ ) { for ( let j = 0 ; j < N ; j ++ ) { if ( graph [ i ] [ k ] != Number . MAX_SAFE_INTEGER && graph [ k ] [ j ] != Number . MAX_SAFE_INTEGER ) { if ( graph [ i ] [ k ] + graph [ k ] [ j ] < graph [ i ] [ j ] ) graph [ i ] [ j ] = graph [ i ] [ k ] + graph [ k ] [ j ] ; } } } } } function maxInThisComponent ( component , graph ) { let maxDistance = Number . MIN_SAFE_INTEGER ; let n = component . length ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { maxDistance = Math . max ( maxDistance , graph [ component [ i ] ] [ component [ j ] ] ) ; } } return maxDistance == Number . MIN_SAFE_INTEGER ? 0 : maxDistance ; } function maximumShortesDistances ( graph , N ) { let visited = new Array ( N ) . fill ( false ) ; let components = new Array ( ) ; let temp = [ ] ; for ( let i = 0 ; i < N ; i ++ ) { if ( ! visited [ i ] ) { temp = [ ] ; dfs ( i , visited , graph , temp , N ) ; components . push ( temp ) ; } } floydWarshall ( graph , N ) ; let result = [ ] ; let numOfComp = components . length ; let maxDistance ; for ( let i = 0 ; i < numOfComp ; i ++ ) { maxDistance = maxInThisComponent ( components [ i ] , graph ) ; result . push ( maxDistance ) ; } return result ; } let N = 8 ; const inf = Number . MAX_SAFE_INTEGER ; let graph1 = [ [ 0 , inf , 9 , inf , inf , inf , 3 , inf ] , [ inf , 0 , inf , 10 , 1 , 8 , inf , inf ] , [ 9 , inf , 0 , inf , inf , inf , 11 , inf ] , [ inf , 10 , inf , 0 , 5 , 13 , inf , inf ] , [ inf , 1 , inf , 5 , 0 , 3 , inf , inf ] , [ 8 , inf , inf , 13 , 3 , 0 , inf , inf ] , [ 3 , inf , 11 , inf , inf , inf , 0 , inf ] , [ inf , inf , inf , inf , inf , inf , inf , 0 ] , ] ; let result1 = maximumShortesDistances ( graph1 , N ) ; for ( mx1 of result1 ) document . write ( mx1 + " " ) ;