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 is19.

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

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⚙️

Make the given graph an undirected graph.

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

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.

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

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

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

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⚙️

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

Sort all of the vertices in topological order.

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

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

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.