Introduction:
We are given an Adjacency Matrix of a Weighted Graph containing N nodes. We need to find the maximum shortest distance for each disconnected component in the graph.
Let us see an example:-
Input:
Output: [9, 1, 0]
Explanation:
For the component A:-
- Shortest DIstance between 1 and 2 => 6
- Shortest DIstance between 2 and 3 => 9
- Shortest DIstance between 1 and 3 => 3
Hence, the maximum shortest distance for component A is 9.
For the component B:-
- Shortest between 4 and 5 => 1
Hence, the maximum shortest distance for component B is 1.
For component C, there is only 1 node. Hence, the maximum shortest distance for component B is 0.
Input:
Output:
[7]
Explanation:
There is only one connected component and 7 is the maximum shortest distance in this graph.
Approach:
We will solve this question using the following steps:-
- We will first calculate the shortest path between each pair of vertices using the Floyd Warshal Algorithm.
- Then we will run a DFS Algorithm and store the nodes of each component separately in a 2D vector of vectors.
- Then for each component, we will find the maximum shortest distance between all the nodes using the precalculation we did to find the shortest path between each pair of vertices.
Refer to the below implementation of the above approach.
|
#include <bits/stdc++.h> using namespace std; /* This function will help us to find the nodes of each curComponent and store them in the curComponent vector. */ void dfs(int src, vector<bool>& visited, vector<vector<int> >& adjList, vector<int>& curComponent, int N) { // Marking the vertex to be visited visited[src] = true; // Adding this node to the current curComponent curComponent.push_back(src); // Visiting the neighbors of the current vertex. for (int dest = 0; dest < N; dest++) { if (adjList[src][dest] != INT_MAX) { /* We will visit the neighbor node is not visited already. */ if (!visited[dest]) dfs(dest, visited, adjList, curComponent, N); } } } /* This function will help us to find the Shortest path between each pair of vertices. */ void floydWarshall(vector<vector<int> >& adjList, int N) { 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 (adjList[i][k] != INT_MAX && adjList[k][j] != INT_MAX) { /* We will update the distance between i and j if the distance taking k as the intermediary node is less. */ if (adjList[i][k] + adjList[k][j] < adjList[i][j]) adjList[i][j] = adjList[i][k] + adjList[k][j]; } } } } } /* This function will find the maximum shortest path of a curComponent by considering the distance between all pairs of vertices. */ int maxShortest(vector<int>& curComponent, vector<vector<int> >& adjList) { int maxDist = INT_MIN; int n = curComponent.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { maxDist = max(maxDist, adjList[curComponent[i]][curComponent[j]]); } } /* If the value of maxDist is still INT_MIN then return 0 because this curComponent has a single element */ return (maxDist == INT_MIN ? 0 : maxDist); } vector<int> maximumShortesDistances(vector<vector<int>>& adjList, int N) { // Find the connected components vector<bool> visited(N, false); vector<vector<int> > components; // For storing the nodes in a particular curComponent vector<int> temp; /* Running the dfs() function for each unvisited node to find the nodes of that curComponent. */ for (int i = 0; i < N; i++) { if (!visited[i]) { // First of all clear the temp temp.clear(); dfs(i, visited, adjList, temp, N); components.push_back(temp); } } /* Calling the floydWarshall() function to find the shortest path between each pair of vertices. */ floydWarshall(adjList, N); /* Now for each curComponent find the maximum shortest distance and store it in result */ vector<int> result; int numOfComp = components.size(); int maxDist; for (int i = 0; i < numOfComp; i++) { maxDist = maxShortest(components[i], adjList); result.push_back(maxDist); } return result; } |
Time Complexity: The time complexity for the above approach is O(N ^ 3) (Where N is the number of nodes in the graph) because we are running the Floyd Warshal algorithm which is an O(N ^ 3) algorithm.
Space Complexity: The space complexity of the above algorithm is O(N) because we are storing all the nodes in a vector of components.
34+ registered 
