Given an adjacency matrix graph[][] of a weighted graph consisting of N nodes and positive weights, the task for each connected component of the graph is to find the maximum among all possible shortest distances between every pair of nodes.
Examples:
Input:
Output:
8 0 11
Explanation: There are three components in the graph namely a, b, c. In component (a) the shortest paths are following:
- The shortest distance between 3 and 4 is 5 units.
- The shortest distance between 3 and 1 is 1+5=6 units.
- The shortest distance between 3 and 5 is 5+3=8 units.
- The shortest distance between 1 and 4 is 1 unit.
- The shortest distance between 1 and 5 is 1+3=4 units.
- The shortest distance between 4 and 5 is 3 units.
Out of these shortest distances:
The maximum shortest distance in component (a) is 8 units between node 3 and node 5.
Similarly,
The maximum shortest distance in component (b) is 0 units.
The maximum shortest distance in component (c) is 11 units between nodes 2 and 6.Input:
Output:
7
Explanation: Since, there is only one component with 2 nodes having an edge between them of distance 7. Therefore, the answer will be 7.
Approach: This given problem can be solved by finding the connected components in the graph using DFS and store the components in a list of lists. Floyd Warshall’s Algorithm can be used to find all-pairs shortest paths in each connected component which is based on Dynamic Programming. After getting the shortest distances of all possible pairs in the graph, find the maximum shortest distances for each and every component in the graph. Follow the steps below to solve the problem:
- Define a function maxInThisComponent(vector<int> component, vector<vector<int>> graph) and perform the following steps:
- Initialize the variable maxDistance as INT_MIN and n as the size of the component.
- Iterate over the range [0, n) using the variable i and perform the following tasks:
- Iterate over the range [i+1, n) using the variable j and update the value of maxDistance as the maximum of maxDistance or graph[component[i]][component[j]].
- Return the value of maxDistance as the answer.
- Initialize a vector visited of size N and initialize the values as false.
- Initialize vectors, say components[][] and temp[] to store each component of the graph.
- Using Depth First Search(DFS) find all the components and store them in the vector components[][].
- Now, call the function floydWarshall(graph, V) to implement Floyd Warshall algorithm to find the shortest distance between all pairs of a component of a graph.
- Initialize a vector result[] to store the result.
- Initialize the variable numOfComp as the size of the vector components[][].
- Iterate over the range [0, numOfComp) using the variable i and call the function maxInThisComponent(components[i], graph) and store the value returned by it in the vector result[].
- After performing the above steps, print the values of the vector result[] as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Below dfs function will be used to// get the connected components of a// graph and stores all the connected// nodes in the vector componentvoid dfs(int src, vector<bool>& visited, vector<vector<int> >& graph, vector<int>& component, int N){ // Mark this vertex as visited visited[src] = true; // Put this node in component vector component.push_back(src); // For all other vertices in graph for (int dest = 0; dest < N; dest++) { // If there is an edge between // src and dest i.e., the value // of graph[u][v]!=INT_MAX if (graph[src][dest] != INT_MAX) { // If we haven't visited dest // then recursively apply // dfs on dest if (!visited[dest]) dfs(dest, visited, graph, component, N); } }}// Below is the Floyd Warshall Algorithm// which is based on Dynamic Programmingvoid floydWarshall( vector<vector<int> >& graph, int N){ // For every vertex of graph find // the shortest distance with // other vertices for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Taking care of integer // overflow if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX) { // Update distance between // vertex i and j if choosing // k as an intermediate vertex // make a shorter distance if (graph[i][k] + graph[k][j] < graph[i][j]) graph[i][j] = graph[i][k] + graph[k][j]; } } } }}// Function to find the maximum shortest// path distance in a component by checking// the shortest distances between all// possible pairs of nodesint maxInThisComponent(vector<int>& component, vector<vector<int> >& graph){ int maxDistance = INT_MIN; int n = component.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { maxDistance = max(maxDistance, graph[component[i]][component[j]]); } } // If the maxDistance is still INT_MIN // then return 0 because this component // has a single element return (maxDistance == INT_MIN ? 0 : maxDistance);}// 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 componentvector<int> maximumShortesDistances( vector<vector<int> >& graph, int N){ // Find the connected components vector<bool> visited(N, false); vector<vector<int> > components; // For storing the nodes in a // particular component vector<int> temp; // Now for each unvisited node run // the dfs to get the connected // component having this unvisited node for (int i = 0; i < N; i++) { if (!visited[i]) { // First of all clear the temp temp.clear(); dfs(i, visited, graph, temp, N); components.push_back(temp); } } // Now for all-pair find the shortest // path distances using Floyd Warshall floydWarshall(graph, N); // Now for each component find the // maximum shortest distance and // store it in result vector<int> result; int numOfComp = components.size(); int maxDistance; for (int i = 0; i < numOfComp; i++) { maxDistance = maxInThisComponent(components[i], graph); result.push_back(maxDistance); } return result;}// Driver Codeint main(){ int N = 8; const int inf = INT_MAX; // Adjacency Matrix for the first // graph in the examples vector<vector<int> > 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 }, }; // Find the maximum shortest distances vector<int> result1 = maximumShortesDistances(graph1, N); // Printing the maximum shortest path // distances for each components for (int mx1 : result1) cout << mx1 << ' '; return 0;} |
Java
// Java code for the above approach:import java.util.*;public class Main { static boolean[] visited; // For storing the connected components static ArrayList <ArrayList <Integer> > components; // Below dfs function will be used to // get the connected components of a // graph and stores all the connected // nodes in the vector component static void dfs(int[][] graph, ArrayList<Integer> temp,int src, int N) { // Mark this vertex as visited visited[src] = true; // Put this node in component vector temp.add(src); // For all other vertices in graph for (int dest = 0; dest < N; dest++) { // If there is an edge between // src and dest i.e., the value // of graph[u][v]!=Integer.MAX_VALUE if (graph[src][dest] != Integer.MAX_VALUE) { // If we haven't visited dest // then recursively apply // dfs on dest if (!visited[dest]) dfs(graph, temp, dest, N); } } } // Below is the Floyd Warshall Algorithm // which is based on Dynamic Programming static void floydWarshall(int[][] graph, int N) { // For every vertex of graph find // the shortest distance with // other vertices for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Taking care of integer // overflow if (graph[i][k] != Integer.MAX_VALUE && graph[k][j] != Integer.MAX_VALUE) { // Update distance between // vertex i and j if choosing // k as an intermediate vertex // make a shorter distance if (graph[i][k] + graph[k][j] < graph[i][j]) graph[i][j] = graph[i][k] + graph[k][j]; } } } } } // Function to find the maximum shortest // path distance in a component by checking // the shortest distances between all // possible pairs of nodes static int maxInThisComponent(int[][] graph, ArrayList <Integer> component) { int maxDistance = Integer.MIN_VALUE; int n = component.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { maxDistance = Math.max(maxDistance, graph[component.get(i)][component.get(j)]); } } // If the maxDistance is still Integer.MIN_VALUE // then return 0 because this component // has a single element return (maxDistance == Integer.MIN_VALUE ? 0 : maxDistance); } // 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 static ArrayList <Integer> maximumShortesDistances(int[][] graph, int N) { visited = new boolean[N]; Arrays.fill(visited, false); // Find the connected components components = new ArrayList <ArrayList<Integer> > (); // Now for each unvisited node run // the dfs to get the connected // component having this unvisited node for (int i = 0; i < N; i++) { if (!visited[i] ) { // For storing the nodes in a // particular component ArrayList<Integer> temp = new ArrayList<Integer> (); dfs(graph, temp, i, N); components.add(temp); } } // Now for all-pair find the shortest // path distances using Floyd Warshall floydWarshall(graph, N); // Now for each component find the // maximum shortest distance and // store it in result ArrayList <Integer> result = new ArrayList <Integer> (); int numOfComp = components.size(); int maxDistance; for (int i = 0; i < numOfComp; i++) { maxDistance = maxInThisComponent(graph, components.get(i)); result.add(maxDistance); } return result; } // Driver Code public static void main(String args[]) { int N = 8; final int inf = Integer.MAX_VALUE; // Adjacency Matrix for the first // graph in the examples int[][] graph = { { 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 }, }; // Find the maximum shortest distances ArrayList <Integer> result1 = maximumShortesDistances(graph, N); // Printing the maximum shortest path // distances for each components for (int mx1 : result1) System.out.print(mx1 + " "); }}// This code has been contributed by Sachin Sahara (sachin801) |
Python3
## Python program for the above approach:INT_MAX = 9223372036854775807INT_MIN = -9223372036854775808## Below dfs function will be used to## get the connected components of a## graph and stores all the connected## nodes in the vector componentdef dfs(src, visited, graph, component, N): ## Mark this vertex as visited visited[src] = True ## Put this node in component vector component.append(src); ## For all other vertices in graph for dest in range(0, N): ## If there is an edge between ## src and dest i.e., the value ## of graph[u][v]!=INT_MAX if (graph[src][dest] != INT_MAX): ## If we haven't visited dest ## then recursively apply ## dfs on dest if not visited[dest]: dfs(dest, visited, graph, component, N);## Below is the Floyd Warshall Algorithm## which is based on Dynamic Programmingdef floydWarshall(graph, N): ## For every vertex of graph find ## the shortest distance with ## other vertices for k in range(0, N): for i in range(0, N): for j in range(0, N): ## Taking care of integer ## overflow if (graph[i][k] != INT_MAX and graph[k][j] != INT_MAX): ## Update distance between ## vertex i and j if choosing ## k as an intermediate vertex ## make a shorter distance if (graph[i][k] + graph[k][j] < graph[i][j]): graph[i][j] = graph[i][k] + graph[k][j];## Function to find the maximum shortest## path distance in a component by checking## the shortest distances between all## possible pairs of nodesdef maxInThisComponent(component, graph): maxDistance = INT_MIN; n = len(component); for i in range(0, n): for j in range(i+1, n): maxDistance = max(maxDistance, graph[component[i]][component[j]]) ## If the maxDistance is still INT_MIN ## then return 0 because this component ## has a single element if maxDistance == INT_MIN: return 0 return maxDistance## 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 componentdef maximumShortesDistances(graph, N): ## Find the connected components visited = [] for i in range(0, N): visited.append(False) components = [] ## Now for each unvisited node run ## the dfs to get the connected ## component having this unvisited node for i in range(0, N): if not visited[i]: ## For storing the nodes in a ## particular component temp = [] dfs(i, visited, graph, temp, N) components.append(temp) ## Now for all-pair find the shortest ## path distances using Floyd Warshall floydWarshall(graph, N) ## Now for each component find the ## maximum shortest distance and ## store it in result result = [] numOfComp = len(components) maxDistance = 0 for i in range(0, numOfComp): maxDistance = maxInThisComponent(components[i], graph) result.append(maxDistance) return result## Driver codeif __name__=='__main__': N = 8 inf = INT_MAX; ## Adjacency Matrix for the first ## graph in the examples 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 ], ]; ## Find the maximum shortest distances result1 = maximumShortesDistances(graph1, N); ## Printing the maximum shortest path ## distances for each components for mx1 in result1: print(mx1, end = " ") print("") # This code is contributed by subhamgoyal2014. |
Javascript
<script>// Javascript program for the above approach// Below dfs function will be used to// get the connected components of a// graph and stores all the connected// nodes in the vector componentfunction dfs(src, visited, graph, component, N){ // Mark this vertex as visited visited[src] = true; // Put this node in component vector component.push(src); // For all other vertices in graph for (let dest = 0; dest < N; dest++) { // If there is an edge between // src and dest i.e., the value // of graph[u][v]!=INT_MAX if (graph[src][dest] != Number.MAX_SAFE_INTEGER) { // If we haven't visited dest // then recursively apply // dfs on dest if (!visited[dest]) dfs(dest, visited, graph, component, N); } }}// Below is the Floyd Warshall Algorithm// which is based on Dynamic Programmingfunction floydWarshall(graph, N){ // For every vertex of graph find // the shortest distance with // other vertices for (let k = 0; k < N; k++) { for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { // Taking care of integer // overflow if (graph[i][k] != Number.MAX_SAFE_INTEGER && graph[k][j] != Number.MAX_SAFE_INTEGER) { // Update distance between // vertex i and j if choosing // k as an intermediate vertex // make a shorter distance if (graph[i][k] + graph[k][j] < graph[i][j]) graph[i][j] = graph[i][k] + graph[k][j]; } } } }}// Function to find the maximum shortest// path distance in a component by checking// the shortest distances between all// possible pairs of nodesfunction 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]]); } } // If the maxDistance is still INT_MIN // then return 0 because this component // has a single element return maxDistance == Number.MIN_SAFE_INTEGER ? 0 : maxDistance;}// 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 componentfunction maximumShortesDistances(graph, N) { // Find the connected components let visited = new Array(N).fill(false); let components = new Array(); // For storing the nodes in a // particular component let temp = []; // Now for each unvisited node run // the dfs to get the connected // component having this unvisited node for (let i = 0; i < N; i++) { if (!visited[i]) { // First of all clear the temp temp = []; dfs(i, visited, graph, temp, N); components.push(temp); } } // Now for all-pair find the shortest // path distances using Floyd Warshall floydWarshall(graph, N); // Now for each component find the // maximum shortest distance and // store it in result 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;}// Driver Codelet N = 8;const inf = Number.MAX_SAFE_INTEGER;// Adjacency Matrix for the first// graph in the exampleslet 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],];// Find the maximum shortest distanceslet result1 = maximumShortesDistances(graph1, N);// Printing the maximum shortest path// distances for each componentsfor (mx1 of result1) document.write(mx1 + " ");// This code is contributed by gfgking.</script> |
C#
using System;using System.Collections.Generic;public class Graph { public int N; public int[, ] graph; public bool[] visited; public List<int> component; public Graph(int N) { this.N = N; graph = new int[N, N]; visited = new bool[N]; component = new List<int>(); } public void dfs(int src) { visited[src] = true; component.Add(src); for (int dest = 0; dest < N; dest++) { if (graph[src, dest] != Int32.MaxValue && !visited[dest]) dfs(dest); } } public void floydWarshall() { for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (graph[i, k] != Int32.MaxValue && graph[k, j] != Int32.MaxValue) if (graph[i, k] + graph[k, j] < graph[i, j]) graph[i, j] = graph[i, k] + graph[k, j]; } public int maxInThisComponent(List<int> component) { int maxDistance = Int32.MinValue; int n = component.Count; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) maxDistance = Math.Max( maxDistance, graph[component[i], component[j]]); return maxDistance == Int32.MinValue ? 0 : maxDistance; } public List<int> maximumShortesDistances() { List<List<int> > components = new List<List<int> >(); List<int> temp = new List<int>(); for (int i = 0; i < N; i++) { if (!visited[i]) { temp.Clear(); dfs(i); components.Add(new List<int>(component)); component.Clear(); } } floydWarshall(); List<int> result = new List<int>(); int numOfComp = components.Count; int maxDistance; for (int i = 0; i < numOfComp; i++) { maxDistance = maxInThisComponent(components[i]); result.Add(maxDistance); } return result; }}class Program { static void Main(string[] args) { int N = 8; int inf = int.MaxValue; // Adjacency Matrix for the first graph in the // examples int[, ] graph1 = new int[, ] { { 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 }, }; Graph g = new Graph(N); g.graph = graph1; // Find the maximum shortest distances List<int> result1 = g.maximumShortesDistances(); // Printing the maximum shortest path distances for // each component foreach(int mx1 in result1) { Console.Write(mx1 + " "); } }} |
Output
11 8 0
Time Complexity: O(N3), where N is the number of vertices in the graph.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
