Graph Theory37 sections · 1633 units
Open in Course

When You Need Longest Paths

Scheduling and critical paths

Longest path in DAGs appears in project scheduling. Each node is a task, edges represent dependencies, and weights are task durations. The longest path is the critical path, the minimum time to complete the project. Another use case is finding the most useful path in a game or decision tree.

Each edge has a reward, and you want the maximum total reward. Remember this only works on DAGs. If your graph has cycles, longest path becomes intractable.