Graph Theory37 sections · 1633 units
Open in Course

Quiz: Path Types

Knowledge check

Check Your Understanding

For SHORTEST path in a DAG with arbitrary edge weights, you can use DP in topological order. What about shortest path in a general graph with negative edges?

  1. A.Use Bellman-Ford. DAG-DP only works because no cycles exist
  2. B.Same DP works for general graphs
  3. C.Negative edges make shortest paths undefined everywhere
  4. D.Convert to DAG first by removing edges
Start the roadmap to answer the quizzes and solve the challenges