Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction:
2.
Approach:
3.
FAQs:
4.
Key Takeaways: 
Last Updated: Mar 27, 2024

Find Maximum Shortest Distance in Each Component of a Graph

Author Nishant Rana
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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:-

  1. Shortest DIstance between 1 and 2 => 6
  2. Shortest DIstance between 2 and 3 => 9
  3. Shortest DIstance between 1 and 3 => 3

Hence, the maximum shortest distance for component A is 9.

 

For the component B:-

  1. 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:-

  1. We will first calculate the shortest path between each pair of vertices using the Floyd Warshal Algorithm
  2. Then we will run a DFS Algorithm and store the nodes of each component separately in a 2D vector of vectors.
  3. 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.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs:

  1. What is a Floyd Warshal Algorithm?
    • Floyd Warshal Algorithm is a Dynamic Programming algorithm that is used to find the shortest distance between each pair of vertices of a graph.
  2. What is the time complexity for the approach used?
    • 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.
       

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the approach to find the Maximum Shortest Distance in Each Component of a Graph.
  2. Then we saw how to implement the approach discussed.

 

If you want to learn more about Graphs and want to practice some questions which require you to take your basic knowledge on Graphs a notch higher, then you can visit our Guided Path for Graphs

Check out this problem - Frog Jump

Until then, All the best for your future endeavors, and Keep Coding.







 

Live masterclass