1.
Introductionđź“–
2.
Problem Statementâť“
2.1.
Sample Exampleđź‘€
2.1.1.
InputâŚ¨ď¸Ź
2.1.2.
Outputđź–Ąď¸Ź
2.1.3.
Explanationđź—’ď¸Ź
2.1.4.
Dry Run
3.
Approachđź”Ť
3.1.
Approach 1â¬‡ď¸Ź
3.1.1.
Algorithmâš™ď¸Ź
3.1.2.
Implementationđź§°
3.1.3.
Outputđź–Ąď¸Ź
3.1.4.
Outputđź–Ąď¸Ź
3.1.5.
Outputđź–Ąď¸Ź
3.1.6.
Time and Space ComplexityâŹł
3.2.
Approach 2â¬‡ď¸Ź
3.2.1.
Algorithmâš™ď¸Ź
3.2.2.
Implementationđź§°
3.2.3.
Outputđź–Ąď¸Ź
3.2.4.
Time and Space ComplexityâŹł
4.
4.1.
What is a Graph?
4.2.
What is the difference between a tree and a graph?
4.3.
What is the difference between a DFS and a BFS traversal?
4.4.
What is a topological sort?
4.5.
What is the maximum number of edges in node N's undirected graph?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Print the Longest Path Between Any Pair of Vertices

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introductionđź“–

This blog is about a graph problem called â€śPrint the longest path betwee any pair of verticesâ€ť. In programming contests and technical interviews, graphs are one of the most important and frequently asked data structures.

There are many common graph problems and techniques. This blog explores a graph problem that explores how to print the longest path between any two vertices.

## Problem Statementâť“

We are given a graph in which nodes are connected via edges so that no two nodes have a cycle. We must find the longest path between any two vertices for a given graph.

### Sample Exampleđź‘€

#### InputâŚ¨ď¸Ź

Let the given graph be the input

#### Outputđź–Ąď¸Ź

The longest path between any two vertices is 19.

#### Explanationđź—’ď¸Ź

We can see in the example that the path with the maximum sum of edge weights is 1-2-6-5, with the longest path between any two vertices being 19.

#### Dry Run

The dry run for the above example is shown in the steps below:

Step 1

Step 2

Step 3

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

## Approachđź”Ť

We can have two approaches to find the longest path between any two vertices. Let us discuss these approaches in detail.

### Approach 1â¬‡ď¸Ź

This approach is a brute force approach. This method will traverse all the graph nodes and find the path with the maximum sum of edge weights with all the other vertices.

#### Algorithmâš™ď¸Ź

1. Make the given graph an undirected graph.

2. Perform DFS Algorithm from each node to find the path with the maximum sum between vertices.

3. While traversing, we look for the total path sum to reach the current node, and if its adjacent node is not visited, we call DFS for it, but if all adjacent nodes for the current node are visited, we call DFS for it.

4. Create a variable max_len and update its value if the previous value of max_len is less than the current total edge weights value.

#### Implementationđź§°

Let's look at the implementation of the above approach.

Implementation in C++

/* C++ program to print the longest path between any pair of vertices */

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

void DFS(vector< pair<int,int> > gph[], int sc, int prev_len, int *max_len, vector<bool>  &vis)
{
// Mark the src node visited

vis[sc] = 1;
int curr_len = 0;

/* Adjacent is a pair type that stores
destination node and edge weight*/

pair < int, int > adj;

for (int i=0; i<gph[sc].size(); i++)
{

// If node is not visited
{

// Call DFS for adjacent nodes
max_len,  vis);
}
/* If total cable length till now greater than
previous length then update it*/

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

// make curr_len = 0 for next adjacent
curr_len = 0;
}
}

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

/* call DFS for each node to find maximum
length of cable */

for (int i=1; i<=n; i++)
{
//initialise visited array with 0
vector< bool > visited(n+1, false);

// Call DFS for src vertex i
DFS(graph, i, 0, &max_len, visited);
}
return max_len;
}

// driver program to test the input

int main()
{
// n is the number of cities

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

/* create an undirected graph
first edge */

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

// second edge

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

// third edge

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

// fourth edge

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

// fifth edge

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

cout << "The longest path between any two vertices is "
<< longestPath(graph, n);

return 0;
}

