Longest Paths in DAGs using Shortest Path Algorithms

1. From Shortest to Longest: Adapting the Idea

The longest path problem in a general graph (one that may contain cycles) is notoriously difficult—it's NP-hard, meaning no efficient algorithm is known for it. So, why can we solve it efficiently on a DAG?

The reason, as explained in the document "Longest path in a directed acyclic graph (DAG)," is that the problem gains the optimal substructure property when restricted to DAGs. A longest path to a vertex v must contain a longest path to one of its predecessors. This is the same logic that allowed us to use dynamic programming for shortest paths.

With optimal substructure confirmed, we can define a new DP recurrence. If dist[v] now represents the length of the longest path from a source s to v, we need to find the predecessor u that maximizes the path length.

This leads to a new recurrence relation, which should look very familiar:

The only change from the shortest path recurrence is replacing min with max. What about initialization? For shortest paths, we started with ∞ and sought smaller values. For longest paths, we need to start with a value that is guaranteed to be smaller than any possible path length. Therefore, we initialize distances to negative infinity (-∞), with the source vertex's distance still being 0.

The algorithm is a direct adaptation of the one from our last lesson:

1. Initialize: Create a dist array of size V. Set dist[source] = 0 and all other entries to -∞.
2. Topological Sort: Find a topological ordering of the graph's vertices.
3. Iterate and Relax: Go through each vertex u in the topological order. For each outgoing edge (u, v) with weight w, perform the "longest path relaxation":
   • if (dist[u] + w > dist[v]), then update dist[v] = dist[u] + w.

2. The Negation Trick: A Programmer's Shortcut

The learning outcome for this lesson highlights a particularly elegant method: negating edge weights. This technique allows you to find the longest path by calling a shortest path function without changing its internal logic.

The idea is simple yet powerful:

• Maximizing a sum of weights W = w1 + w2 + ... is mathematically equivalent to minimizing the sum of their negatives -W = (-w1) + (-w2) + ....
• Therefore, the longest path in a graph with weights w is the same as the shortest path in a graph with weights -w.

The algorithm using this trick is:

1. Create a conceptual copy of your graph where every edge weight w(u,v) is replaced by -w(u,v).
2. Run the DAG shortest path algorithm (from the previous lesson) on this new graph with negated weights.
3. The resulting shortest path distances, let's call them short_dist[v], will be the negation of the longest path lengths in the original graph.
4. To get the final answer, simply negate the results: longest_dist[v] = -short_dist[v].

This video from WilliamFiset explains this trick clearly.

Both methods—modifying the recurrence or negating the weights—are perfectly valid and have the same $O(V+E)$ complexity. The negation trick is often favored in contests because it maximizes code reuse.

3. A Walkthrough Example

Let's trace the algorithm on the weighted DAG shown below. We will use the first method (modifying the recurrence) to find the longest paths from source vertex 7.

A valid topological sort starting from the nodes with in-degree 0 is 7, 1, 3, 5, 2, 0, 4, 6.

1. Initialization:
   dist = [-∞, -∞, -∞, -∞, -∞, -∞, -∞, 0] (for vertices 0 through 7).

2. Topological Iteration:

   • Process 7 (dist[7] = 0):

     • Relax edge (7,1): dist[1] = max(-∞, 0 + (-1)) = -1.
     • Relax edge (7,5): dist[5] = max(-∞, 0 + (-4)) = -4.
     • Relax edge (7,0): dist[0] = max(-∞, 0 + 6) = 6.
     • Relax edge (7,3): dist[3] = max(-∞, 0 + 4) = 4.
       dist is now [6, -1, -∞, 4, -∞, -4, -∞, 0].

   • Process 1 (dist[1] = -1):

     • Relax edge (1,2): dist[2] = max(-∞, -1 + (-4)) = -5.
     • Relax edge (1,4): dist[4] = max(-∞, -1 + 1) = 0.
     • Relax edge (1,5): dist[5] = max(-4, -1 + 2) = 1. Update!
     • Relax edge (1,6): dist[6] = max(-∞, -1 + 8) = 7.
       dist is now [6, -1, -5, 4, 0, 1, 7, 0].

   • Process 3 (dist[3] = 4):

     • Relax edge (3,0): dist[0] = max(6, 4 + 3) = 7. Update!
     • Relax edge (3,4): dist[4] = max(0, 4 + 5) = 9. Update!
       dist is now [7, -1, -5, 4, 9, 1, 7, 0].

   • Process 5 (dist[5] = 1): No outgoing edges.

   • Process 2 (dist[2] = -5): No outgoing edges.

   • Process 0 (dist[0] = 7):

     • Relax edge (0,6): dist[6] = max(7, 7 + 2) = 9. Update!
       dist is now [7, -1, -5, 4, 9, 1, 9, 0].

   • Process 4 and 6: No outgoing edges.

The final dist array contains the lengths of the longest paths from vertex 7: dist[4] = 9 and dist[6] = 9 are the maximum path lengths found.

4. Application: The Critical Path Method

The longest path algorithm for DAGs isn't just a theoretical exercise; it's the core of the Critical Path Method (CPM), a classic technique used in project management.

Imagine you have a project with many jobs, where some jobs must be completed before others can begin. Each job has a specific duration. The goal is to find the minimum possible time to complete the entire project.

This can be modeled as a longest path problem:

• Nodes represent the start and end of each job.
• An edge from a job's start to its end has a weight equal to its duration.
• A precedence constraint (job A must precede job B) is a zero-weight edge from the end of A to the start of B.
• The longest path through this DAG from a global start node to a global end node represents the critical path. Its length is the minimum total project duration, as it's determined by the longest chain of dependent tasks.

The following resource provides a brief overview of this application.

Conclusion

You've now seen how a single, powerful idea—dynamic programming on a topologically sorted graph—can solve two fundamental problems: shortest and longest paths in a DAG. This pattern is incredibly versatile and a key one to have in your problem-solving arsenal.

Key Takeaways:

• The longest path problem is efficiently solvable in linear time on DAGs because the acyclic nature guarantees the optimal substructure property.
• You can find the longest path by modifying the shortest path algorithm: use max instead of min for relaxation and initialize distances to -∞.
• A common and powerful alternative is to negate all edge weights, run the standard shortest path algorithm for DAGs, and then negate the final distance values.
• The time and space complexity remains linear, $O(V+E)$.
• This algorithm is the basis for practical applications like the Critical Path Method for project scheduling.

Having mastered DP on DAGs, we are now ready to tackle shortest path problems in more general graphs. In the next module, we will explore Dijkstra's algorithm, a cornerstone of graph theory. We'll analyze its greedy approach and understand why it works beautifully for graphs with non-negative weights but fails when negative weights are introduced—a limitation our DAG algorithm did not have.