Find the Longest path between any pair of vertices in C++

Welcome to code speedy. Today here we will Find the Longest path between any pair of vertices in C++. Finally, we go through the implementation.

The longest path between vertices in C++

Suppose we noticed a map of cities with cable lines linked with each other in such cases there is no cycle between any two cities. Our task is to find the best possible maximum length of cable.

Let look over the example.

Input : x = 6  
        1 2 3 
        2 3 4
        2 6 2
        6 4 6
        6 5 5
Output: maximum length of cable = 12

Make an undirected graph for a given city map and do DFS from every city to find out the maximum length of cable.

Code for Implementing:

#include<bits/stdc++.h> 
using namespace std; 

void DFS(vector< pair<int,int> > graph[], int src, 
    int prev_len, int *max_len, 
    vector <bool> &visited) 
{ 
  visited[src] = 1; 

   
   
  int curr_len = 0; 


  pair < int, int > adjacent; 

  
  for (int i=0; i<graph[src].size(); i++) 
  { 
     
    adjacent = graph[src][i]; 

    
    if (!visited[adjacent.first]) 
    { 
      
      curr_len = prev_len + adjacent.second; 

       
      DFS(graph, adjacent.first, curr_len, 
        max_len, visited); 
    } 

    
     
    if ((*max_len) < curr_len) 
      *max_len = curr_len; 

     
    curr_len = 0; 
  } 
} 

 
 
int longestCable(vector<pair<int,int> > graph[], 
                    int n) 
{ 
   
  int max_len = INT_MIN; 

   
  for (int i=1; i<=n; i++) 
  { 
     
    vector< bool > visited(n+1, false); 

     
    DFS(graph, i, 0, &max_len, visited); 
  } 

  return max_len; 
} 

 
int main() 
{ 
   
  int n = 6; 

  vector< pair<int,int> > graph[n+1]; 

   
  graph[1].push_back(make_pair(2, 3)); 
  graph[2].push_back(make_pair(1, 3)); 

   
  graph[2].push_back(make_pair(3, 4)); 
  graph[3].push_back(make_pair(2, 4)); 

   
  graph[2].push_back(make_pair(6, 2)); 
  graph[6].push_back(make_pair(2, 2)); 

   
  graph[4].push_back(make_pair(6, 6)); 
  graph[6].push_back(make_pair(4, 6)); 

   
  graph[5].push_back(make_pair(6, 5)); 
  graph[6].push_back(make_pair(5, 5)); 

  cout << "Maximum length of cable = "
    << longestCable(graph, n); 

  return 0; 
} 
OUTPUT:
Maximum length of cable = 12

Also read: C++ Program to check if a matrix is invertible

Leave a Reply

Your email address will not be published. Required fields are marked *