#### Outputđź–Ąď¸Ź

Implementation in Java

/* Java program to print the longest path between any pair of vertices */
import java.util.*;
public class Main
{
static class pair
{
public int x, y;
public pair(int f, int s)
{
x = f;
y = s;
}
}
static int max_len = Integer.MIN_VALUE;
static void DFS(Vector<Vector<pair>> gph, int sc, int prev_len, boolean[] vis)
{
// Mark the source node as visited
vis[sc] = true;
int curr_len = 0;

for(int i = 0; i < gph.get(sc).size(); i++)
{

// If node is unvisited
{

// perform dfs for adjacent node
}
// update max length

if (max_len < curr_len)
{
max_len = curr_len;
}
curr_len = 0;
}
}
// n is number of nodes in gph

static int longestPath(Vector<Vector<pair>> gph, int n)
{
// call DFS for each node
for (int i=1; i<=n; i++)
{
// initialize visited array with 0
boolean[] vis = new boolean[n+1];

// Call DFS for src vertex i
DFS(gph, i, 0, vis);
}
return max_len;
}

public static void main(String[] args)
{
// n is number of nodes

int n = 7;
Vector<Vector<pair>> gph = new Vector<Vector<pair>>();
for(int j = 0; j < n+1; j++)
{
}

// create undirected gph
// first edge

// second edge

// third edge

// fourth edge

// fifth edge

System.out.print("The longest path between any two vertices is " + longestPath(gph, n));
}
}

#### Outputđź–Ąď¸Ź

Implementation in Python

def DFS(gph, sr, prev_len, max_len, vis):

# Mark the source node visited
vis[sr] = 1

curr_len = 0

for i in range(len(gph[sr])):

# If node is unvivisited

# perform DFS for adjacent node

# update max_len

if (max_len[0] < curr_len):
max_len[0] = curr_len

# make curr_len = 0

curr_len = 0

# n is number of nodes

def longestPath(gph, n):

# maximum length of cable among
# the connected cities

max_len = [-999999999999]

# call DFS for each node

for i in range(1, n + 1):

# initialise visited array with 0

vis = [False] * (n + 1)

# Call DFS for source vertex i

DFS(gph, i, 0, max_len, vis)
return max_len[0]

# Driver Code

if __name__ == '__main__':

# n is number of cities

n = 6
gph = [[] for i in range(n + 1)]

# create undirected graph

# first edge
gph[1].append([2, 9])
gph[2].append([1, 9])

# second edge
gph[2].append([3, 7])
gph[3].append([2, 7])

# third edge
gph[2].append([6, 4])
gph[6].append([2, 4])

# fourth edge
gph[4].append([6, 1])
gph[6].append([4, 1])

# fifth edge
gph[5].append([6, 6])
gph[6].append([5, 6])

print("The longest path between any two vertices is",
longestPath(gph, n))

#### Time and Space ComplexityâŹł

Time Complexity: Time complexity is a type of computational complexity that describes how long it takes to run an algorithm. The time complexity of an algorithm is the amount of time it takes to complete each statement. As a result, the size of the processed data is extremely important. The time complexity of the above code is O(V * (V + E))

Space Complexity: The total amount of memory space used by an algorithm or programme, including the space of input values for execution, is referred to as its space complexity. The space complexity of the code is O(V^2)

### Approach 2â¬‡ď¸Ź

This approach is efficient but is only applicable to directed graphs. We can find the longest path between any two vertices in improvised time complexity.

#### Algorithmâš™ď¸Ź

1. Make a distance array dist and set all its entries to minus infinite.

2. Sort all of the vertices in topological order.

3. Do the following in topological order for each vertex u.

• Perform the following for every adjacent vertex v of u
• if (dis[v] < dis[u] + wght(u, v))
• dis[v] = dis[u] + wght(u, v)

4. Return the largest value from the dist array.

Note: In the third step above the function wght(u,v) describes the weight of the edge u,v and dis[] array stores the distance of any vertex from the source vertex.

#### Implementationđź§°

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

/* Graph is represented using adjacency list. Every
node of the adjacency list contains the vertex number of
the vertex to which the edge connects. It also
weights the edge */

int v;
int weight;

public:
{
v = _v;
weight = _w;
}
int getV() { return v; }
int getWeight() { return weight; }
};

