How to find the maximum weight path between two vertices in a DAG?

Question

In a DAG G with non-negative weighted edges, how do you find the maximum weight path between two vertices in G?

Thanks guys!

Answer 1

You can solve this in O (n + m) time (where n is the number of nodes and m is the number of edges) using topological sorting. Start by performing topological sorting on the inverse graph so that all nodes are ordered so that no node is visited before all its children are visited.

Now we will denote all nodes by the weight of the highest weight, starting from this node. This is done based on the following recursive observation:

• The weight of the highest weight starting from the shell of a node (any node without outgoing edges) is zero, since the only path starting from this node is the path of length to zero only node.
• The weight of the highest weight starting with any other node is determined by the maximum weight of any path formed by the next outgoing edge on the node, and then with the maximum length of the node path.

Since we have nodes reversibly topologically sorted, we can visit all nodes in an order that ensures that if we ever try to follow the edge and look at the cost of the hardest path at the endpoint of this node, we have already calculated the maximum weight path starting from this node. This means that as soon as we get the reverse topological sort order, we can apply the following algorithm to all nodes in this order:

• If node has no outgoing edges, write down the weight of the hardest path starting with node (denoted by d (u)) as zero.
• Otherwise, for each edge (u, v) leaving the current node u, we calculate l (u, v) + d (v) and put d (u) at the highest value achieved in this way.

As soon as we have done this step, we can make the last pass through all nodes and return the maximum value d reached by any node.

The runtime of this algorithm can be analyzed as follows. Topological sorting can be done in O (n + m) time using many different methods. When we then scan each node and each outgoing edge from each node, we visit each node and edge exactly once. This means that we spend time O (n) on nodes and time O (m) at the edges. Finally, we spend O (n) time on one final pass through the elements to find the highest weight path that O (n) takes. This gives a total amount of time O (n + m), which is linear in input size.

Answer 2

A simple brute force algorithm can be written using recursive functions. Start with an empty vector (in C ++: std :: vector) and insert the first node. Then call your recursive function with a vector as an argument that does the following:

• cycle for all neighbors and for each neighbor
  • copy vector
  • add neighbor
  • call us

Also add the total weight as an argument to the recursive function and add the weight to each recursive call.

The function should stop when it reaches the end of the node. Then compare the total weight with the maximum weight that you still have (use the global variable), and if the new total weight is greater, set the maximum weight and save the vector.

The rest is up to you.