25.1.4. Setting Up the Longest Path Problem

Try these first

1. 1.

   What is a DAG?

   Hint

   Think about directed edges and cycles.

2. 2.

   Explain topological sorting in one sentence.

   Hint

   No hint provided

3. 3.

   In a DAG, how many times can you revisit a vertex?

   • 0
   • 1
   • As many times as needed

   Hint

   Consider the meaning of acyclic.

4. 4.

   True or False: A topological sort can only be performed on graphs with cycles.

   • True
   • False

   Hint

   Remember the definition of topological sorting.

5. 5.

   Given a DAG with courses and their respective prerequisites represented as edges, calculate the total time to complete all courses and identify the longest path.

   Hint

   Concentrate on sequences of dependencies.

6. 6.

   Explain why finding the longest path in a graph with cycles is a different challenge and what strategies might be applicable.

   Hint

   Think about cycles and their meaning for paths.