Graph Theory37 sections · 1633 units
Open in CourseQuiz: 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?
- 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
- B.Standard Dijkstra cannot handle weighted graphs with more than dimensions
- C.The visited array would use too much memory
- D.Standard Dijkstra works fine. Adding stops is unnecessary