Print the Longest Path Between Any Pair of Vertices

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++)
    {
        // Adjacent element
        adj = gph[sc][i];
 
        // If node is not visited
        if (!vis[adj.first])
        {
            curr_len = prev_len + adj.second;
 
            // Call DFS for adjacent nodes
            DFS(gph, adj.first, curr_len,
                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;
}

You can also try this code with Online C++ Compiler

Run Code

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;

		pair adj;

		// Traverse every adjacent node

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

			// If node is unvisited
			if (!vis[adj.x])
			{
				curr_len = prev_len + adj.y;

				// perform dfs for adjacent node
				DFS(gph, adj.x, curr_len, vis);
			}
			// 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++)
		{
			gph.add(new Vector<pair>());
		}

		// create undirected gph
		// first edge
		gph.get(1).add(new pair(2, 9));
		gph.get(2).add(new pair(1, 9));

		// second edge
		gph.get(2).add(new pair(3, 7));
		gph.get(3).add(new pair(2, 7));

		// third edge
		gph.get(2).add(new pair(6, 4));
		gph.get(6).add(new pair(2, 4));

		// fourth edge
		gph.get(4).add(new pair(6, 1));
		gph.get(6).add(new pair(4, 1));

		// fifth edge
		gph.get(5).add(new pair(6, 6));
		gph.get(6).add(new pair(5, 6));

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

You can also try this code with Online Java Compiler

Run Code

Output🖥️

Implementation in Python

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

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

	curr_len = 0

	adjacent = None

	# Traverse all adjacent
	for i in range(len(gph[sr])):

		# Adjacent node
		adjacent = gph[sr][i]

		# If node is unvivisited
		if (not vis[adjacent[0]]):

			curr_len = prev_len + adjacent[1]

			# perform DFS for adjacent node

			DFS(gph, adjacent[0], curr_len, max_len, vis)

		# 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))

You can also try this code with Online Python Compiler

Run Code

Output🖥️

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 */

class AdjListNode {
	int v;
	int weight;

	public:
	AdjListNode(int _v, int _w)
	{
		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

	list<AdjListNode>* adj;

	// 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;
	adj = new list<AdjListNode>[V];
}


Graph::~Graph() // Destructor
{
	delete [] adj;
}

void Graph::addEdge(int u, int v, int weight)
{
	AdjListNode node(v, weight);
	adj[u].push_back(node); // Add v to u's list
}

void Graph::topologicalSortUtil(int v, bool vis[],stack<int>& Stack)
{
	vis[v] = true;
	list<AdjListNode>::iterator i;
	for (i = adj[v].begin(); i != adj[v].end(); ++i) 
	{
		AdjListNode node = *i;
		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

		list<AdjListNode>::iterator i;
		if (dist[u] != NINF) 
		{
			for (i = adj[u].begin(); i != adj[u].end(); ++i)
			{
				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);
	g.addEdge(1, 2, 9);
	g.addEdge(2, 3, 7);
	g.addEdge(2, 6, 4);
	g.addEdge(6, 4, 1);
	g.addEdge(6, 5, 6);

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

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output🖥️

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.

Frequently Asked Questions

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 vertex u comes 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 Graph, DFS Traversal of a Graph - Iteratively, Clone 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! 🥷