Last Updated: 8 Dec, 2020

Longest Path

Moderate

Asked in companies

Solve now

Problem statement

You are given a Directed Acyclic Graph (DAG) with ‘E’ edges and ‘V’ vertices. A DAG is a type of graph with no directed cycles.

You have been given a source vertex ‘S’. Your task is to find the distance between ‘S’ and the farthest vertex reachable from ‘S’?

Example: Given a DAG graph :

Source node: 1
The farthest vertex in the above graph from vertex 1 is 2 via the route of vertex 3. So, the distance is 2.

Input Format :

The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains two single space-separated integers ‘V’ and ‘E’ representing the number of vertices and edges of the graph respectively.

The next ‘E’ lines will denote the edges of the graph where every edge is defined by two single space-separated integers ‘X' and 'Y', which signifies an edge from vertex 'X’ to vertex 'Y'.

The last line of each test case contains the single integer ‘S’, representing the Source vertex.

Output Format :

For each test case, print the distance between ‘S’ and the farthest vertex reachable from ‘S’.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= V <= 10^3
1 <= E <= 3*10^3
1 <= X, Y <= V - 1
0 <= S <= V - 1

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is to find the maximum number of vertices that are reachable from the ‘SOURCE’ vertex. We can find that using simple DFS traversal. We don’t need to use any ‘VISITED’ array as the graph given is DAG which means it contains no cycle.

Here is the algorithm :

Create a graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of adjacency list (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
Push the vertices in the ‘GRAPH’.
Create a variable (say, ‘RES’) which will store the maximum reachable distance from the ‘SOURCE’.
Call the ‘DFS’ function, DFS( ‘SOURCE’, ‘GRAPH’) which will calculate the maximum distance reachable from the source and store it in ‘RES’.
Finally, return ‘RES’

DFS( ‘SOURCE’, ‘GRAPH’)

Create a variable (say, ‘DIST’) that will store the maximum distance from the ‘SOURCE’ and initialize it to 0.
Iterate all the adjacent vertices of the source vertex (say, iterator = ‘i’)
- Call the ‘DFS’ function on the adjacent vertices of the ‘SOURCE’ vertex, which will calculate the maximum distance of the adjacent vertex from other vertices. Store it in a variable (say, ‘TEMP’)
- Increment ‘TEMP’ by 1 (Distance between ‘SOURCE’ vertex and adjacent vertex is 1)
- Calculate the maximum distance as the maximum of ‘DIST’ and ‘TEMP’.
Finally, return ‘DIST’.

Solve now

02 Approach

The approach is very similar to approach 1. We will try to avoid making repetitive recursive calls to the recursive functions if we have already calculated an answer for a specific vertex.

But how do we know that there will be repeated recursive calls ?

Let’s understand :

Let’s take an example.

Let the source vertex be 3 from which we have to calculate the maximum distance in the above graph.

There are 2 reachable vertices from vertex 3 which are 0 and 1.
The first recursive call will be made to adjacent vertex 0. (‘DFS’(0, ‘GRAPH’)) which will calculate the maximum distance from vertex 0
The second recursive call will be made to adjacent vertex 1 (‘DFS’(1, ‘GRAPH’)) which will make another recursive call to its adjacent vertex i.e. 0.

As we can see, we made 2 recursive calls at vertex 0 which increases the time complexity in complex graphs. So, to avoid these repetitive calls, we can store previously calculated distances of vertices in an array.

The steps are similar to approach 1. Create an array (say, ‘DP’) and initialize it with -1.

Changes in Functionality of DFS function :

We will also pass a ‘DP’ array with ‘SOURCE’ and ‘GRAPH’ as an argument this time.

Check if DP[SOURCE] exists :
- return DP[SOURCE]
Calculate the maximum distance from the source vertex to other vertices similar to approach 1.
Update DP[SOURCE] as ‘DIST’ (Memoization step)
Finally, return DP[SOURCE]

Solve now