/* Class to represent a graph using adjacency list
representation */

class Graph {
int V; // No. of vertices'

// Pointer to an array containing adjacency lists

// A function used by longestPath

void topologicalSortUtil(int v, bool visited[], stack<int>& Stack);

public:
Graph(int V); // Constructor
~Graph(); // Destructor

void addEdge(int u, int v, int weight);

// Finds longest distances from given source vertex
void longestPath();
};

Graph::Graph(int V) // Constructor
{
this->V = V;
}

Graph::~Graph() // Destructor
{
}

void Graph::addEdge(int u, int v, int weight)
{
}

void Graph::topologicalSortUtil(int v, bool vis[],stack<int>& Stack)
{
vis[v] = true;
{
if (!vis[node.getV()])
topologicalSortUtil(node.getV(), vis, Stack);
}

/* Push current vertex to stack, which stores topological
sort */

Stack.push(v);
}

/* The function to find the longest distances from a given vertex.
It uses recursive topologicalSortUtil() to get topological
sorting. */

void Graph::longestPath()
{
stack<int> Stack;
int dist[V];

// Mark all the vertices as unvisited

bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

/* To store Topological Sort, use the recursive helper function, starting from all vertices one by one.*/

for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
int s = Stack.top();

/* Initialize distances to all vertices as infinite and
distance to source as 0 */

for (int i = 0; i < V; i++)
dist[i] = NINF;
dist[s] = 0;

// Process vertices in topological order

while (Stack.empty() == false)
{
// Get the next vertex from topological order

int u = Stack.top();
Stack.pop();

// Update distances of all adjacent vertices

if (dist[u] != NINF)
{
{
if (dist[i->getV()] < dist[u] + i->getWeight())
dist[i->getV()] = dist[u] + i->getWeight();
}
}
}
// Print the calculated longest distances

int ans = INT_MIN;
for (int i = 0; i < V; i++)
{
if(dist[i]!=NINF)
{
ans = max(ans,dist[i]);
}
}
cout<<ans;
delete [] visited;
}

// Driver program to test the above functions

int main()
{
// Here vertex numbers are 1, 2, 3, 4, 5, 6
Graph g(7);

cout << "The longest path between any two vertices is ";
g.longestPath();

return 0;
}

#### Time and Space ComplexityâŹł

Time Complexity: Time complexity is a type of computational complexity that describes how long it takes to run an algorithm. The time complexity of an algorithm is the amount of time it takes to complete each statement. As a result, the size of the processed data is extremely important. The time complexity of the above code is O(V + E)

Space Complexity: The total amount of memory space used by an algorithm or programme, including the space of input values for execution, is referred to as its space complexity. The space complexity of the code is O(V^2).

Check out this problem - Pair Sum In Array.

### What is a Graph?

A graph is a non-linear data structure composed of nodes and edges. The nodes are also known as vertices; edges are lines or arcs connecting any two nodes in the graph.

### What is the difference between a tree and a graph?

Trees and graphs differ because loops cannot exist in a tree but can live in a graph. A tree's nodes are always connected, whereas a graph's nodes are not.

### What is the difference between a DFS and a BFS traversal?

In a DFS traversal of a graph, we start at any random node and travel as far down each branch as possible before returning to the current node. In a BFS traversal, on the other hand, we visit each node before visiting their children's nodes. A stack is used for DFS traversal, whereas a queue is used for BFS traversal.

### What is a topological sort?

A topological sort, also known as a topological ordering, of a directed graph is a linear ordering of its vertices in which vertexcomes before vertex v when ordering every directed edge uv from vertex u to vertex v.

### What is the maximum number of edges in node N's undirected graph?

In an undirected graph, each node can have the edge over every other n-1 node. As a result, the total number of edges possible is n*(n-1)/2.

## Conclusion

This article extensively discusses a graph problem in which we have to find the longest path between any pair of vertices.

Do you not feel eager to read/explore additional information on the Graph subject after reading about how to find the longest path between any pair of vertices? See the Print All Mother Vertices In The GraphDFS Traversal of a Graph - IterativelyClone of an undirected graph, and Clone a Directed Acyclic Graph.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning Ninja! đźĄ·

Live masterclass