About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Longest Path In Weighted DAG Problem

Given a weighted directed acyclic graph (DAG), find the longest path between two nodes.

Example

Input:

dag_nodes = 4

dag_from = [1 1 1 3]

dag_to = [2 3 4 4]

dag_weight =  [2 2 4 3]

from_node = 1

to_node = 4

Output: [1, 3, 4]

Total there are two paths from node 1 to node 4:

1) 1 -> 4 with length 4.

2) 1 -> 3 -> 4 with length 2 + 3 = 5.

The latter is the longest one.

Notes

Input Parameters: There are six arguments.

1. An integer dag_nodes

2. An integer array dag_from

3. An integer array dag_to

4. An integer array dag_weight

5. An integer from_node

6. An integer to_node

The first four arguments cumulatively describe the weighted DAG: there are dag_nodes nodes and there is an edge from dag_from[i] node to dag_to[i] node with length dag_weight[i].

Output: Return an array of integers, the nodes in the longest paths from from_node to to_node (including both ends). If from_node=to_node, return [from_node]. If there are multiple longest paths, return any one.

Constraints:

● There will be at most one edge connecting any pair of nodes in one direction, i.e. no multi edges.

● to_node is reachable from from_node.

● 1

● 1

● 1

● Total number of edges in the graph

Solution

Make sure to use an appropriate data type to store the integer values, e.g. long long int in C++.

Given graph is a DAG. In a DAG we can divide our nodes in different levels, with "each edge" going from upper level to lower level.

So we can start updating maximum length level wise, starting from upper level and then moving to level below it!

To divide nodes level wise with each edge going from upper level to lower level, we can use topological sort.

The sample solution we provided uses this approach.

Time Complexity:

O(number of nodes + number of edges). Given the constraints it is equivalent to O(number of edges).

Auxiliary Space Used:

O(number of nodes + number of edges) = O(number of edges).

Space Complexity:

O(number of nodes + number of edges) = O(number of edges).

Note that the complexities aren’t equal to just O(numberber of nodes) because the number of edges in a DAG can be way larger than the number of nodes.


// -------- START --------

const int MAX_NODES = 450, MAX_WEIGHT = 2000000000;

/*
Note that we are passing vectors by reference. Passing vector by value will slow down solution. 
Either use pass by reference or use global vectors.
*/
void dfs(int from, vector>> &node_wise_edges, 
	vector &topological_order, vector &active, vector &visited)
{	
	/*
	Note that we are passing node_wise_edges, topological_order, active and visited by reference. 
	Either pass by reference or use global variables.  
	*/
	// Mark as visited.
	visited[from] = true;
	// This is just for our use you can ignore it. 
	active[from] = true;
	for (int i = 0; i < node_wise_edges[from].size(); i++)
	{
		int to = node_wise_edges[from][i].first;
		// This is just for our use you can ignore it. 
		assert(active[to] == false);
		// If the node is not visited then visit it and do dfs from that node. 
		if (visited[to] == false)
		{
			dfs(to, node_wise_edges, topological_order, active, visited);
		}
	}
	// This is just for our use you can ignore it. 
	active[from] = false;
	/*
	We could have added it at the front, but adding at the front is costly in vector type 
	container, so I have added at the end and then we will reverse this vector. 
	*/
	topological_order.push_back(from);
}

/*
I will quickly try to summarize how topological sorting works. In topological sorting we try to 
order nodes such that, nodes reachable from any ith node comes after the ith node. Suppose we have
only 2 nodes 1 and 2 and one edge 1 -> 2 then toplological order will be [1 2] because 2 is 
reachable from node 1, hence it should come after 1. We can use dfs to find the topological order.
In dfs we visit node then its children and then "come back" to that node "after" we have finished 
visiting all its reachable nodes. So when we have completed visiting all children nodes, then all 
children will have "already" finished visiting their children and will have pushed them self in 
topological order! So now if we add the current node then all its children will be already added! 
Try some examples and it will be more clear!    
*/
vector topological_sort(int dag_nodes, vector>>& node_wise_edges)
{
	vector topological_order;
	/*
	You can ignore the active vector. This is for our use to check if given graph is a valid dag. 
	*/
	vector active(dag_nodes + 1, false);
	// Keeps track of visited nodes. 
	vector visited(dag_nodes + 1, false);
	for (int i = 1; i <= dag_nodes; i++)
	{
		// If the node is not visited then visit it and do dfs from that node. 
		if (visited[i] == false)
		{
			dfs(i, node_wise_edges, topological_order, active, visited);
		}
	}
	/*
	We have added the nodes at the end of topological_order vector that will give nodes in reverse
	order of topological order.
	*/
	reverse(topological_order.begin(), topological_order.end());
	return topological_order;
}

vector find_longest_path(int dag_nodes, vector dag_from, vector dag_to, 
	vector dag_weight, int from_node, int to_node)
{
	int dag_edges = dag_from.size();

	// Separate edges node-wise for quick access in future. 
	vector>> node_wise_edges(dag_nodes + 1, vector>(0));
	for (int i = 0; i < dag_edges; i++)
	{
		node_wise_edges[dag_from[i]].push_back({dag_to[i], dag_weight[i]});
	}

	// Find topological order of given dag.
	vector topological_order = topological_sort(dag_nodes, node_wise_edges);
	assert(topological_order.size() == dag_nodes);

	/*
	Longest_path[i] contains longest path from from_node to ith node (found till now). Here not 
	that we are using long long int! 
	*/
	vector longest_path(dag_nodes + 1, -1);
	/*
	Parent[i] contains node through which Longest_path[i] updated last time. Suppose our final 
	answer is path (1 -> 5 -> 3) then Parent[3] will be 5. This is just to track the path. Using 
	this we will reconstruct the path. 
	*/
	vector parent(dag_nodes + 1, 0);
	// Don't forget this. 
	longest_path[from_node] = 0;

	/*
	Iterate over each node in topological order and update nodes which are connected to the 
	current node. 
	*/
	for (int i = 0; i < dag_nodes; i++)
	{
		int from = topological_order[i];
		/*
		We initialized longest_path of node from_node as 0 and all other nodes as -1, hence update
		will start only at from_node. If you are confused then better to try some examples while 
		understanding this code. 
		*/
		if (longest_path[from] >= 0)
		{
			/*
			"each edge" goes from upper level to lower level hence once we have found our 
			destination node, it will not get updated by any other node so we can stop updating 
			here. This is just an optimization, if we remove this if then also code will work 
			fine. 
			*/
			if (from == to_node)
			{
				break;
			}
			for (int j = 0; j < node_wise_edges[from].size(); j++)
			{
				int to = node_wise_edges[from][j].first;
				long long int weight = node_wise_edges[from][j].second;
				// If longer path possible then update. 
				if (longest_path[to] <= longest_path[from] + weight)
				{
					longest_path[to] = longest_path[from] + weight;
					// Also keep track of node through which it gets updated. 
					parent[to] = from;
				}
			}
		}
	}

	// Find the path in reverse order! And then reverse it! 
	vector path;
	path.push_back(to_node);
	while (to_node != from_node)
	{
		to_node = parent[to_node];
		path.push_back(to_node);
	}
	// Till now we have found the path in reverse order. 
	reverse(path.begin(), path.end());
	return path;
}

// -------- END --------

Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts