Last Updated: 22 Feb, 2021

Longest Path In Directed Graph

Moderate

Asked in companies

Solve now

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

Solve now

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.

Solve now

02 Approach

Topological Sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex ‘u’ to vertex ‘v’, vertex ‘u’ comes before ‘v’ in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. We can find topological sorting of any DAG using this algorithm.

We can solve this problem of finding the longest paths in a directed graph in linear time if we process nodes in topological order, and update distances of their adjacent.

Note that if the graph is not DAG, then this problem is an NP-hard problem.

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 list ‘order’ of size ‘N’ that will have topological sorting of graph, Topological sorting can be found using this algorithm.
Assign ‘maxDistances[Src]’ := 0.
Run a loop where ‘i’ ranges from to ‘N’-1, and for each ‘i’ do following -:
- Initialize an integer variable current := order[i].
- If ‘maxDistances[current] == -1, then continue because this node is not reachable from the source node.
- Visit over all the adjacent nodes 'neighbor’ of node current, and update their distances maxDistances[neighbor] := max( maxDistances[neighbors], maxDistances[current] + weight of directed edge between node at current and neighbor)
Return ‘maxDistances’.

Solve now