Graph Theory37 sections · 1633 units
Open in Course

LeetCode 787 Cheapest Flights Within K Stops - Lessons

Key takeaways

Dijkstra finds the shortest path in a graph. When you have constraints (like maximum stops), you expand the state space to include the constraint.

Instead of tracking cost per node, you track cost per (node, constraint_value). The algorithm stays the same. You redefine what a "state" is. This technique appears in many problems: shortest path with limited fuel, shortest path visiting certain nodes, shortest path with color constraints. The pattern is always the same: add the constraint to your state.