Graph Theory37 sections · 1633 units
Open in Course

Quiz: Dijkstra with Constraints

Knowledge check

Check Your Understanding

In the Cheapest Flights Within K Stops problem, you add a "stops" dimension to the state: (cost, node, stops_used). Why can you not just use standard Dijkstra with a visited array?

  1. A.A node might need to be visited multiple times with different stop counts, since a higher-cost path with fewer stops may lead to a better final answer
  2. B.Standard Dijkstra cannot handle weighted graphs with more than 22 dimensions
  3. C.The visited array would use too much memory
  4. D.Standard Dijkstra works fine. Adding stops is unnecessary
Start the roadmap to answer the quizzes and solve the challenges