Longest Path In Directed Graph

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
10 upvotes
Asked in companies
SalesforceCodenationSaas labs

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1 0 0
5 7 0
0 1 3
0 2 10
0 3 14
1 3 7
1 4 51
2 3 5
3 4 11
Sample Output 1:
0
0 3 10 15 54
Explanation of Sample Input 1:
Test case 1:
There is only one node, which is also the source node since the distance from the source node to itself is 0, so we will print only a single integer 0.

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
2
5 4 2
0 1 1
0 2 1
1 2 1
3 4 1
5 4 0
0 1 1
0 2 1
1 2 1
3 4 1
Sample Output 2:
-1 -1 0 -1 -1
 0  1  2 -1 -1
Hint

Try out all possible paths starting from the source node.

Approaches (2)
Brute Force

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.
Time Complexity

O(N^N), where  ‘N’ is the number of nodes in the given directed graph.

 

For each node there are at most ‘N’ vertices that can be visited from the current node and there are ‘N’ nodes in the graph. Thus, overall it will take O(N^N) time to explore all the paths.

Space Complexity

O(N + E),  where  ‘N’ is the number of nodes in the given directed graph and E is the number of edges.

 

The space used by the adjacency list ‘adj’ is of the order of O(N + E), the space used by array ‘maxDistances’ is of order O(N) and the space used by recursion stack is of order O(N). Thus, the final space complexity will be O(N+E) + O(N)+ O(N) = O(N+E).

Code Solution
(100% EXP penalty)
Longest Path In Directed Graph
Full screen
Console