Question

Consider a directed acyclic graph (DA

  • G . The problem of finding the longest path in a DAG (with edge weights) can be solved in:
A Polynomial time via dynamic programming after topological sort
B Is NP-hard in DAGs
C Requires exponential time
D Solvable only for unweighted DAGs
E Equivalent to shortest path with Dijkstra
Practice Next

Hey! Ask a query