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(V⋅E)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