Graph Theory37 sections · 1633 units
Open in Course

Quiz: DP on DAGs

Knowledge check

Check Your Understanding

You want the longest path from node 11 to node nn in a DAG with VV nodes and EE edges. You process nodes in topological order and relax edges. What is the time complexity?

  1. A.O(V!)O(V!) because you consider all permutations
  2. B.O(VE)O(V \cdot E) because you relax all edges for each node
  3. C.O(V2)O(V^2) because you compare all pairs
  4. D.O(V+E)O(V + E) because each node and edge is processed once
Start the roadmap to answer the quizzes and solve the challenges