25.1.8. Pseudo Code for Longest Path

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Remember the meaning of acyclic.

2. 2.

   What is the result of topological sorting?

   Hint

   Think about the dependencies represented by edges.

3. 3.

   What is a Directed Acyclic Graph?

   • A graph with cycles
   • A graph with directed edges
   • A graph with directed edges and no cycles

   Hint

   Focus on both directed edges and cyclic properties.

4. 4.

   True or False: In a DAG, the longest path can always be found in linear time if using the correct algorithm.

   • True
   • False

   Hint

   Remember the connection between sorting and pathfinding.

5. 5.

   Consider a DAG representing a project with 10 tasks, where each task has dependencies. Construct the graph and calculate the longest path.

   Hint

   Focus on representing dependencies well.

6. 6.

   Modify the previous DAG by adding a new task with dependencies, then recalculate the longest path.

   Hint

   Ensure the new task is correctly added to the workflow.