Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 22 Feb, 2021

Longest Path In Directed Graph

Moderate
Asked in companies
Tata Consultancy Services (TCS)SalesforceCodenation

Problem statement

You are given a Weighted Directed Acyclic Graph (DAG) consisting of ‘N’ nodes and ‘E’ directed edges. Nodes are numbered from 0 to ’N’-1. You are also given a source node ‘Src’ in it. Your task is to find the longest distances from ‘Src’ to all the nodes in the given graph.

Return an array of ‘N’ integers where ‘ith’ integer gives the maximum distance of the node ‘i’ from the source node ‘Src’.

A Directed Acyclic Graph (DAG) is a directed graph that contains no cycles.

Note:

Print -1 if a node is not reachable from the given source node.

Example:

Consider the following DAG consists of 5 nodes and 7 edges,  Let the source node ‘Src’ be 0.

alt text

Then the maximum distance of node 0 from the source node 0 is 0. (the distance of a node from itself is always 0).
The maximum distance of node 1 from the source node 0 is 3. The path that gives this maximum distance is 0 -> 1.
The maximum distance of node 2 from the source node 0 is 10. The path that gives this maximum distance is 0 -> 2.
The maximum distance of node 3 from the source node 0 is 15. The path that gives this maximum distance is 0 -> 2 -> 3.
The maximum distance of node 4 from the source node 0 is 54. The path that gives this maximum distance is 0 -> 1 -> 4.

Thus we should print 0 3 10 15 54
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line of each test case consists of three space-separated integers ‘N’, ‘E’, and ‘Src’ representing the number of nodes, number of edges, and the given source node in the given DAG respectively.

The next ‘E’ lines consist of three space-separated integers ‘U’, ‘V’, ‘W’ representing that there is a directed edge from node U to V having weight ‘W’. 
Output format :
For each test case, print ‘N’ space-separated integers where ’ith’ integer gives the maximum distance of node ‘i’ from the source node ‘Src’.

The output of each test case will be printed in a new line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
0 <= E <= 10^4
0 <= Src <= N-1
0 <= U, V <= N-1
1 <= W <= 10^5

Where ‘T’ is the total number of test cases, ‘N’, ‘E’, and ‘Src’ representing the number of nodes, number of edges, and the given source node in the given DAG respectively.  ‘U’, ‘V’, ‘W’ represents that there is a directed edge from node U to V having weight ‘W’. 


Time limit: 1 sec

Approaches

01 Approach

First we create an integer array ‘maxDistances’  of size ‘N’ and fill it with -1, maxDistances[i] will give the maximum distance of node ‘i’  from the given source node. We will then recursively try out all paths starting from the source node. We will also use an integer variable ‘dist’ to track distance covered so far on this path. Whenever we reaches any node ‘i’ we update its maximum distance i.e maxDistances[i] with maximum of its current value and ‘dist’.

 

Algorithm

  • Create an adjacency list ‘adj’, such that adj[i][j] is a list of two integers [v, w], representing that that ‘jth’ adjacent node of ‘i’ is node ‘v’ and the weight of directed edge i -> v is ‘w’.
  • Create a list of integers 'maxDistances' of size 'N' and fill it with -1.
  • Create a boolean list ‘visited’ of size ‘N’ and fill it with false.
  • Make a recursive function findMaxDistancesHelper(current, dist), where ‘current’ is the current node and ‘dist’ is the distance covered so far on this path (from source node ‘Src’ to current). In each recursive call do the following.
    • Update maxDistances[current] := maximum(maxDistances[current], dist).
    • Mark current node visited i.e visited[current] := true.
    • Iterate over all of its adjacent nodes, 'node’ for which visited[node] is false, and for each of them call  findMaxDistancesHelper(node, dist + weight of directed edge from current to this node).
    • Mark current node unvisited i.e visited[current] := false. This makes this node available to visit by other paths.
  • Return maxDistances after calling this recursive function as findMaxDistancesHelper(Src, 0). In this list maxDistances now maxDistances[i] gives the maximum distance of node ‘i’  from the given source node.