medium10 pts · first answer countsgraphstopological-sortdag

Longest path in a dependency graph

For a project plan, you want the longest weighted path (the critical path) in a DAG of tasks. What is true?

A.It is NP-hard, even in a DAGB.Dijkstra with max instead of min solves itC.It needs Floyd-Warshall, O(V^3)D.It takes O(V + E) using topological order

Discussion 0

Join free to post in the discussion.

Longest path in a dependency graph

Discussion 0

Related questions