1.
Introduction:
2.
Approach:
3.
FAQs:
4.
Key Takeaways:
Last Updated: Mar 27, 2024

# Find Maximum Shortest Distance in Each Component of a Graph

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.

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